Combinatorics
- [1] arXiv:2405.09635 [pdf, ps, html, other]
-
Title: On the number of $P$-free set systems for tree posets $P$Subjects: Combinatorics (math.CO)
We say a finite poset $P$ is a tree poset if its Hasse diagram is a tree. Let $k$ be the length of the largest chain contained in $P$. We show that when $P$ is a fixed tree poset, the number of $P$-free set systems in $2^{[n]}$ is $2^{(1+o(1))(k-1){n \choose \lfloor n/2\rfloor}}$. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm.
- [2] arXiv:2405.09656 [pdf, ps, html, other]
-
Title: Distance Critical GraphsComments: 14 pages, 4 figuresSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
In 1971, Graham and Pollak provided a formula for the determinant of the distance matrix of any tree on $n$ vertices. Yan and Yeh reproved this by exploiting the fact that pendant vertices can be deleted from trees without changing the remaining entries of the distance matrix. Considering failures of their argument to generalize invites the question: which graphs have the property that deleting any one vertex results in a change to some pairwise distance? We refer to such worst-case graphs as ``distance critical''. This work explores the structural properties of distance critical graphs, preservation of distance-criticality by products, and the nature of extremal distance critical graphs. We end with a few open questions.
- [3] arXiv:2405.09710 [pdf, ps, html, other]
-
Title: The lattice of submonoids of the uniform block permutations containing the symmetric groupComments: 15 pagesSubjects: Combinatorics (math.CO); Group Theory (math.GR)
We study the lattice of submonoids of the uniform block permutation monoid containing the symmetric group (which is its group of units). We prove that this lattice is distributive under union and intersection by relating the submonoids containing the symmetric group to downsets in a new partial order on integer partitions. Furthermore, we show that the sizes of the $\mathscr{J}$-classes of the uniform block permutation monoid are sums of squares of dimensions of irreducible modules of the monoid algebra.
- [4] arXiv:2405.09856 [pdf, ps, other]
-
Title: Generation of acyclic biological diagramsSubjects: Combinatorics (math.CO)
For the generation of acyclic biological diagrams, from a graph-theoretical perspective, we introduce the relative diagrams of cyclic permutations with ramphoid and keratoid vertices of degree 2, which correspond to Motzkin and Dyck words/paths. The relation between these two types of diagrams, defines the generation of the first via the permutations of the second, which may be of assistance in the study and treatment of several biological problems.
- [5] arXiv:2405.09991 [pdf, ps, html, other]
-
Title: A characterization of complex Hadamard matrices appearing in families of MUB tripletsComments: 17 pages, preprintSubjects: Combinatorics (math.CO)
It is shown that a normalized complex Hadamard matrix of order $6$ having three distinct columns, each containing at least one $-1$ entry necessarily belongs to the transposed Fourier family, or to the family of $2$-circulant complex Hadamard matrices. The proofs rely on solving polynomial system of equations by Gröbner basis techniques, and make use of a structure theorem concerning regular Hadamard matrices. As a consequence, members of these two families can be easily recognized in practice. In particular, one can identify complex Hadamard matrices appearing in known triplets of pairwise mutually unbiased bases in dimension $6$.
- [6] arXiv:2405.10088 [pdf, ps, html, other]
-
Title: Vertex-transitive graphs with small motion and transitive permutation groups with small minimal degreeSubjects: Combinatorics (math.CO)
The motion of a graph is the minimum number of vertices that are moved by a non-trivial automorphism. Equivalently, it can be defined as the minimal degree of its automorphism group (as a permutation group on the vertices). In this paper we develop some results on permutation groups (primitive and imprimitive) with small minimal degree. As a consequence of such results we classify vertex-transitive graphs whose motion is $4$ or a prime number.
- [7] arXiv:2405.10275 [pdf, ps, html, other]
-
Title: The Helly number of Hamming balls and related problemsSubjects: Combinatorics (math.CO)
We prove the following variant of Helly's classical theorem for Hamming balls with a bounded radius. For $n>t$ and any (finite or infinite) set $X$, if in a family of Hamming balls of radius $t$ in $X^n$, every subfamily of at most $2^{t+1}$ balls have a common point, so do all members of the family. This is tight for all $|X|>1$ and all $n>t$. The proof of the main result is based on a novel variant of the so-called dimension argument, which allows one to prove upper bounds that do not depend on the dimension of the ambient space. We also discuss several related questions and connections to problems and results in extremal finite set theory and graph theory.
New submissions for Friday, 17 May 2024 (showing 7 of 7 entries )
- [8] arXiv:2405.09748 (cross-list from q-bio.CB) [pdf, ps, html, other]
-
Title: A Mathematical Reconstruction of Endothelial Cell NetworksComments: 14 pages, 9 figuresSubjects: Cell Behavior (q-bio.CB); Combinatorics (math.CO); Group Theory (math.GR); Quantitative Methods (q-bio.QM)
Endothelial cells form the linchpin of vascular and lymphatic systems, creating intricate networks that are pivotal for angiogenesis, controlling vessel permeability, and maintaining tissue homeostasis. Despite their critical roles, there is no rigorous mathematical framework to represent the connectivity structure of endothelial networks. Here, we develop a pioneering mathematical formalism called $\pi$-graphs to model the multi-type junction connectivity of endothelial networks. We define $\pi$-graphs as abstract objects consisting of endothelial cells and their junction sets, and introduce the key notion of $\pi$-isomorphism that captures when two $\pi$-graphs have the same connectivity structure. We prove several propositions relating the $\pi$-graph representation to traditional graph-theoretic representations, showing that $\pi$-isomorphism implies isomorphism of the corresponding unnested endothelial graphs, but not vice versa. We also introduce a temporal dimension to the $\pi$-graph formalism and explore the evolution of topological invariants in spatial embeddings of $\pi$-graphs. Finally, we outline a topological framework to represent the spatial embedding of $\pi$-graphs into geometric spaces. The $\pi$-graph formalism provides a novel tool for quantitative analysis of endothelial network connectivity and its relation to function, with the potential to yield new insights into vascular physiology and pathophysiology.
- [9] arXiv:2405.09846 (cross-list from math.RT) [pdf, ps, html, other]
-
Title: Delta Operators on Almost Symmetric FunctionsComments: 20 pages. arXiv admin note: text overlap with arXiv:2307.05864Subjects: Representation Theory (math.RT); Combinatorics (math.CO)
We construct $\Delta$-operators $F[\Delta]$ on the space of almost symmetric functions $\mathscr{P}_{as}^{+}$. These operators extend the usual $\Delta$-operators on the space of symmetric functions $\Lambda \subset \mathscr{P}_{as}^{+}$ central to Macdonald theory. The $F[\Delta]$ operators are constructed as certain limits of symmetric functions in the Cherednik operators $Y_i$ and act diagonally on the stable-limit non-symmetric Macdonald functions $\widetilde{E}_{(\mu|\lambda)}(x_1,x_2,\ldots;q,t).$ Using properties of Ion-Wu limits, we are able to compute commutation relations for the $\Delta$-operators $F[\Delta]$ and many of the other operators on $\mathscr{P}_{as}^{+}$ introduced by Ion-Wu. Using these relations we show that there is an action of $\mathbb{B}_{q,t}^{\text{ext}}$ on almost symmetric functions which we show is isomorphic to the polynomial representation of $\mathbb{B}_{q,t}^{\text{ext}}$ constructed by González-Gorsky-Simental.
- [10] arXiv:2405.10161 (cross-list from hep-th) [pdf, ps, html, other]
-
Title: Torus knots and generalized Schr\"oder pathsComments: 33 pages, 7 figuresSubjects: High Energy Physics - Theory (hep-th); Combinatorics (math.CO); Quantum Algebra (math.QA)
We relate invariants of torus knots to the counts of a class of lattice paths, which we call generalized Schröder paths. We determine generating functions of such paths, located in a region determined by a type of a torus knot under consideration, and show that they encode colored HOMFLY-PT polynomials of this knot. The generators of uncolored HOMFLY-PT homology correspond to a basic set of such paths. Invoking the knots-quivers correspondence, we express generating functions of such paths as quiver generating series, and also relate them to quadruply-graded knot homology. Furthermore, we determine corresponding A-polynomials, which provide algebraic equations and recursion relations for generating functions of generalized Schröder paths. The lattice paths of our interest explicitly enumerate BPS states associated to knots via brane constructions.
- [11] arXiv:2405.10297 (cross-list from cs.CC) [pdf, ps, html, other]
-
Title: Low-Degree Polynomials Are Good ExtractorsComments: 42 pagesSubjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, (2) affine sources, and (3) local sources. We significantly generalize these results, and prove the following.
1. Low-degree polynomials extract from small families. We show that a random low-degree polynomial is a good low-error extractor for any small family of sources. In particular, we improve the positive result of Alrabiah, Chattopadhyay, Goodman, Li, and Ribeiro (ICALP 2022) for local sources, and give new results for polynomial sources and variety sources via a single unified approach.
2. Low-degree polynomials extract from sumset sources. We show that a random low-degree polynomial is a good extractor for sumset sources, which are the most general large family of sources (capturing independent sources, interleaved sources, small-space sources, and more). This extractor achieves polynomially small error, and its min-entropy requirement is tight up to a square.
Our results on sumset extractors imply new complexity separations for linear ROBPs, and the tools that go into its proof have further applications, as well. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between randomness extractors. Using the first new tool, we strengthen and generalize the extractor impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024). Using the second, we show the existence of sumset extractors for min-entropy $k=O(\log(n/\varepsilon))$, resolving an open problem of Chattopadhyay and Liao (STOC 2022).
Cross submissions for Friday, 17 May 2024 (showing 4 of 4 entries )
- [12] arXiv:2011.10458 (replaced) [pdf, ps, html, other]
-
Title: Spectra of Complex Unit HypergraphsSubjects: Combinatorics (math.CO); Spectral Theory (math.SP)
A complex unit hypergraph is a hypergraph where each vertex-edge incidence is given a complex unit label. We define the adjacency, incidence, Kirchoff Laplacian and normalized Laplacian of a complex unit hypergraph and study each of them. Eigenvalue bounds for the adjacency, Kirchoff Laplacian and normalized Laplacian are also found. Complex unit hypergraphs naturally generalize several hypergraphic structures such as oriented hypergraphs, where vertex-edge incidences are labelled as either $+1$ or $-1$, as well as ordinary hypergraphs. Complex unit hypergraphs also generalize their graphic analogues, which are complex unit gain graphs, signed graphs, and ordinary graphs.
- [13] arXiv:2111.05099 (replaced) [pdf, ps, other]
-
Title: Coalgebraic methods for Ramsey degrees of unary algebrasComments: arXiv admin note: substantial text overlap with arXiv:2104.01837Subjects: Combinatorics (math.CO); Category Theory (math.CT)
In this paper we are interested in the existence of small and big Ramsey degrees of classes of finite unary algebras in arbitrary (not necessarily finite) algebraic language $\Omega$. We think of unary algebras as $M$-sets where $M = \Omega^*$ is the free monoid of words over the alphabet $\Omega$ and show that for an arbitrary monoid $M$ (finite or infinite) the class of all finite $M$-sets has finite small Ramsey degrees. This immediately implies that the class of all finite $G$-sets, where $G$ is an arbitrary group (finite or infinite), has finite small Ramsey degrees, and that the class of all finite unary algebras over an arbitrary (finite or infinite) algebraic language $\Omega$ has finite small Ramsey degrees. This generalizes some Ramsey-type results of M.\ Sokić concerning finite unary algebras over finite languages and finite $G$-sets for finite groups~$G$. To do so we develop a completely new strategy that relies on the fact that right adjoints preserve the Ramsey property. We then treat $M$-sets as Eilenberg-Moore coalgebras for "half a comonad" and using pre-adjunctions transport the Ramsey properties we are interested in from the category of finite or countably infinite chains of order type $\omega$. Moreover, we show that finite objects have finite big Ramsey degrees in the corresponding cofree structures over countably many generators.
- [14] arXiv:2205.06686 (replaced) [pdf, ps, other]
-
Title: Pebble treesComments: 22 pages, 15 figures. Version 2: included a bijective explanation for the appearance of the Catalan numbers in the enumeration of maximal (1,1)-pebble treesSubjects: Combinatorics (math.CO)
A pebble tree is an ordered tree where each node receives some colored pebbles, in such a way that each unary node receives at least one pebble, and each subtree has either one more or as many leaves as pebbles of each color. We show that the contraction poset on pebble trees is isomorphic to the face poset of a convex polytope called pebble tree polytope. Beside providing intriguing generalizations of the classical permutahedra and associahedra, our motivation is that the faces of the pebble tree polytopes provide realizations as convex polytopes of all assocoipahedra constructed by K. Poirier and T. Tradler only as polytopal complexes.
- [15] arXiv:2212.11380 (replaced) [pdf, ps, html, other]
-
Title: Flips in Two-dimensional HypertriangulationsSubjects: Combinatorics (math.CO); Metric Geometry (math.MG)
We study flips in hypertriangulations of planar points sets. Here a level-$k$ hypertriangulation of $n$ points in the planes is a subdivision induced by the projection of a $k$-hypersimplex, which is the convex hull of the barycenters of the $(k-1)$-dimensional faces of the standard $(n-1)$-simplex. In particular, we introduce four types of flips and prove that the level-2 hypertriangulations are connected by these flips.
- [16] arXiv:2301.13632 (replaced) [pdf, ps, html, other]
-
Title: 2-tough 4-regular graphs with clawsSubjects: Combinatorics (math.CO)
We show that there are 2-tough 4-regular graphs with claws
- [17] arXiv:2310.04634 (replaced) [pdf, ps, html, other]
-
Title: A Polynomial Upper Bound for Poset SaturationComments: 7 pages, 2 figuresSubjects: Combinatorics (math.CO)
Given a finite poset $\mathcal P$, we say that a family $\mathcal F$ of subsets of $[n]$ is $\mathcal P$-saturated if $\mathcal F$ does not contain an induced copy of $\mathcal P$, but adding any other set to $\mathcal F$ creates an induced copy of $\mathcal P$. The induced saturation number of $\mathcal P$, denoted by $\text{sat}^*(n,\mathcal P)$, is the size of the smallest $\mathcal P$-saturated family with ground set $[n]$. In this paper we prove that the saturation number for any given poset grows at worst polynomially. More precisely, we show that $\text{sat}^*(n, \mathcal P)=O(n^c)$, where $c\leq|\mathcal{P}|^2/4+1$ is a constant depending on $\mathcal P$ only. We obtain this result by bounding the VC-dimension of our family.
- [18] arXiv:2403.06589 (replaced) [pdf, ps, html, other]
-
Title: Analysis of Regular Sequences: Summatory Functions and Divide-and-Conquer RecurrencesSubjects: Combinatorics (math.CO)
In the asymptotic analysis of regular sequences as defined by Allouche and Shallit, it is usually advisable to study their summatory function because the original sequence has a too fluctuating behaviour. It might be that the process of taking the summatory function has to be repeated if the sequence is fluctuating too much. In this paper we show that for all regular sequences except for some degenerate cases, repeating this process finitely many times leads to a ``nice'' asymptotic expansion containing periodic fluctuations whose Fourier coefficients can be computed using the results on the asymptotics of the summatory function of regular sequences by the first two authors of this paper.
In a recent paper, Hwang, Janson, and Tsai perform a thorough investigation of divide-and-conquer recurrences. These can be seen as $2$-regular sequences. By considering them as the summatory function of their forward difference, the results on the asymptotics of the summatory function of regular sequences become applicable. We thoroughly investigate the case of a polynomial toll function. - [19] arXiv:2403.12195 (replaced) [pdf, ps, other]
-
Title: PackIt! Gamified Rectangle PackingComments: Accepted at FUN with Algorithms 2024Subjects: Combinatorics (math.CO); Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT)
We present and analyze PackIt!, a turn-based game consisting of packing rectangles on an $n \times n$ grid. PackIt! can be easily played on paper, either as a competitive two-player game or in \emph{solitaire} fashion. On the $t$-th turn, a rectangle of area $t$ or $t+1$ must be placed in the grid. In the two-player format of PackIt! whichever player places a rectangle last wins, whereas the goal in the solitaire variant is to perfectly pack the $n \times n$ grid. We analyze conditions for the existence of a perfect packing over $n \times n$, then present an automated reasoning approach that allows finding perfect games of PackIt! up to $n = 50$ which includes a novel SAT-encoding technique of independent interest, and conclude by proving an NP-hardness result.
- [20] arXiv:2404.14375 (replaced) [pdf, ps, html, other]
-
Title: Two classes of Hadamard matrices of Goethals-Seidel typeComments: 10 pagesSubjects: Combinatorics (math.CO)
We introduce two classes of Hadamard matrices of Goethals-Seidel type and construct many matrices in these classes.
- [21] arXiv:2405.02092 (replaced) [pdf, ps, html, other]
-
Title: Geometric realizations of the $s$-weak order and its lattice quotientsComments: 50 pages, 33 figures. Version 2: minor corrections in particular in a few pictures, added Remark 98Subjects: Combinatorics (math.CO)
For an $n$-tuple $s$ of non-negative integers, the $s$-weak order is a lattice structure on $s$-trees, generalizing the weak order on permutations. We first describe the join irreducible elements, the canonical join representations, and the forcing order of the $s$-weak order in terms of combinatorial objects, generalizing the arcs, the non-crossing arc diagrams, and the subarc order for the weak order. We then extend the theory of shards and shard polytopes to construct geometric realizations of the $s$-weak order and all its lattice quotients as polyhedral complexes, generalizing the quotient fans and quotientopes of the weak order.
- [22] arXiv:2405.06091 (replaced) [pdf, ps, html, other]
-
Title: Limit points of (signless) Laplacian spectral radii of linear treesSubjects: Combinatorics (math.CO); Spectral Theory (math.SP)
We study limit points of the spectral radii of Laplacian matrices of graphs. We adapted the method used by J. B. Shearer in 1989, devised to prove the density of adjacency limit points of caterpillars, to Laplacian limit points. We show that this fails, in the sense that there is an interval for which the method produces no limit points. Then we generalize the method to Laplacian limit points of linear trees and prove that it generates a larger set of limit points. The results of this manuscript may provide important tools for proving the density of Laplacian limit points in $[4.38+, \infty)$.
- [23] arXiv:2405.07612 (replaced) [pdf, ps, html, other]
-
Title: Expansions of the Potts model partition function along deletions and contractionsComments: 12 pages, 2 figuresSubjects: Combinatorics (math.CO)
We establish two expansions of the Potts model partition function of a graph. One is along the deletions of a graph, a rewritten formula given in Biggs (1977). The other is along the contractions of a graph. Then, we specialize the partition function to the chromatic or flow polynomial by the Möbius inversion formula, and prove two known equations of the two polynomials. One expresses the chromatic polynomial as a weighted sum of flow polynomials of deletions, the other expresses the flow polynomial as a weighted sum of chromatic polynomials of contractions. The proof of the former by Biggs formula is due to Bychkov et al. (2021). The two expressions are considered to be dual in the sense of their forms, and transfer to each other with plane duality. This relation also holds in our expansions of the Potts model partition function. We clarify this duality by using matroid duality. Partition functions can be extended to matroids, and the two expansions can also be extended. The two expansions transfer to each other with matroid duality, so in addition to an elementary combinatorial proof of the two, we give another proof by the "duality" relation between them.
- [24] arXiv:2405.08781 (replaced) [pdf, ps, html, other]
-
Title: To graph total coloring via efficient dominating setsComments: 7 pages, 2 figuresSubjects: Combinatorics (math.CO)
A totally efficient coloring of a regular graph with color set formed by one unit more than its degree is a total coloring in which each vertex color class is an efficient dominating set, that is a perfect code. We find that the 3-cube graph has a totally efficient coloring and conjecture that this is the only existing case of a totally effective coloring. We also deal with a related problem exemplified by star transposition graphs and related graphs, leading to edge-girth colorings on their prism graphs.
- [25] arXiv:2405.09429 (replaced) [pdf, ps, other]
-
Title: Generalizations of cyclic polytopesComments: 10 pagesSubjects: Combinatorics (math.CO); Metric Geometry (math.MG)
Cyclic polytopes have been studied since at least the early last century by Caratheodory and others.A generalization is a construction of a class of polytopes such that the polytopes have some of their properties.The best known example is the class of neighbourly polytopes. Cyclic polytopes have explicit facet structures, important properties and applications in different branches of mathematics. In the past few decades, generalizations of their combinatorial properties have yielded new classes of polytopes that also have explicit facet structures and useful applications. We present an overview of these generalizations along with some applications of the resultant polytopes, and some possible approaches to other generalizations.
- [26] arXiv:2402.02312 (replaced) [pdf, ps, html, other]
-
Title: Higher Congruences in Character TablesComments: 12 pages. Comments welcome!Subjects: Representation Theory (math.RT); Combinatorics (math.CO); Group Theory (math.GR)
Motivated by recent work of Peluse and Soundararajan on divisibility properties of the entries of the character tables of symmetric groups, we investigate the question: For a finite group G, when are two columns of the character table of G congruent to one another modulo a power of a prime?