Recent combinatorial_theory items

Growth diagram proofs for the Littlewood identities

Mon, 20 Apr 2026 00:00:00 +0000

The (dual) Cauchy identity has an easy algebraic proof utilising a commutation relation between the up and (dual) down operators. By using Fomin's growth diagrams, a bijective proof of the commutation relation can be "bijectivised" to obtain RSK like correspondences. In this paper we give a concise overview of this machinery and extend it to Littlewood type identities by introducing a new family of relations between these operators, called projection identities. Thereby we obtain infinite families of bijections for the Littlewood identities generalising the classical ones. We believe that this approach will be useful for finding bijective proofs for Littlewood type identities in other settings such as for Macdonald polynomials and their specialisations, alternating sign matrices or vertex models.

Mathematics Subject Classifications: 05E05, 05A19

Keywords: Littlewood identity, growth diagrams, Robinson-Schensted-Knuth correspondence, RSK, Schur polynomials

Quotients of M-convex sets and M-convex functions

Mon, 20 Apr 2026 00:00:00 +0000

We unify the study of quotients of matroids, polymatroids, valuated matroids and strong maps of submodular functions in the framework of Murota's discrete convex analysis. As a main result, we compile a list of ten equivalent characterizations of quotients for M-convex sets, generalizing existing formulations for (poly)matroids and submodular functions. We also initiate the study of quotients of M-convex functions, constructing a hierarchy of four separate characterizations. Our investigations yield new insights into the fundamental operation of induction, as well as the structure of linking sets and linking functions, which are generalizations of linking systems and bimatroids.

Mathematics Subject Classifications: 05B35, 14T15, 52B20, 52B40, 14M15, 90C25, 90C27

Keywords: Discrete convex functions, flag matroids, discrete convex analysis, matroid theory, matroid quotients, polymatroids

Structure of quasi-crystal graphs and applications to the combinatorics of quasi-symmetric functions

Mon, 20 Apr 2026 00:00:00 +0000

Crystal graphs are powerful combinatorial tools for working with the plactic monoid and symmetric functions. Quasi-crystal graphs are an analogous concept for the hypoplactic monoid and quasi-symmetric functions. This paper makes a combinatorial study of these objects. We explain a previously-observed isomorphism of components of the quasi-crystal graph, and provide an explicit description using a new combinatorial structure called a quasi-array. Then two conjectures of Maas-Gariépy on the interaction of fundamental quasi-symmetric functions and Schur functions and on the arrangement of quasi-crystal components within crystal components are answered, the former positively, the latter negatively.

Mathematics Subject Classifications: 05E05, 05E99

Keywords: Crystal graphs, quasi-crystal graphs, quasi-symmetric functions

Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction-based approach

Mon, 20 Apr 2026 00:00:00 +0000

By a classic result of Gessel, the exponential generating functions for \(k\)-regular graphs are D-finite. Using Gröbner bases in Weyl algebras, we compute the linear differential equations satisfied by the generating function for 5-, 6-, and 7- regular graphs. The method is sufficiently robust to consider variants such as graphs with multiple edges, loops, and graphs whose degrees are limited to fixed sets of values.

Mathematics Subject Classifications: 05C30, 12H05

Keywords: Regular graph, enumeration, Weyl algebra, reduction-based integration

Representability of the direct sum of uniform \(q\)-matroids

Mon, 20 Apr 2026 00:00:00 +0000

There are many similarities between the theories of matroids and \(q\)-matroids. However, when dealing with the direct sum of \(q\)-matroids many differences arise. Most notably, it has recently been shown that the direct sum of representable \(q\)-matroids is not necessarily representable. In this work, we focus on the direct sum of uniform \(q\)-matroids. Using algebraic and geometric tools, together with the notion of cyclic flats of \(q\)-matroids, we show that this is always representable, by providing a representation over a sufficiently large field.

Mathematics Subject Classifications: 05B35, 94B05, 51E20

Keywords: \(q\)-matroids, representability, evasive subspaces, rank-metric codes, linear sets

The intersection density of cubic arc-transitive graphs with \(2\)-arc-regular full automorphism group equal to \( \operatorname{PGL}_{2}(q)\)

Mon, 20 Apr 2026 00:00:00 +0000

The intersection density of a transitive permutation group \(G\leq \operatorname{Sym}(V)\) is the ratio between the largest size of a subset of \(G\) in which any two agree on at least one element of \(V\), and the order of a point-stabilizer of \(G\). In this paper, we determine the intersection densities of the automorphism groups of the arc-transitive graphs admitting a \(2\)-arc-regular full automorphism group \(G^* = \operatorname{PGL}_{2}(q)\) and an arc-regular subgroup of automorphism \(G = \operatorname{PSL}_{2}(q)\).

Mathematics Subject Classifications: 05C35, 05C69, 20B05

Keywords: Derangement graphs, cocliques, projective special linear groups

Shuffle bases and quasisymmetric power sums

Mon, 20 Apr 2026 00:00:00 +0000

The algebra of quasisymmetric functions QSym and the shuffle algebra of compositions Sh are isomorphic as graded Hopf algebras (in characteristic zero), and isomorphisms between them can be specified via shuffle bases of QSym. We use the notion of infinitesimal characters to characterize shuffle bases, and we establish a universal property for Sh in the category of connected graded Hopf algebras equipped with an infinitesimal character, analogous to the universal property of QSym as a combinatorial Hopf algebra described by Aguiar, Bergeron, and Sottile. We then use these results to give general constructions for quasisymmetric power sums, recovering four previous constructions from the literature, and study their properties.

Mathematics Subject Classifications: 05E05, 16T30

Keywords: Quasisymmetric functions, quasisymmetric power sums, shuffle algebra, compositions, infinitesimal characters

Sperner systems with restricted differences

Mon, 20 Apr 2026 00:00:00 +0000

Let \(\mathcal{F}\) be a family of subsets of \([n]\) and \(L\) be a subset of \([n]\). We say \(\mathcal{F}\) is an \(L\)-differencing Sperner system if \(|A\setminus B|\in L\) for any distinct \(A,B\in\mathcal{F}\). Let \(p\) be a prime and \(q\) be a power of \(p\). Frankl first studied \(p\)-modular \(L\)-differencing Sperner systems and showed an upper bound of the form \(\sum_{i=0}^{|L|}\binom{n}{i}\). In this paper, we obtain new upper bounds on \(q\)-modular \(L\)-differencing Sperner systems using elementary \(p\)-adic analysis and polynomial method, extending and improving existing results substantially. Moreover, our techniques can be used to derive new upper bounds on subsets of the hypercube with restricted Hamming distances. One highlight of the paper is the first analogue of the celebrated Snevily's theorem in the \(q\)-modular setting, which results in several new upper bounds on \(q\)-modular \(L\)-avoiding \(L\)-intersecting systems. In particular, we improve...

Chow polynomials of uniform matroids are real-rooted

Mon, 20 Apr 2026 00:00:00 +0000

June Huh and Matthew Stevens conjectured that the Hilbert-Poincaré series of the Chow ring of any matroid is a polynomial with only real zeros. We prove this conjecture for the class of uniform matroids. We also prove that the Chow polynomial and the augmented Chow polynomial of any maximal ranked poset have only real zeros.

Mathematics Subject Classifications: 05E14, 05B35, 06A07, 26C10

Keywords: Chow polynomials, real-rooted polynomials, partially ordered sets, geometric lattices

Uncountably many enumerations of well-quasi-ordered permutation classes

Mon, 20 Apr 2026 00:00:00 +0000

We construct an uncountable family of well-quasi-ordered permutation classes, each with a distinct enumeration sequence. This disproves a conjecture that all well-quasi-ordered permutation classes have algebraic generating functions, and in fact shows that many such classes lack D-finite or D-algebraic generating functions. Our construction is based on an uncountably large collection of factor-closed, well-quasi-ordered binary languages due to Pouzet.

Mathematics Subject Classifications: 05A05, 05A15, 06A07

Keywords: Generating functions, permutation classes, well-quasi-order

Improved bound on the number of cycle sets

Mon, 20 Apr 2026 00:00:00 +0000

The cycle set of a graph \(G\) is the set consisting of all sizes of cycles in \(G\). Answering a conjecture of Erdős and Faudree, Verstraëte showed that there are at most \(2^{n - n^{1/10}}\) different cycle sets of graphs with \(n\) vertices. We improve this bound to \(2^{n - n^{1/2 - o(1)}}\). Our proof follows the general strategy of Verstraëte of reducing the problem to counting cycle sets of Hamiltonian graphs with many chords or a large maximum degree. The key new ingredients are near-optimal container lemmata for cycle sets of such graphs.

Mathematics Subject Classifications: 05C30, 05C38

Keywords: Cycle sets, container method

High-dimensional envy-free partitions

Mon, 20 Apr 2026 00:00:00 +0000

A vast array of envy-free results have been found for the subdivision of one-dimensional resources, such as the interval \([0,1]\). The goal is to divide the space into \(n\) pieces and distribute them among \(n\) guests such that each receives their favorite pieces. We study high-dimensional versions of these results. We prove that several spaces of convex partitions of \(\mathbb{R}^d\) allow for envy-free division among any \(n\) guests. We also prove the existence of convex partitions of \(\mathbb{R}^d\) which allow envy-free divisions among several groups of \(n\) guests simultaneously.

Mathematics Subject Classifications: 91B32, 52A37, 55M20, 28A75

Keywords: Mass partition, KKM cover, Envy-free partition, Equivariant topology, Voronoi diagram

Branching rules of minuscule representations via a new partial order

Mon, 20 Apr 2026 00:00:00 +0000

We introduce a new partial order on the set of all antichains of a fixed size in any poset. When applied to minuscule posets, these partial orders give rise to distributive lattices that appear in the branching rules for minuscule representations of complex simple Lie algebras.

Mathematics Subject Classifications: 06A07, 05E10, 06A11

Keywords: Antichain, distributive lattice, minuscule representation, branching rule

Colorful intersections and Tverberg partitions

Mon, 20 Apr 2026 00:00:00 +0000

We prove an extension of Tverberg's classical result on partitioning a point set in \(\mathbb{R}^d\) by replacing the point set with families of convex sets which satisfy the colorful Helly hypothesis. In particular, we show the following for any integers \(d \geq m \geq 1\) and \(r\) a prime power. Suppose \(F_1, F_2, \dots, F_m\) are families of convex sets in \(\mathbb{R}^d\), each of size \({n › (\frac{d}{m}+1)(r-1)}\), such that for every choice \(C_1\in F_1, C_2\in F_2, \dots,C_m \in F_m\) we have \(\bigcap_{i=1}^mC_i\neq \varnothing\). Then, one of the families \(F_i\) admits a Tverberg \(r\)-partition. That is, one of the families \(F_i\) can be partitioned into \(r\) nonempty parts such that the convex hulls of the parts have nonempty intersection. As a corollary, we extend the work of Karasev and Montejano concerning geometric transversals to families of convex sets in \(\mathbb{R}^d\) that satisfy the colorful Helly hypothesis.

Mathematics Subject Classifications:...

Relative Lonely Runner spectra

Mon, 20 Apr 2026 00:00:00 +0000

For a subtorus \(T \subseteq (\mathbb{R}/\mathbb{Z})^n\), let \(D(T)\) denote the \(L^\infty\)-distance from \(T\) to the point \((1/2, \ldots, 1/2)\). For a subtorus \(U \subseteq (\mathbb{R}/\mathbb{Z})^n\), define \(\mathcal{S}_1(U)\), the Lonely Runner spectrum relative to \(U\), to be the set of all values of \(D(T)\) as \(T\) ranges over the \(1\)-dimensional subtori of \(U\) not contained in the union of the coordinate hyperplanes of \((\mathbb{R}/\mathbb{Z})^n\). The relative spectrum \(\mathcal{S}_1((\mathbb{R}/\mathbb{Z})^n)\) is the ordinary Lonely Runner spectrum that has been studied previously. Giri and the second author recently showed that the relative spectra \(\mathcal{S}_1(U)\) for two-dimensional subtori \(U \subseteq (\mathbb{R}/\mathbb{Z})^n\) essentially govern the accumulation points of the Lonely Runner spectrum \(\mathcal{S}_1((\mathbb{R}/\mathbb{Z})^n)\). In the present work, we prove that such relative spectra \(\mathcal{S}_1(U)\) have a very rigid...

Order and inverses in the monoid of misère blocking games

Mon, 20 Apr 2026 00:00:00 +0000

This paper considers combinatorial games with the last move losing (misère play) instead of winning (normal play). Misère games form a pomonoid in which no non-zero elements are invertible; normal-play games, however, form a group with a much richer partial order. To compensate, misère researchers typically weaken the comparison relation by restricting to a subset of games, especially to a "universe" (closed under addition, conjugation, and options). For some well-studied universes (like the dicot and dead-ending universes), there exist finite comparison tests and also complete characterisations of their invertible elements; more recently, the invertible elements of every "parental" universe have been characterised. In this paper, we study the recently-defined universe of "blocking games" (containing both dicots and dead-ending games): we develop a finite comparison test, and we improve on the general invertibility characterisation by showing that, as in dead-ending, a game...

Two gluing methods for string C-group representations of the symmetric groups

Mon, 20 Apr 2026 00:00:00 +0000

The study of string C-group representations of rank at least \(n/2\) for the symmetric group \(S_n\) has gained a lot of attention in the last fifteen years. In a recent paper, Cameron et al. gave a list of permutation representation graphs of rank \(r\geq n/2\) for \(S_n\), having a fracture graph and a non-perfect split. They conjecture that these graphs are permutation representation graphs of string C-groups. In trying to prove this conjecture, we discovered two new techniques to glue two CPR graphs for symmetric groups together. We discuss the cases in which they yield new CPR graphs. By doing so, we invalidate the conjecture of Cameron et al. We believe our gluing techniques will be useful in the study of string C-group representations of high ranks for the symmetric groups.

Mathematics Subject Classifications: 20B30, 05C25, 52B15

Keywords: String C-group representations, symmetric groups, permutation representation graphs, CPR graphs

Colored multiset Eulerian polynomials

Mon, 20 Apr 2026 00:00:00 +0000

Colored multiset Eulerian polynomials are a common generalization of MacMahon's multiset Eulerian polynomials and the colored Eulerian polynomials, both of which are known to satisfy well-studied distributional properties including real-rootedness, log-concavity and unimodality. The symmetric colored multiset Eulerian polynomials are characterized and used to prove sufficient conditions for a colored multiset Eulerian polynomial to be self-interlacing. The latter property implies the aforementioned distributional properties as well as others, including the alternatingly increasing property and bi-\(\gamma\)-positivity. To derive these results, multivariate generalizations of an identity due to MacMahon are deduced. The results are applied to a pair of questions, both previously studied in several special cases, that are seen to admit more general answers when framed in the context of colored multiset Eulerian polynomials. The first question pertains to \(s\)-Eulerian polynomials,...

Labeling regions in deformations of graphical arrangements

Mon, 2 Feb 2026 00:00:00 +0000

Combining Carver's variant of the Farkas' lemma with the Flow Decomposition Theorem we show that the regions of any deformation of a graphical arrangement may be bijectively labeled with a set of weighted digraphs containing directed cycles of negative weight only. Bounded regions correspond to strongly connected digraphs. The study of the resulting labelings allows us to add the omitted details in Stanley's proof on the injectivity of the Pak-Stanley labeling of the regions of the extended Shi arrangement, to generalize the ceiling diagrams in the deleted Shi and Ish arrangements studied by Armstrong and Rhoades and to introduce a new labeling of the regions in the Fuss-Catalan arrangement. We also point out that Athanasiadis-Linusson labelings may be used to directly count regions in a class of arrangements properly containing the extended Shi arrangement and the Fuss-Catalan arrangement.

Mathematics Subject Classifications: 52C35, 05A10, 05A15, 11B83

Keywords:...

Skeletal generalizations of chip-firing games, parking functions, and Dyck paths

Mon, 2 Feb 2026 00:00:00 +0000

For \(0\leq k\leq n-1\), we introduce a family of \(k\)-skeletal paths which are counted by the \(n\)th Catalan number for each \(k\), and specialize to Dyck paths when \(k=n-1\). We similarly introduce \(k\)-skeletal parking functions which are equinumerous with spanning trees on the complete graph with \(n+1\) vertices for each \(k\), and specialize to classical parking functions for \(k=n-1\). The preceding constructions are generalized to paths lying in a trapezoid with base \(c › 0\) and southeastern diagonal of slope \(1/m\); \(c\) and \(m\) need not be integers. We give bijections among these families when \(k\) varies with \(m\) and \(c\) fixed. Our constructions are motivated by chip firing and have connections to combinatorial representation theory and tropical geometry.

Mathematics Subject Classifications: 05A15, 05A19, 05C57

Keywords: Chip firing, skeletal objects, lattice paths, Dyck paths, parking functions, Catalan numbers, ballot numbers

Some enumerative properties of parking functions

Mon, 2 Feb 2026 00:00:00 +0000

A parking function is a sequence \((\pi_1,\dots, \pi_n)\) of positive integers such that if \(\lambda_1\leq\cdots\leq \lambda_n\) is the increasing rearrangement of \(\pi_1,\dots,\pi_n\), then \(\lambda_i\leq i\) for \(1\leq i\leq n\). In this paper we obtain some new results on the enumeration of parking functions. We will consider the joint distribution of several sets of statistics on parking functions. The distribution of most of these individual statistics is known, but the joint distributions are new. Parking functions of length \(n\) are in bijection with labelled forests on the vertex set \([n]=\{1,2,\dots,n\}\) (or rooted trees on \([n]_0=\{0,1,\dots,n\}\) with root \(0\)), so our results can also be applied to labelled forests. Extensions of our techniques are discussed, including an extension to a probabilistic scenario.

Mathematics Subject Classifications: 05A15, 60C05, 05A19

Keywords: Parking function, labelled forest, generating function, recurrence,...

Ryser's Theorem for symmetric \(\rho\)-latin squares

Mon, 2 Feb 2026 00:00:00 +0000

Let \(L\) be an \(n\times n\) array whose top left \(r\times r\) subarray is filled with \(k\) different symbols, each occurring at most once in each row and at most once in each column. We establish necessary and sufficient conditions that ensure the remaining cells of \(L\) can be filled such that each symbol occurs at most once in each row and at most once in each column, \(L\) is symmetric with respect to the main diagonal, and each symbol occurs a prescribed number of times in \(L\). The case where the prescribed number of times each symbol occurs is \(n\) was solved by Cruse (J. Combin. Theory Ser. A 16 (1974), 18-22), and the case where the top left subarray is \(r\times n\) and the symmetry is not required, was settled by Goldwasser et al. (J. Combin. Theory Ser. A 130 (2015), 26-41). Our result allows the entries of the main diagonal to be specified as well, which leads to an extension of the Andersen-Hoffman Theorem (Annals of Disc. Math. 15 (1982) 9-26, European...

On the face stratification of the \(m=2\) amplituhedron

Mon, 2 Feb 2026 00:00:00 +0000

We define and study the face stratification of the \(m=2\) amplituhedron. We show that the face poset is an upper order ideal in the face poset of the totally nonnegative Grassmannian. Our construction is consistent with earlier work of Lukowski, and we confirm various predictions of Lukowski.

Mathematics Subject Classifications: 05E14, 52B40

Keywords: Total positivity, amplituhedron, Grassmannian

Diagonal operators, \(q\)-Whittaker functions and rook theory

Mon, 2 Feb 2026 00:00:00 +0000

We discuss the problem posed by Bender, Coley, Robbins and Rumsey of enumerating the number of subspaces which have a given profile with respect to a linear operator over the finite field \(\mathbb{F}_q\). We solve this problem in the case where the operator is diagonalizable. The solution leads us to a new class of polynomials \(b_{\mu\nu}(q)\) indexed by pairs of integer partitions. These polynomials have several interesting specializations and can be expressed as positive sums over semistandard tableaux. We present a new correspondence between set partitions and semistandard tableaux. A close analysis of this correspondence reveals the existence of several new set partition statistics which generate the polynomials \(b_{\mu\nu}(q)\); each such statistic arises from a Mahonian statistic on multiset permutations. The polynomials \(b_{\mu\nu}(q)\) are also given a description in terms of coefficients in the monomial expansion of \(q\)-Whittaker symmetric functions which are...

Periodic colorings and orientations in infinite graphs

Mon, 2 Feb 2026 00:00:00 +0000

We study the existence of periodic colorings and orientations in locally finite graphs. A coloring or orientation of a graph \(G\) is periodic if the resulting colored or oriented graph is quasi-transitive, meaning that \(V(G)\) has finitely many orbits under the action of the group of automorphisms of \(G\) preserving the coloring or the orientation. When such a periodic coloring or orientation of \(G\) exists, \(G\) itself must be quasi-transitive and it is natural to investigate when quasi-transitive graphs have such periodic colorings or orientations. We provide examples of Cayley graphs with no periodic orientation or non-trivial coloring, and examples of quasi-transitive graphs of treewidth 2 without periodic orientation or proper coloring. On the other hand we show that every quasi-transitive graph \(G\) of bounded pathwidth has a periodic proper coloring with \(\chi(G)\) colors and a periodic orientation. We relate these problems with techniques and questions from symbolic...

A tower lower bound for the degree relaxation of the Regularity Lemma

Mon, 2 Feb 2026 00:00:00 +0000

It is well-known that if \((A,B)\) is an \(\tfrac{\varepsilon}{2}\)-regular pair (in the sense of Szemerédi) then there exist sets \(A'\subset A\) and \(B'\subset B\) with \(|A'|\le \varepsilon|A|\) and \(|B'|\le \varepsilon|B|\) so that the degrees of all vertices in \(A\setminus A'\) differ by at most \(\varepsilon|B|\) and the degrees of all vertices in \(B\setminus B'\) differ by at most \(\varepsilon|A|\). We call such a property \(\varepsilon\)-degularity. This leads to the notion of an \(\varepsilon\)-degular partition of a graph in the same way as the definition of \(\varepsilon\)-regular pairs leads to the notion of \(\varepsilon\)-regular partitions.

We show that there exist graphs in which any \(\varepsilon\)-degular partition requires the number of clusters to be \(\mathrm{tower}(\Theta(\varepsilon^{-1/3}))\). That is, even though degularity is a substantial relaxation of regularity, in general one cannot improve much on the bounds that come with Szemerédi's...

On a question of Gowers on clique differences

Mon, 2 Feb 2026 00:00:00 +0000

We solve a question of Gowers from 2009 on clique differences in chains, thus ruling out any Sperner-type proof of the polynomial density Hales-Jewett Theorem for alphabets of size 2.

Mathematics Subject Classifications: 05D10

Keywords: Hales-Jewett, Polynomial Hales-Jewett, Ramsey Theory

The foundation of generalized parallel connections, 2-sums, and segment-cosegment exchanges of matroids

Mon, 2 Feb 2026 00:00:00 +0000

We show that, under suitable hypotheses, the foundation of a generalized parallel connection of matroids is the relative tensor product of the foundations. Using this result, we show that the foundation of a 2-sum of matroids is the absolute tensor product of the foundations, and that the foundation of a matroid is invariant under segment-cosegment exchange.

Mathematics Subject Classifications: 05B35, 20Axx

Keywords: Matroids, pastures, foundations, generalized parallel connection, 2-sum, segment-cosegment exchange

The Ehrhart \(h^\ast\)-polynomials of positroid polytopes

Mon, 2 Feb 2026 00:00:00 +0000

A positroid is a matroid realized by a matrix such that all maximal minors are non-negative. Positroid polytopes are matroid polytopes of positroids. In particular, they are lattice polytopes. The Ehrhart polynomial of a lattice polytope counts the number of integer points in the dilation of that polytope. The Ehrhart series is the generating function of the Ehrhart polynomial, which is a rational function with the numerator called the \(h^\ast\)-polynomial. We compute the \(h^\ast\)-polynomials of an arbitrary positroid polytope by a family of shelling orders of it. We also compute the \(h^\ast\)-polynomial of any positroid polytope with some facets removed and we relate it to the descents of permutations. Our result generalizes that of Early, Kim, and Li for hypersimplices.

Mathematics Subject Classifications: 05B35

Keywords: Positroid, Ehrhart theory

An extension theorem for signotopes

Mon, 2 Feb 2026 00:00:00 +0000

In 1926, Levi showed that, for every pseudoline arrangement \(\mathcal{A}\) and two points in the plane, \(\mathcal{A}\) can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in \(\mathbb{R}^d\) with a hyperplane containing \(d\) prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in \(\mathbb{R}^3\) which cannot be extended with a pseudoplane containing two particular prescribed points. In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks \(r \geq 4\) there exist signotopes...

Poset polytopes and pipe dreams: types C and B

Mon, 2 Feb 2026 00:00:00 +0000

The first part of this paper concerns type C. We present new explicitly defined families of algebro-combinatorial structures of three kinds: combinatorial bases in representations, Newton-Okounkov bodies of flag varieties and toric degenerations of flag varieties. All three families are parametrized by the same family of polytopes: the marked chain-order polytopes of Fang and Fourier which interpolate between the type C Gelfand-Tsetlin and FFLV polytopes. Thus, in each case the obtained structures interpolate between the well-known bases, Newton-Okounkov bodies or degenerations associated with the latter two polytopes. We then obtain similar results for type B after introducing a new family of poset polytopes to be considered in place of marked chain-order polytopes. In both types our constructions and proofs rely crucially on a combinatorial connection between poset polytopes and pipe dreams.

Mathematics Subject Classifications: 14M15, 17B10, 05E14, 05E10, 52B20, 06A11

Keywords:...

Canonical theorems in geometric Ramsey theory

Mon, 2 Feb 2026 00:00:00 +0000

In Euclidean Ramsey Theory usually we are looking for monochromatic configurations in the Euclidean space, whose points are colored with a fixed number of colors. In the canonical version, the number of colors is arbitrary, and we are looking for an `unavoidable' set of colorings of a finite configuration, that is, a set of colorings with the property that one of them always appears in any coloring of the space. This set definitely includes the monochromatic and the rainbow colorings. In the present paper, we prove the following two results of this type. First, for any acute triangle \(T\), and any coloring of \(\mathbb{R}^3\), there is either a monochromatic or a rainbow copy of \(T\). Second, for every \(m\), there exists a sufficiently large \(n\) such that in any coloring of \(\mathbb{R}^n\), there exists either a monochromatic or a rainbow \(m\)-dimensional unit hypercube. In the maximum norm, \(\ell_{\infty}\), we have a much stronger statement. For every finite \(M\),...

Sidorenko hypergraphs and random Turán numbers

Mon, 2 Feb 2026 00:00:00 +0000

Let \(\mathrm{ex}(G_{n,p}^r,F)\) denote the maximum number of edges in an \(F\)-free subgraph of the random \(r\)-uniform hypergraph \(G_{n,p}^r\), and let \[s(F):=\sup\{s: \exists H, t_F(H)=t_{K_r^r}(H)^{s+e(F)}›0\}.\] Following recent work of Conlon, Lee, and Sidorenko, we prove non-trivial lower bounds on \(\mathrm{ex}(G_{n,p}^r,F)\) whenever \(s(F)›0\), i.e. \(F\) is not Sidorenko. This connection between Sidorenko's conjecture and random Turán problems gives new lower bounds on \(\mathrm{ex}(G_{n,p}^r,F)\) whenever \(s(F)›0\), and further allows us to establish upper bounds for \(s(F)\) whenever upper bounds for \(\mathrm{ex}(G_{n,p}^r,F)\) are known. As a consequence, we prove that \(s(\mathrm{E}^r(K_{k+1}^k))=\frac{1}{r-k}\) where \(\mathrm{E}^r(K_{k+1}^k)\) is the \(r\)-expansion of \(K_{k+1}^k\).

Mathematics Subject Classifications: 05C65, 05C80, 05D05, 05D40

Keywords: Hypergraph, Sidorenko Conjecture, Random Turán Problem

Subsets of free groups with distinct differences

Mon, 2 Feb 2026 00:00:00 +0000

Let \(F_n\) be a free group of rank \(n\), with free generating set \(X\). A subset \(D\) of \(F_n\) is a Distinct Difference Configuration if the differences \(g^{-1}h\) are distinct, where \(g\) and \(h\) range over all (ordered) pairs of distinct elements of \(D\). The subset \(D\) has diameter at most \(d\) if these differences all have word length at most \(d\). When \(n\) is fixed and \(d\) is large, the paper shows that the largest distinct difference configuration in \(F_n\) of diameter at most \(d\) has size approximately \((2n-1)^{d/3}\).

Mathematics Subject Classifications: 05B10, 20E05

Keywords: Difference sets, distinct difference configurations, free groups, combinatorial designs

Shortest paths on polymatroids and hypergraphic polytopes