CS Paper Radar

Beyond geometric lattices: pseudo-atoms and redundant join representations in the face lattice of the permutohedron

Giovanni Rossi

cs.DM math.CO ·submitted 2026-11-19 08:50 UTC · v1

Abstract

We study the lattice obtained from the poset of ordered set partitions (the Fubini poset), ordered by merging adjacent blocks, by adjoining a bottom element of rank -1. It is the face lattice of the permutohedron. We look at it from the point of view of geometric lattices: it is graded, atomic and coatomic in the strong sense that every element is a meet of coatoms, but it is not semimodular. Its atoms are the $n!$ permutations, and its elements of rank one, which we call pseudo-atoms, are the edges of the permutohedron. Describing ordered set partitions by chains of subsets, the cuts, we show that the rank is modular whenever the meet is above $\bot$, while the join of two distant atoms can have large rank, so that the rank of the join is a metric on permutations. An element has a unique representation as a join of atoms only up to rank one; above it, irredundant representations have sizes ranging from two to the rank, and the redundancy of an element is its number of atoms minus two. The Möbius function is that of an Eulerian lattice, the Whitney numbers are the face numbers of the permutohedron, and the characteristic polynomial has the alternating coefficients of the geometric case, but only $\bot$ and $\top$ are left-modular, so the lattice is not supersolvable. We show that it is CL-shellable, we exhibit EL-labelings for $n\le5$, and we compare the independent sets of Raz arXiv:2307.05005 (v3, Jan. 2026) with irredundant families and with the matroid of the vertices of the permutohedron. Replacing ordered set partitions by partial flags of subspaces of $\mathbb F_q^n$ gives a $q$-analogue, whose Möbius function is $(-1)^{\mathrm{rk}+1}q^κ$, with $κ$ the number of pairs of elements in a common block at $q=1$, and whose characteristic polynomial and Betti numbers are polynomials in $q$.

Comment
27 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A Canonical m-Atomic Decomposition of Bipartite Graphs via a Grid Model

cs.DS math.CO ·2026-08-20 ·Béla Jónás
theory similarity 0.60
Abstract · 60 pages. Structural decomposition of bipartite graphs via a grid model. Introduces the characteristic m of a brick, determines it for disco…

We study finite, connected, simple bipartite graphs in a grid model, in which a graph is drawn as a rectangular array and its structure is read off from empty subrectangles, called holes. In this model we attach to every brick a numerical invariant, its characteristic m, the difference between the number of rows and the largest proper independent set. A brick is excessive if m > 0. Our main results concern this invariant. We determine the characteristic of a disconnected excessive brick from those of its components, showing that m = min_i min{m_i, imb(W_i)} while the imbalance is additive; and we prove that an m-excessive brick is m-extendable, that is, every matching of size m extends to a maximum matching. Since Plummer's notion of n-extendability is defined only for graphs carrying a perfect matching, and our proof nowhere uses balance, the characteristic extends that notion canonically to unbalanced bipartite graphs. Using the characteristic we partition bipartite graphs into eleven structural classes. The underlying decomposition into atomic blocks is the classical decomposition into elementary components, and the description of the maximum proper independent sets by ideals of the block poset is likewise classical; the paper states precisely which results are classical and are not claimed here. What the grid model adds is a single geometric framework in which holes, characteristics and the block triangular form are read off from one picture.

0.32

Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori

cs.DM math.CO ·2026-09-23 ·Tim Gerlach, Elizabeth Hartung, Pia Herkenrath, Joe Sawada, Aaron Williams
similarity 0.58
Abstract

A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when $n = 2m + 1$ is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into $2^{m-1}$ matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized $\mathcal{O}(1)$-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.

0.23

Unilluminable rooms: minimal examples, classifications and exceptions

cs.CG math.CO ·2026-11-09 ·J. C. F. de Winter, George W. Tokarsky
similarity 0.54
Abstract · 36 pages, 19 figures. Programs and data are included as ancillary files

A room with mirrored walls can contain two points that are mutually invisible: no light ray from one reaches the other. Tokarsky built the first polygonal examples by tiling a room with reflected copies of a triangle and making every tile vertex of certain kinds a corner of the room. We study the smallest rooms of this kind, which we call lattice rooms. Their interior tile vertices of the remaining kind, the sources, are invisible and pairwise mutually invisible. On the tiling by isosceles right triangles, a hole-free lattice room with a source has at least 12 sides, attained only by the pinwheel. On the square tiling the least number is 16, again attained by one room. A hole-free lattice room with two sources has at least 24 sides on the first tiling and 34 on the square tiling. Up to congruence there are 12 such rooms with 24 sides, 89 with 25 sides and 14 with 34 sides. One absorbing post, one partition, or one hole that touches the outer boundary at one point lowers the least number of sides for two sources to 18, 20 and 22 (21 if sides are counted as maximal straight segments). Two and three posts give 17 and 16 sides, and a hole that does not touch the outer boundary gives 26. We list all smallest rooms. Rooms assembled from n modules have exactly 12n sides and n sources, and a hole-free lattice room with three or more sources has at least 36 sides. We also give rooms in which some tile vertices need not be corners: 15 types of 27-sided rooms on the tiling by triangles with angles 30, 60 and 90 degrees, which are smallest in their class, a nonagon with three mutually invisible corners, and a 42-sided room in which a rotation through 180 degrees takes the place of a corner. In a ring of three trapezoids a light ray returns to a corner that is invisible in one trapezoid. Several classifications rely on exhaustive computer searches made finite by the bounds proved here.

0.24

Towards Strongly Aperiodic Monotiles in Higher Dimensions

cs.CG math.MGmath.COmath.DS ·2026-10-01 ·Dmitry Kamenetsky
theorycode/data similarity 0.54
Abstract · 13 pages, 3 tables, 4 figures

The discovery of Chair44 (Tsiokos, 2026) settled the three-dimensional einstein problem with a strongly aperiodic polyhedral monotile in $\mathbb{R}^3$. This note extends the underlying mechanism---the rep-$2^N$ chair $C_N = [0,2]^N \setminus (1,2]^N$ with corner/socket markings---to $\mathbb{R}^N$. Besides expository material (the rep-$2^N$ dissection and a conditional strong-aperiodicity theorem under lattice registration and hierarchical enforcement), the note makes a new computational contribution. We introduce a frame-marking formalism in which the marking of a tile is its full orientation frame and the matching rule is the contact language generated by the substitution itself; this makes the search for matching rules finite in every dimension. We give a finite certificate (coarsening closure, tightness, and a two-shell enclosure analysis) whose validity implies that every lattice-registered tiling by the marked tile is uniquely hierarchical, hence strongly aperiodic. For $N=3$ the certificate passes: it yields explicit facet matching rules on the 24 panels of $C_3$ (135 admissible facet-contact triples) and reproduces, from first principles and independently of published constructions, the Chair44 statistics 2388 $\to$ 44 admissible contacts (30 occurring), 33 one-shell clusters, 15 extendable, each forcing a unique supertile. Among the 2187 homochiral frame assignments of the 3D substitution with a translated central child, the certified one is unique up to conjugation. For $N=4$ the same pipeline is run on several structured families of frame assignments (canonical, $D_4$-, $Z_2\times Z_2$- and $Z_4$-symmetric, and a lift of the 3D solution); none is coarsening-closed, and we report the failure data. A self-similar marking of $C_4$ thus remains an explicitly finite, open computational problem, which we state precisely. Code: https://github.com/dimkadimon/Monotile-RN

0.57

The lattice of antichains of intervals: Dyck paths, level sets, and sweep dimension

cs.DM math.CO ·2026-10-30 ·Paolo Boldi, Sebastiano Vigna
theory similarity 0.53
Abstract

The Clarke-Cormack-Burkowski lattice $\mathcal{E}_n$ is the lattice of antichains of intervals of the chain $\{0,1,\dots,n-1\}$, the algebraic structure underlying minimal-interval semantics, a query semantics used in information retrieval. We give an explicit, elementary anti-isomorphism between $\mathcal{E}_n$ minus its top element and the Stanley lattice of Dyck words of semilength $n+1$ (an anti-isomorphism whose existence is implicit in work of Ferrari and Munarini), under which the rank of an antichain is $\binom{n+1}{2}$ minus the area of the associated Dyck word. Hence the rank generating function of $\mathcal{E}_n\setminus\{\top\}$ is the reverse of the Carlitz-Riordan $q$-Catalan polynomial. Using a local limit theorem for the area of random-walk excursions, we confirm unconditionally an asymptotic formula of Takács: the size $λ_n$ of the largest level set of $\mathcal{E}_n$ satisfies $λ_n\simκ\,4^{n+1}/(n+1)^3$, where $κ\approx1.0807$. Finally, for the antichains of intervals of an arbitrary finite poset $P$ we study the sweep dimension, the minimum number of linear orders needed to separate every interval from every element outside it. It equals the Dushnik-Miller dimension of the lattice of convex subsets of $P$, it is the least $k$ for which $P$ maps into $\mathbb{R}^k$ so that every interval is the preimage of an upper orthant, and it lies between $\max(2,w)$ and $2w$, where $w$ is the width of $P$, both bounds being tight. Antichains of intervals embed, preserving joins, into $k$-dimensional staircase regions.

0.13

On the Triangle Inequality for the Jaccard Distance in Arbitrary Lattices

cs.AI cs.DMmath.CO ·2026-08-18 ·Costin Bădică, Amelia Bădică
theory similarity 0.52
Abstract

This paper presents new theoretical results on generalizing the Jaccard distance for lattices and real valuations. We demonstrate that when the valuation is strictly positive, monotone, and modular, the Jaccard distance satisfies the triangle inequality on arbitrary lattices, effectively generalizing earlier results that depended heavily on distributivity. Moving to relatively complemented distributive lattices (which safely drop the requirement for the global bounds found in Boolean algebras), we prove the triangle inequality holds as long as the valuation is positive, monotone, supermodular, and $\log$-submodular. Additionally, we adapt the symmetric-difference Jaccard formulation for submodular valuations to sectionally complemented distributive lattices. Shifting to necessary conditions, we prove that supermodularity is a strict requirement for the standard generalized Jaccard distance to operate as a valid metric. Finally, we map the practical value of relaxing these structural constraints to computational fields like quantum information theory, formal concept analysis, and machine learning, closing with a brief look at open mathematical problems.

0.24

UTVPI-representable integer point sets: discrete convexity, polymorphisms, and pairwise closure

cs.DM ·2026-08-25 ·Kei Kimura, Kazuhisa Makino, Shota Yamada, Ryo Yoshizumi
theory similarity 0.52
Abstract · 48 pages, v2: acknowledgments updated, references added

We study subsets of the integer lattice represented by single-variable-per-inequality (SVPI), difference-constraint (DC), unit two-variable-per-inequality (UTVPI), and two-variable-per-inequality (TVPI) systems. We relate five viewpoints: inequality representation, discrete convexity, polymorphisms, reconstruction from two-coordinate projections, and fixed points of closure operators. Our central result completely characterizes UTVPI-representability. For every set $S\subseteq\mathbb Z^n$ with $n>1$, \[ \begin{aligned} &S\text{ is UTVPI-representable}\\ &\;\Longleftrightarrow\; S\text{ is closed under the directed midpoint and median operations}\\ &\;\Longleftrightarrow\; S\text{ is integrally convex and $2$-decomposable}. \end{aligned} \] The median condition may instead be replaced by closedness under some majority operation, and the same class is the fixed-point class of a pairwise directed-midpoint closure operator. Thus, all five viewpoints yield equivalent characterizations of UTVPI-representability. In particular, $2$-decomposability is exactly the global condition needed to lift the known two-dimensional equivalence between integral convexity and UTVPI-representability to arbitrary dimension. This theorem is embedded in a broader pairwise-closure theory. For a family $F$ of operations, we define a closure operator by closing every two-coordinate projection under $F$ and joining the resulting sets. Its fixed points are precisely the sets that are both $2$-decomposable and $F$-closed, and we establish a local-to-global criterion for such characterizations. A closed-convex-hull analogue characterizes TVPI-representability. We also characterize SVPI-representability by natural multioperations, prove limitations of operation-based characterizations for several related classes, and determine the complete inclusion hierarchies in the general, Boolean, and two-dimensional settings.

0.26

Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance

cs.IT ·2026-09-30 ·Fengqi Hou
similarity 0.52
Abstract · 15 pages. Lean formalization included as ancillary files

We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for $K_{3,3}$ and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most $2^{δ+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $δ$, where $C$ is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for $(\mathbb R^m,\|\cdot\|_1)$ for every $m\ge1$.

0.12