Combinatorial Theory

In this sequel to "Foundations of matroids - Part 1," we establish several presentations of the foundation of a matroid in terms of small building blocks. For example, we show that the foundation of a matroid \(M\) is the colimit of the foundations of all embedded minors of \(M\) isomorphic to one of the matroids \(U^2_4\), \(U^2_5\), \(U^3_5\), \(C_5\), \(C_5^\ast\), \(U^2_4\oplus U^1_2\), \(F_7\), \(F_7^\ast\), and we show that this list is minimal. We establish similar minimal lists of building blocks for the classes of 2-connected and 3-connected matroids. We also establish a presentation for the foundation of a matroid in terms of its lattice of flats. Each of these presentations provides a useful method to compute the foundation of certain matroids, as we illustrate with a number of concrete examples. Combining these techniques with other results in the literature, we are able to compute the foundations of several interesting classes of matroids, including whirls, rank-2 uniform matroids, and projective geometries. In an appendix, we catalogue various `small' pastures which occur as foundations of matroids, most of which were found with the assistance of a computer, and we discuss some of their interesting properties.

Mathematics Subject Classifications: 05B35, 12K99

Keywords: Matroid representation, cross ratio, inner Tutte group, foundations

We construct two-weight sets in PG\((3n-1,q)\), \(n\geq2\) with the same weights as those that would arise from the blow-up of a maximal \(q\)-arc in PG\((2,q^n)\). The construction is of particular interest when \(q\) is odd, as it is well known that no maximal arcs in PG\((2,q^n)\) exist in that case.

Mathematics Subject Classifications: 51E20, 05B25

Keywords: Projective two-weight set, maximal arc

Let \(u\) be a nonempty finite word, a square is a word of the form \(uu\). In this paper, we prove that for a given finite word \(w\), the number of distinct square factors of \(w\) is bounded by \(|w|-|\operatorname{Alph}(w)|\), where \(|w|\) denotes the length of \(w\) and \(|\operatorname{Alph}(w)|\) denotes the number of distinct letters in \(w\). This result answers positively a conjecture stated by Fraenkel and Simpson in 1998 and the \(d\)-step conjecture stated by Deza, Franek and Jiang in 2011.

Mathematics Subject Classifications: 68R15, 68R10, 68R05

Keywords: Combinatorics on words, squares, repetition

We introduce a simple bijection between Tamari intervals and the blossoming trees (Poulalhon and Schaeffer, 2006) encoding planar triangulations, using a new meandering representation of such trees. Its specializations to the families of synchronized, Kreweras, new/modern, and infinitely modern intervals give a combinatorial proof of the counting formula for each family. Compared to (Bernardi and Bonichon, 2009), our bijection behaves well with the duality of Tamari intervals, also enabling the counting of self-dual intervals.

Mathematics Subject Classifications: 05A15, 05A19

Keywords: Tamari intervals, blossoming trees, enumeration, duality

The chromatic quasisymmetric functions (csf) of Shareshian and Wachs associated to unit interval orders have attracted a lot of interest since their introduction in 2016, both in combinatorics and geometry, because of their relation to the famous Stanley-Stembridge conjecture (1993) and to the topology of Hessenberg varieties, respectively.

In the present work we study the csf associated to the larger class of interval orders with no restriction on the length of the intervals. Inspired by an article of Abreu and Nigro, we show that these csf are weighted sums of certain quasisymmetric functions associated to the increasing spanning forests of the associated incomparability graphs. Furthermore, we define quasisymmetric functions that include the unicellular LLT symmetric functions and generalize an identity due to Carlsson and Mellit. Finally we conjecture a formula giving their expansion in the type 1 power sum quasisymmetric functions which extends a formula proved by Athanasiadis.

Mathematics Subject Classifications: 05E05

Keywords: Chromatic function, interval order graph, quasisymmetric functions

We generalize the perfectly clustering words of Simpson and Puglisi and relate them to band bricks over certain gentle algebras. This allows us to prove a generalization of a conjecture by the second author on perfectly clustering words.

Mathematics Subject Classifications: 16G20, 68R15

Keywords: Perfectly clustering words, gentle algebras, bands, bricks

We give a short and self-contained argument that shows that, for any positive integers \(t\) and \(n\) with \(t =O\Bigl(\frac{n}{\log n}\Bigr)\), the number \(\alpha([t]^n)\) of antichains of the poset \([t]^n\) is at most \[{\exp_2\Bigl[\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\Bigr]}\,,\] where \(N(t,n)\) is the size of a largest level of \([t]^n\). This, in particular, says that if \({t \!\ll\! n/\log^3 \! n}\) as \(n \rightarrow \infty\), then \(\log\alpha([t]^n)=(1+o(1))N(t,n)\), giving a (partially) positive answer to a question of Moshkovitz and Shapira for \(t, n\) in this range. Particularly for \(t=3\), we prove a better upper bound: \[\log\alpha([3]^n)\le(1+4\log 3/n)N(3,n),\] which is the best known upper bound on the number of antichains of \([3]^n\).

Mathematics Subject Classifications: 05A16, 06A07

Keywords: Boolean lattice, antichains, entropy method

A folklore result on matchings in graphs states that if \(G\) is a bipartite graph whose vertex classes \(A\) and \(B\) each have size \(n\), with \(\deg(u) \geq a\) for every \(u \in A\) and \(\deg(v) \geq b\) for every \(v \in B\), then \(G\) admits a matching of size \(\min\{n, a+b\}\). In this paper we establish the analogous result for large \(k\)-partite \(k\)-uniform hypergraphs, answering a question of Han, Zang and Zhao, who previously demonstrated that this result holds under the additional condition that the minimum degrees into at least two of the vertex classes are large. A key part of our proof is a study of rainbow matchings under a combination of degree and multiplicity conditions, which may be of independent interest.

Mathematics Subject Classifications: 05C65, 05C70

Keywords: Matchings, Hypergraphs

In the combinatorial theory of continued fractions, the Foata-Zeilberger bijection and its variants have been extensively used to derive various continued fractions enumerating several (sometimes infinitely many) simultaneous statistics on permutations (combinatorial model for factorials) and D-permutations (combinatorial model for Genocchi and median Genocchi numbers). A Laguerre digraph is a digraph in which each vertex has in- and out-degrees \(0\) or \(1\). In this paper, we interpret the Foata-Zeilberger bijection in terms of Laguerre digraphs, which enables us to count cycles in permutations. Using this interpretation, we obtain Jacobi-type continued fractions for multivariate polynomials enumerating permutations, and also Thron-type and Stieltjes-type continued fractions for multivariate polynomials enumerating D-permutations, in both cases including the counting of cycles. This enables us to prove some conjectured continued fractions due to Sokal and Zeng (2022 Advances in Applied Mathematics) in the case of permutations, and Randrianarivony and Zeng (1996 Electronic Journal of Combinatorics) and Deb and Sokal (2024 Advances in Applied Mathematics) in the case of D-permutations.

Mathematics Subject Classifications: 05A19 (Primary); 05A05, 05A10, 05A15, 05A30, 11B68, 30B70 (Secondary).

Keywords: Permutations, D-permutations, continued fraction, Foata-Zeilberger bijection, S-fraction, J-fraction, T-fraction, Dyck path, almost-Dyck path, Motzkin path, Schröder path, Laguerre digraphs

For every regular graph, we define a sequence of integers, using the recursion of the Martin polynomial. We prove that this sequence counts spanning tree partitions and thus constitutes the diagonal coefficients of powers of the Kirchhoff polynomial. We also prove that this sequence respects all known symmetries of Feynman period integrals in quantum field theory. We show that other quantities with this property, the \(c_2\) invariant and the extended graph permanent, are essentially determined by our new sequence. This proves the completion conjecture for the \(c_2\) invariant at all primes, and also that it is fixed under twists. We conjecture that our invariant is perfect: Two Feynman periods are equal, if and only if, their Martin sequences are equal.

Mathematics Subject Classifications: 81Q30, 05C70, 05C45

Keywords: Martin polynomial, transitions, spanning trees, point counts, Feynman integrals, integer sequences, permanent, Prüfer sequence

We settle a version of the conjecture about intransitive dice posed by Conrey, Gabbard, Grant, Liu and Morrison in 2016 and Polymath in 2017. We consider generalized dice with \(n\) faces and we say that a die \(A\) beats \(B\) if a random face of \(A\) is more likely to show a higher number than an independently chosen random face of \(B\). We study random dice with faces drawn iid from the uniform distribution on \([0,1]\) and conditioned on the sum of the faces equal to \(n/2\). Considering the "beats" relation for three such random dice, Polymath showed that each of eight possible tournaments between them is asymptotically equally likely. In particular, three dice form an intransitive cycle with probability converging to \(1/4\). In this paper we prove that for four random dice not all tournaments are equally likely and the probability of a transitive tournament is strictly higher than \(3/8\).

Mathematics Subject Classifications: 60C05

Keywords: Intransitive dice, central limit theorem

The noncrossing partition poset associated to a Coxeter group \(W\) and Coxeter element \(c\) is the interval \([1,c]_T\) in the absolute order on \(W\). We construct a new model of noncrossing partititions for \(W\) of classical affine type, using planar diagrams (affine types \(\widetilde{A}\) and \(\widetilde{C}\) in this paper and affine types \(\widetilde{D}\) and \(\widetilde{B}\) in the sequel). The model in type \(\widetilde{A}\) consists of noncrossing partitions of an annulus. In type \(\widetilde{C}\), the model consists of symmetric noncrossing partitions of an annulus or noncrossing partitions of a disk with two orbifold points. Following the lead of McCammond and Sulway, we complete \([1,c]_T\) to a lattice by factoring the translations in \([1,c]_T\), but the combinatorics of the planar diagrams leads us to make different choices about how to factor.

Mathematics Subject Classifications: 20F55, 05E16, 20F36

Keywords: Absolute order, affine Coxeter group, annulus, noncrossing partition

Given a rational polytope \(P \subset \mathbb R^d\), the numerical function counting lattice points in the integral dilations of \(P\) is known to become a quasi-polynomial, called the Ehrhart quasi-polynomial \(\operatorname{ehr}_P\) of \(P\). In this paper we study the following problem: Given a rational \(d\)-polytope \(P \subset \mathbb R^d\), is there a nice way to know Ehrhart quasi-polynomials of translated polytopes \(P+  v\) for all \( v \in \mathbb Q^d\)? We provide a way to compute such Ehrhart quasi-polynomials using a certain toric arrangement and lattice point counting functions of translated cones of \(P\). This method allows us to visualize how constituent polynomials of \(\operatorname{ehr}_{P+ v}\) change in the torus \(\mathbb R^d/\mathbb Z^d\). We also prove that information of \(\operatorname{ehr}_{P+ v}\) for all \( v \in \mathbb Q^d\) determines the rational \(d\)-polytope \(P \subset \mathbb R^d\) up to translations by integer vectors, and characterize all rational \(d\)-polytopes \(P \subset \mathbb R^d\) such that \(\operatorname{ehr}_{P+ v}\) is symmetric for all \( v \in \mathbb Q^d\).Mathematics Subject Classifications: 52C07, 52C35Keywords: Ehrhart quasi-polynomials, rational polytopes, toric arrangements, conic divisorial ideals

A rectangulation is a decomposition of a rectangle into finitely many rectangles. Via natural equivalence relations, rectangulations can be seen as combinatorial objects with a rich structure, with links to lattice congruences, flip graphs, polytopes, lattice paths, Hopf algebras, etc. In this paper, we first revisit the structure of the respective equivalence classes: weak rectangulations that preserve rectangle-segment adjacencies, and strong rectangulations that preserve rectangle-rectangle adjacencies. We thoroughly investigate posets defined by adjacency in rectangulations of both kinds, and unify and simplify known bijections between rectangulations and permutation classes. This yields a uniform treatment of mappings between permutations and rectangulations that unifies the results from earlier contributions, and emphasizes parallels and differences between the weak and the strong cases. Then, we consider guillotine rectangulations, and prove that they can be characterized -- under all known mappings between permutations and rectangulations -- by avoidance of two mesh patterns that correspond to windmills in rectangulations. This yields new permutation classes in bijection with weak guillotine rectangulations, and the first known permutation class in bijection with strong guillotine rectangulations. Finally, we address enumerative issues and prove asymptotic bounds for several families of strong rectangulations.

Mathematics Subject Classifications: 05A05, 05A15, 05A16, 05C10, 06A07, 06B10

Keywords: Rectangulations, combinatorial enumeration, generating functions, asymptotic enumeration, posets, permutation patterns

Given an \(n\)-vertex digraph \(D\) and a labeling \(\sigma:V(D)\to [n]\), we say that an arc \(u\to v\) of \(D\) is a descent of \(\sigma\) if \(\sigma(u)›\sigma(v)\). Foata and Zeilberger introduced a generating function \(A_D(t)\) for labelings of \(D\) weighted by descents, which simultaneously generalizes both Eulerian polynomials and Mahonian polynomials. Motivated in part by work of Kalai, we prove three results related to \(-1\) evaluations of \(A_D(t)\): we give combinatorial interpretations of \(|A_D(-1)|\) for a large class of digraphs (such as digraphs whose underlying graph is bipartite), we determine the maximum and minimum possible values of \(|A_D(-1)|\) obtained by directed trees, and we obtain bounds on the mulitiplicity of \(-1\) as a root of \(A_D(t)\).

Mathematics Subject Classifications: 05C20, 05A15

Keywords: Eulerian polynomials, alternating permutations, combinatorial reciprocity

For integers \(n \geq k \geq 1\), the Kneser graph \(K(n, k)\) is the graph with vertex-set consisting of all the \(k\)-element subsets of \(\{1,2,\ldots,n\}\), where two \(k\)-element sets are adjacent in \(K(n,k)\) if they are disjoint. We show that if \((n,k,s) \in \mathbb{N}^3\) with \(n › 10000 k s^5\) and \(\mathcal F\) is set of vertices of \(K(n,k)\) of size larger than \[\{A \subset \{1,2,\ldots,n\}: |A|=k, A \cap \{1,2,\ldots,s\} \neq \varnothing\},\] then the subgraph of \(K(n,k)\) induced by \(\mathcal F\) has maximum degree at least \[ \left(1 - O\left(\sqrt{s^3 k/n}\right)\right)\frac{s}{s+1} \cdot {n-k \choose k} \cdot \frac{\left|{\mathcal F}\right|}{\binom{n}{k}}.\] This is sharp up to the behaviour of the error term \(O(\sqrt{s^3 k/n})\). In particular, if the triple of integers \((n, k, s)\) satisfies the condition above, then the minimum maximum degree does not increase `continuously' with \(\left|{\mathcal F}\right|\). Instead, it has \(s\) jumps, one at each time when \(\left|{\mathcal F}\right|\) becomes just larger than the union of \(i\) stars, for \(i = 1, 2, \ldots, s\). An appealing special case of the above result is that if \(\mathcal{F}\) is a family of \(k\)-element subsets of \(\{1,2,\ldots,n\}\) with \(|\mathcal{F}| = {n-1 \choose k-1}+1\), then there exists \(A \in \mathcal{F}\) such that \(\mathcal{F}\) is disjoint from at least \[\left(1/2-O\left(\sqrt{k/n}\right)\right){n-k-1 \choose k-1}\] of the other sets in \(\mathcal{F}\); we give both a random and a deterministic construction showing that this is asymptotically sharp if \(k=o(n)\). In addition, it solves (up to a constant multiplicative factor) a problem of Gerbner, Lemons, Palmer, Patkós and Szécsi.

Frankl and Kupavskii, using different methods, have recently proven similar results under the hypothesis that \(n\) is at least a quadratic in \(k\).

Mathematics Subject Classifications: 05D05

Keywords: Kneser, intersecting, sensitivity, Erdős-Ko-Rado type theorem

For \(p\) prime, let \(\mathcal{H}^n\) be the linear span of indicator functions of hyperplanes in \((\mathbb{Z}/p^k\mathbb{Z})^n\). We establish new upper bounds on the dimension of \(\mathcal{H}^n\) over \(\mathbb{Z}/p\mathbb{Z}\), or equivalently, on the rank of point-hyperplane incidence matrices in \((\mathbb{Z}/p^k\mathbb{Z})^n\) over \(\mathbb{Z}/p\mathbb{Z}\). Our proof is based on a variant of the polynomial method using binomial coefficients in \(\mathbb{Z}/p^k\mathbb{Z}\) as generalized polynomials. We also establish additional necessary conditions for a function on \((\mathbb{Z}/p^k\mathbb{Z})^n\) to be an element of \(\mathcal{H}^n\).

Mathematics Subject Classifications: 05B20, 05B25, 05A10

Keywords: Hyperplanes, generalized polynomials, binomial coefficients

We consider the generating series of oriented and non-oriented hypermaps with controlled degrees of vertices, hyperedges and faces. It is well known that these series have natural expansions in terms of Schur and Zonal symmetric functions, and with some particular specializations, they satisfy the celebrated KP and BKP equations. We prove that the full generating series of hypermaps satisfy a family of differential equations. We give a first proof which works for an \(\alpha\) deformation of these series related to Jack polynomials. This proof is based on a recent construction formula for Jack characters using differential operators. We also provide a combinatorial proof for the orientable case. Our approach also applies to the series of \(k\)-constellations with control of the degrees of vertices of all colors. In other words, we obtain an equation for the generating function of Hurwitz numbers (and their \(\alpha\)-deformations) with control of full ramification profiles above an arbitrary number of points. Such equations are new even in the orientable case.

Mathematics Subject Classifications: 05E05

Keywords: Hypermaps, differential equations, Jack characters