About
Combinatorial Theory is a mathematician-run journal, owned by its Editorial Board.
It is dedicated to open access publishing with no fees (no APCs) for authors or readers.
Volume 5, Issue 1, 2025
Research Articles
Foundations of matroids Part 2: Further theory, examples, and computational methods
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
Mathematics Subject Classifications: 05B35, 12K99
Keywords: Matroid representation, cross ratio, inner Tutte group, foundations
- 1 supplemental ZIP
Projective two-weight sets of Denniston type
We construct two-weight sets in PG
Mathematics Subject Classifications: 51E20, 05B25
Keywords: Projective two-weight set, maximal arc
- 1 supplemental ZIP
On the number of squares in a finite word
Let
Mathematics Subject Classifications: 68R15, 68R10, 68R05
Keywords: Combinatorics on words, squares, repetition
- 1 supplemental ZIP
Tamari intervals and blossoming trees
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
- 1 supplemental ZIP
Chromatic functions, interval orders and increasing forests
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
- 1 supplemental ZIP
A generalization of perfectly clustering words and band bricks for certain gentle algebras
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
- 1 supplemental ZIP
Note on the number of antichains in generalizations of the boolean lattice
We give a short and self-contained argument that shows that, for any positive integers
Mathematics Subject Classifications: 05A16, 06A07
Keywords: Boolean lattice, antichains, entropy method
- 1 supplemental ZIP
Matchings in multipartite hypergraphs
A folklore result on matchings in graphs states that if
Mathematics Subject Classifications: 05C65, 05C70
Keywords: Matchings, Hypergraphs
- 1 supplemental ZIP
Continued fractions using a Laguerre digraph interpretation of the Foata-Zeilberger bijection and its variants
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
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
- 1 supplemental ZIP
Feynman symmetries of the Martin and invariants of regular graphs
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
Mathematics Subject Classifications: 81Q30, 05C70, 05C45
Keywords: Martin polynomial, transitions, spanning trees, point counts, Feynman integrals, integer sequences, permanent, Prüfer sequence
- 1 supplemental ZIP
Intransitive dice tournament is not quasirandom
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
Mathematics Subject Classifications: 60C05
Keywords: Intransitive dice, central limit theorem
- 1 supplemental ZIP
Noncrossing partitions of an annulus
The noncrossing partition poset associated to a Coxeter group
Mathematics Subject Classifications: 20F55, 05E16, 20F36
Keywords: Absolute order, affine Coxeter group, annulus, noncrossing partition
- 1 supplemental ZIP
Ehrhart quasi-polynomials and parallel translations
Given a rational polytope
Mathematics Subject Classifications: 52C07, 52C35
Keywords: Ehrhart quasi-polynomials, rational polytopes, toric arrangements, conic divisorial ideals
- 1 supplemental ZIP
Combinatorics of rectangulations: old and new bijections
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
- 1 supplemental ZIP
Eulerian polynomials for digraphs
Given an
Mathematics Subject Classifications: 05C20, 05A15
Keywords: Eulerian polynomials, alternating permutations, combinatorial reciprocity
- 1 supplemental ZIP
On the maximum degree of induced subgraphs of the Kneser graph
For integers
Frankl and Kupavskii, using different methods, have recently proven similar results under the hypothesis that
Mathematics Subject Classifications: 05D05
Keywords: Kneser, intersecting, sensitivity, Erdős-Ko-Rado type theorem
- 1 supplemental ZIP
Generalized polynomials and hyperplane functions in
For
Mathematics Subject Classifications: 05B20, 05B25, 05A10
Keywords: Hyperplanes, generalized polynomials, binomial coefficients
- 1 supplemental ZIP
Differential equations for the series of hypermaps with control on their full degree profile
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
Mathematics Subject Classifications: 05E05
Keywords: Hypermaps, differential equations, Jack characters
- 1 supplemental ZIP