Combinatorics · Cross-listed from math.PR
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Monday 14 September
Let a random permutation $W\in S_n$ represent the order of $n$ distinct cards. After each guess, the player learns the actual card, and the objective is to maximize the expected total number of correct guesses. Diaconis, Fulman, and Holmes conjectured that, after a single uniform, unbiased shelf shuffle, the direction-tracking strategy is optimal: first guess the smallest card, and thereafter choose the nearest remaining card in the direction of the most recent rise or fall. We prove a more general theorem: if \[ \mathbb P(W=w)=\frac{f(v(w))}{\sum_{\sigma\in S_n}f(v(\sigma))}, \] where $v(w)$ is the number of interior valleys of the permutation, $f$ is nonnegative and nonincreasing, and the denominator is positive, then direction tracking maximizes the conditional probability of correctly guessing the next card after every history of positive probability. It therefore maximizes the expected total number of correct guesses among all complete-feedback strategies. Here an interior valley is a position $2\le i\le n-1$ satisfying $w_{i-1}>w_i<w_{i+1}$. Combined with the known shelf-shuffling probability formula, this theorem proves the conjecture for every deck size and number of shelves. The key to the proof is a swap of adjacent remaining values that preserves the revealed prefix: starting from the preferred candidate, the swap leaves the valley count unchanged or increases it by one, thereby turning monotonicity of the weights into a conditional probability ordering after every history.
Combinatorics · Cross-listed from math.PR
Extremal expectations in card guessing with partial feedback: proofs of two conjectures of Diaconis-Graham-Spiro
We study the minimum and maximum expected scores over all adaptive strategies in sequential card guessing with yes/no feedback. A deck contains $n$ labels, each appearing $m$ times, and is shuffled uniformly. The cards are guessed one at a time, and after each guess the player is told only whether it was correct. Always guessing the same label gives exactly $m$ points. How far can the expected score depart from $m$ if all previous feedback is used either to seek or to avoid correct guesses? Diaconis, Graham, and Spiro conjectured that the minimum expectation is $m-o(m)$ as $m\to\infty$ with $n$ sufficiently large in terms of $m$, and that, for each fixed $m$, the limit superior of the maximum expectation as $n\to\infty$ is at most $(e-1)m$. Writing these extrema as $P^-_{m,n}$ and $P^+_{m,n}$, we prove \[ 0\le m-P^-_{m,n}\le3m^{3/4} \qquad(n\ge m\ge1), \] and the finite-parameter bound \[ \frac{P^+_{m,n}}m\le\sum_{k=1}^{n}\frac1{k!}<e-1 \] for all positive integers $m,n$. The first bound gives a first-order asymptotic uniform in $n\ge m$; the universal constant $e-1$ in the second cannot be reduced. Thus both conjectures follow. The lower bound combines a switching comparison for restricted permutations with martingale second-moment estimates. For the upper bound, we represent the repeated cards as a random interleaving of independent decks of distinct cards and prove that the optimal expectation is additive when the component-deck labels are revealed.
Read the full abstract
Combinatorics
Close Divisors of Typical Integers:The Ford–Green–Koukoulopoulos Conjecture
For an integer $k\geq2$, let $\alpha_k$ be the supremum of the real numbers $a$ for which almost every integer $n\geq2$ has divisors $d_1<\cdots<d_k\mid n$ satisfying $d_k\leq d_1\bigl(1+(\log n)^{-a}\bigr).$ Let $\mathcal A\subseteq\N$ be the logarithmic random set in which the events $m\in\mathcal A$ are mutually independent and $\Pp(m\in\mathcal A)=1/m$ for every $m\geq1$. For a finite set $B\subseteq\N$, write $\Sigma(B)=\sum_{b\in B}b, \Sigma(\varnothing)=0$ and $m(B)=\max_{s\in\Z}\#\{C\subseteq B\mid\Sigma(C)=s\},$ and define \[ \beta_k=\sup\left\{c<1\,\middle|\,\lim_{D\to\infty}\Pp\bigl(m(\mathcal A\cap(D^c,D])\geq k\bigr)=1\right\}. \] Ford, Green and Koukoulopoulos proved $\alpha_k\geq\beta_k/(1-\beta_k)$ and conjectured that equality holds for every fixed $k\geq2$. In this paper, we confirm their conjecture. More precisely, for every fixed $a>\beta_k/(1-\beta_k)$, almost every integer $n\geq2$ has no divisors $d_1<\cdots<d_k\mid n$ satisfying $d_k\leq d_1\bigl(1+(\log n)^{-a}\bigr)$. We also correct local errors in their paper [Invent. Math. 232 (2023), 1027–1160], concerning the finite-subflag reduction, the residual-sum count, the moment estimate and the lattice adjustment. These corrections preserve the entropy-threshold comparison used in our proof.
Read the full abstract
Combinatorics · Cross-listed from math.SP
An inverse problem on eigenfunction triple products
On a connected closed smooth Riemannian manifold, the algebraic structure of the Laplace eigenfunctions, as described by eigenfunction triple products, uniquely determines the geometry. We refine this correspondence by introducing the notion of an $N$-product eigenbasis, which consists of eigenfunctions whose pairwise products may be written as linear combinations of at most $N$ basis elements. We prove that a manifold admits a $2$-product eigenbasis if and only if it is a flat torus. We also prove an analogous result for Laplace eigenvectors of bounded-degree graphs.
Read the full abstract
Combinatorics
Polynomial Length Cycles In Tough Graphs
We prove that every $n$-vertex $15$-tough graph contains a cycle of length $\Omega(n^{1/20})$.
Combinatorics · Cross-listed from math.NT
Elementary proofs of congruences modulo 5 for overpartitions with restricted odd differences
In 2015, Bringmann, Dousse, Lovejoy, and Mahlburg defined the function $\overline{t}(n)$ to be the number of overpartitions of weight $n$ where (i) the difference between two successive parts may be odd only if the larger part is overlined and (ii) if the smallest part is odd then it is overlined. In their work, they proved that $\overline{t}(n)$ satisfies an elegant congruence modulo 3. Since then, a number of authors have studied arithmetic properties satisfied by $\overline{t}(n)$. In particular, in 2023, Hanson and Smith utilized the theory of modular forms to prove the following two congruences modulo 5: For all $n\geq 0$, \begin{align*} \overline{t}(80n+40)\equiv \overline{t}(80n+60)\equiv 0 \pmod{5}. \end{align*} Our goal in this work is to provide a truly elementary proof of this pair of congruences.
Read the full abstract
Combinatorics · Cross-listed from cs.DM
Ramsey Obstructions to Disambiguation
A partial matrix has entries in $\{0,1,\star\}$, and a disambiguation replaces each $\star$ by $0$ or $1$. We construct partial matrices whose fully specified submatrices satisfy strong restrictions, yet every disambiguation contains every binary matrix of a prescribed size. Our first result answers a question of Alon, Hanneke, Holzman and Moran on the disambiguation of linear classifiers with margin. For $0<\varepsilon<\pi/2$, let $M_\varepsilon^d$ be the partial matrix indexed by points of the unit sphere $\mathbb S^d$, with entry $0$ for pairs at spherical distance at most $\varepsilon$, $1$ for pairs at distance at least $\pi-\varepsilon$, and $\star$ otherwise. Although these matrices have VC-dimension bounded independently of $d$, we prove that every disambiguation contains every binary $k\times k$ matrix once $d$ is sufficiently large. This also yields a partial concept class of Littlestone dimension $1$ with no disambiguation of finite VC-dimension. We also construct, for every $k$, a finite partial matrix whose fully specified $2\times2$ submatrices are all constant, while every disambiguation contains every binary $k\times k$ matrix. A symmetric analogue holds for partial graphs: for every $k$, there exists a partial graph of VC-dimension at most $1$ whose fully specified induced subgraphs are all cliques or stable sets, yet every disambiguation contains every $k$-vertex graph as an induced subgraph. A disambiguation can be viewed as a $2$-coloring of the unspecified entries, making Ramsey theory a natural framework for forcing prescribed patterns. Our proofs draw on two recent Ramsey theorems: the geometric argument uses Pálvölgyi's Dense Block theorem, while the combinatorial constructions rely on the girth Ramsey theorem of Reiher and Rödl, a suitable strengthening of the induced Ramsey theorem.
Read the full abstract
Combinatorics
Independent domination in central graphs
Let $G$ be a graph with vertex set $V(G)$. A set $I\subseteq V(G)$ is an independent dominating set of $G$ if no two vertices in $I$ are adjacent and every vertex in $V(G)\setminus I$ is adjacent to at least one vertex in $I$. The independent domination number of $G$ is the minimum cardinality among all independent dominating sets of $G$. The aim of this article is to obtain tight bounds and closed formulas for the independent domination number of central graphs. The results are expressed in terms of parameters of the original graph from which the central graph is constructed.
Read the full abstract
Combinatorics · Cross-listed from math.GR
Matroids and isomorphism problems for Bestvina-Brady groups
We propose a factorization of the graph isomorphism problem for Bestvina-Brady groups (BBGs) through matroid theory. In particular, we show that finitely presented BBGs depend on their defining graphs only through their cycle matroids. On the other hand, we construct graphs of arbitrarily high connectivity such that they have non-isomorphic cycle matroids but their BBGs are isomorphic. To do so, we prove that if a graph admits a tree clique-spanner, then the Dicks-Leary presentation of its BBG can be explicitly simplified to a right-angled Artin group presentation. In particular, we show that BBGs defined by dually chordal graphs are right-angled Artin groups.
Read the full abstract
Combinatorics
A Cheeger Inequality for Hypergraphs and Its Applications
Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon–Boppana bound.
Read the full abstract
Combinatorics · Cross-listed from math.PR
On symmetric partition lattices and probability interactions
The Möbius function of a partition lattice can be used to define interactions of probability measures. We call a lower set a symmetric partition lattice when it is invariant under permutations of the variables. We characterize these lattices through integer partitions and obtain a recursion for their Möbius coefficients at the top element. By constructing probability measures whose partition products are linearly independent, we show that permutation invariance of an interaction is equivalent to that of its underlying lower set, provided the coordinate spaces are sufficiently large. We also characterize the partitions on a lower set that force an interaction to vanish for every probability measure, and construct indecomposable distributions with zero interaction. We define the order of a symmetric partition lattice and relate it to vanishing marginals. We study generalized Lancaster and define the Streitberg and size-limited partition lattices, obtaining explicit Möbius coefficients for them. Finally, we express interaction equations in terms of characteristic functions. For Gaussian distributions, we show that an interaction vanishes exactly when the distribution factorizes according to a nontrivial partition in the underlying lower set. We also give a nonvanishing criterion for radial characteristic functions generated by Bernstein functions.
Read the full abstract
Combinatorics
Combinatorial slicing problems of polytopes: How (not) to reconstruct a polytope from its slices
We study combinatorial aspects of hyperplane sections of polytopes, focusing on how much the combinatorics of the sections determines the combinatorics of the original polytope. We show that, in general, combinatorial information about the sections is not enough to determine even the $f$-vector of the polytope. In contrast, for sufficiently generic simple polytopes, the function recording the number of vertices of each central section determines the full combinatorial type. We organize different combinatorial slicing properties into hierarchies, separately for affine and central sections, according to the level of combinatorial structure they determine on the polytope. In analogy with classical metric slicing problems, we formulate combinatorial analogues of the Busemann-Petty problem and Bourgain's slicing problem by replacing volume with face numbers, and show that they fail in every dimension and every face dimension.
Read the full abstract
Combinatorics
A simpler proof of the Matrix Spencer Theorem
Combinatorics
Logarithmic Circumference In Tough Graphs
For every real $t>0$, we prove that every $2$-connected $t$-tough graph contains a cycle of length at least $\ell$ whenever $n \leq \ell(1 + 1/t)^{\lfloor \ell/2\rfloor - 1}$. This establishes the logarithmic bound conjectured by Broersma, van den Heuvel, Jung, and Veldman.
Combinatorics
Augmented singular cohomology, uniform matroids, and real-rootedness
We study the singular cohomology rings of toric varieties associated with several fans arising from uniform matroids. These rings generalize the Chow and augmented Chow rings of matroids. For the singular cohomology ring arising from the augmented Bergman fan of a uniform matroid, we construct an explicit basis derived from the retral basis for the singular cohomology ring of a uniform matroid introduced by the first author. We prove that the augmented Bergman fan does not yield a singular cohomology ring that satisfies the quasi-projective Strong Lefschetz property, whereas a suitable modification of the fan does. We then investigate the zeros of the corresponding refined Hodge–Poincaré polynomials. For uniform matroids, we prove that the refined Hodge–Poincaré polynomials associated with both the singular cohomology ring and the modified augmented singular cohomology ring are real-rooted. The former result resolves a conjecture of the first author. These results extend the real-rootedness theorem of Brändén and the second author for the Chow polynomials of uniform matroids. Finally, we relate the failure of real-rootedness for the augmented singular cohomology ring to the failure of Lefschetz properties.
Read the full abstract
Combinatorics · Cross-listed from math.RT
Interval endomorphism algebras of posets: Reedy structure, combinatorics, and homological theory
Let $P$ be a finite connected poset and let $\Lambda_P$ be the opposite endomorphism algebra of the direct sum of all interval representations of $P$ over a field. Via projectivization, this algebra governs resolutions relative to interval-decomposable representations, which arise naturally in persistence theory. We first show that $\Lambda_P$ carries a Reedy algebra structure in the sense of Dalezios–Šťovíček. Its Reedy degree is given by the cardinality of the indexing interval, and the induced quasi-hereditary order is given by reverse interval cardinality. With respect to the resulting quasi-hereditary structure, we give a concrete combinatorial description of the standard modules and construct explicit projective resolutions of these modules. Using these resolutions, we reduce the calculation of standard–simple Ext groups to the reduced cohomology of simplicial complexes determined by the interval combinatorics. Order reversal gives the corresponding simple–costandard formula. Building on these calculations, we determine all simple–simple Ext groups. These groups are one-dimensional in a unique degree when the corresponding pair of intervals is saturated, and vanish otherwise. As a consequence, we obtain an exact combinatorial formula for the global dimension of $\Lambda_P$, which in particular shows that it is independent of the coefficient field. As an application, for the $m$ by $\ell$ grid $G_{m,\ell}$ with $m\geq\ell\geq2$, we give the explicit formula $\operatorname{gldim}\Lambda_{G_{m,\ell}}=\min\{2\ell,m+\ell-2\}$. This also gives an explicit formula for the interval-resolution global dimension of these grids, settling the corresponding grid conjectures of Asashiba–Escolar–Nakashima–Yoshiwaki and determining the stable value and the precise stabilization threshold.
Read the full abstract
Combinatorics · Cross-listed from math.MG
Additive quasi-isometries and cacti
We prove that if a geodesic metric space contains no $c$-fat theta curve for some $c>0$, then it is $(1,K)$-quasi-isometric to a cactus graph, where $K$ depends only on $c$. Using a coarse characterization of cacti in terms of $c$-fat theta curves this implies that every geodesic metric space quasi-isometric to a cactus is $(1,K)$-quasi-isometric to a cactus graph.
Read the full abstract
Combinatorics
A short proof of the Erd\H os–Sós Conjecture
The Erd\H os–Sós Conjecture was recently proved by GPT-6 Astra, using a very ingenious and surprising argument. In this note, we present a simplified version of this argument in an (arguably) more natural form. We also prove a related conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, and give a substantially simplified proof of an analogous result for eulerian digraphs, again proved by GPT-6 Astra, and announced by Mubayi and Verstraete. In addition, we determine the extremal (di)graphs for all three problems.
Read the full abstract
Combinatorics · Cross-listed from math.MG
On the covering of $n + \epsilon$ square with $n^2 + 1$ unit squares for $n \geq 4$
In 2006, Alexander Soifer conjectured that one cannot fully cover a square of side length $> n$ with $n^2 + O(1)$ unit squares. For small $n \in \{2, 3\}$, in 2009, Janusz Januszewski proved that it is impossible to fully cover a square of side length $> n$ with exactly $n^2 + 1$ unit squares. Recently in 2023, Baek and Lee proved that it is impossible to fully cover an equilateral triangle of side length $> n$ with exactly $n^2 + 1$ unit equilateral triangles whose sides are parallel to it. There were also some progress on a related problem: what is the largest square with side length $S(k)$ that can be fully covered by $k$ unit squares. However, there have been no improvement on the original conjecture. In this work, new tools have been developed that led to the proof of this conjecture for $n = 4$, with potential applications to related problems.
Read the full abstract
Combinatorics
Local measures of interval edge-uncolorability
An interval edge coloring of a graph is a proper edge coloring by integers such that the colors on the edges incident with any vertex form an interval of integers. Not all graphs are interval colorable; a simple counterexample is $K_3$. The (interval coloring) deficiency of a graph $G$ is the minimum number of pendant edges whose addition to $G$ yields a graph with an interval edge coloring. In this paper, we introduce and study further measures of how far from being interval colorable a graph is. The local deficiency of a graph $G$ is the smallest number of pendant edges that needs to be added at every vertex of $G$ in order to obtain a graph with an interval edge coloring; we can think of the colors of these added edges as ”locally missing” at a vertex. We also study a weaker version of this notion, the weak local deficiency, which informally is the size of a largest set of consecutive integers ”locally missing” at a vertex in a proper edge coloring of $G$ minimizing this size. We compare weak local deficiency, local deficiency, and deficiency, and show that the difference can be arbitrarily large in both cases. Moreover, we give concrete examples of graphs whose weak local deficiency (and thus local deficiency) grows with the number of vertices as well as with the maximum degree. We also prove some constructive results on graphs with small weak local deficiency. In particular, all complete multipartite graphs have weak local deficiency at most $2$, and many complete multipartite graphs have weak local deficiency at most $1$. Moreover, bipartite graphs with maximum degree at most $6$, and Eulerian bipartite graphs with maximum degree at most $8$ both have weak local deficiency at most $1$. We conclude the paper by pointing to several open questions for further research.
Read the full abstract
Combinatorics
Cauchy identities for skew Ferrers shapes via RSK and keys
Let $\mu\subseteq\lambda\subseteq(m^n)$. We characterize the image under the ordinary Robinson–Schensted–Knuth correspondence of matrices supported on the skew Ferrers diagram $\lambda/\mu$. The outer boundary determines an upper bound on the right key of the insertion tableau, while the inner boundary determines a lower bound on its left key; both bounds depend on the keys of the recording tableau. This yields tableau expansions of skew Ferrers Cauchy kernels using the standard basis polynomials of Lascoux and Schützenberger, indexed by intervals in Bruhat order. The proof first treats ordinary Ferrers diagrams. Using the supremum characterization of right keys from earlier work, we follow the $\lambda$-dependent bounds through single RSK insertions. When $\lambda$ has repeated parts, these weak column bounds need not form a semistandard tableau. Strictification determines a set $\operatorname{Comp}(\lambda)$ of admissible weak compositions and, for each $\alpha\in\operatorname{Comp}(\lambda)$, a composition $\alpha^\lambda$. Ordinary RSK then gives a weight-preserving bijective realization of the expansion \[ \prod_{(i,j)\in\lambda}\frac{1}{1-x_i y_j} = \sum_{\alpha\in\operatorname{Comp}(\lambda)} \hat K_\alpha(x)K_{\alpha^\lambda}(y), \] where $\hat K_\alpha$ and $K_\alpha$ denote Demazure atoms and key polynomials, respectively. We also give a direct admissibility criterion and a parking procedure for computing $\alpha^\lambda$. After translating conventions, these agree with the admissibility condition and half-bubble-sort construction of Feigin, Khoroshkin, and Makedonskyi. The staircase and truncated-staircase identities follow as special cases. Finally, we extend the weak-bound construction to an infinite alphabet, where strictification need not exist, and derive the infinite-variable Cauchy identity for the $m$-symmetric Schur functions.
Read the full abstract
Combinatorics
Neither simpliciality nor mutation connectivity: conjectures of Las Vergnas and Cordovil-Las Vergnas fail
We construct a simple rank-$7$ oriented matroid on $24$ elements with no simplicial tope, disproving the Las Vergnas simplex conjecture from 1980. We then show that the mutation graph on uniform oriented matroids is disconnected for infinitely many values of rank $r$ and ground-set size $n$, disproving the Cordovil–Las Vergnas conjecture from 1988.
Read the full abstract
Combinatorics · Cross-listed from math.NT
Another proof of the $U^4(\mathbf{F}_p^n)$-inverse theorem
We give a new and shorter proof of a quantitative inverse theorem for the Gowers $U^4$-norm in the setting of high-dimensional vector spaces over finite fields.
Combinatorics
A Möbius function computing $h$-polynomials of nestohedra
We introduce a poset of weighted hypergraphs on a fixed vertex set which has a remarkable property: the Möbius values of the intervals associated to any hypergraph give, up to sign, the coefficients of the $h$-polynomial of its nestohedron. We exploit this relation to provide two new recurrence relations to compute $h$-polynomials of nestohedra.
Read the full abstract
Combinatorics
Direct Generation of a Somos-4 Sequence from an Algebraic Generating Function
We construct a five-parameter quadratic algebraic generating function whose coefficient sequence has prescribed initial Hankel determinants $(\lambda,m,r,\eta)$ and whose Hankel transform belongs to the Somos-4 family $A(1,\tau)$. The construction starts from a Stieltjes continued fraction whose coefficients are generated by an alternating recurrence compatible with the Somos-4 relation. We derive an explicit quadratic equation for the resulting generating function and give the corresponding coefficient recurrence. A subtle feature of the construction is the nonuniqueness of a coefficient sequence determined solely by its ordinary Hankel transform. To select a canonical representative, we additionally prescribe the shifted Hankel determinants obtained from the same Somos-4 orbit advanced by two indices. This companion condition determines the odd and even Stieltjes coefficients separately and removes the remaining freedom in the continued-fraction representation. We also analyze the two algebraic branches at the origin, where they coalesce, and derive a desingularized recurrence for the coefficients. The resulting construction provides a direct algebraic generating-function realization of a general five-parameter family of Somos-4 Hankel transforms.
Read the full abstract
Combinatorics
Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
Bilu and Linial conjectured that every finite $d$-regular graph with $d \geq 2$ admits an edge signing $\sigma$ whose signed adjacency matrix $A_\sigma$ has spectral radius at most $2\sqrt{d-1}$. We prove that every signing meeting the mixed-root condition $r_{A_\sigma}\leq\sqrt{2(d-1)}$ satisfies \[ \rho(A_\sigma) < \frac{3+\sqrt5}{2}\sqrt{d-1}, \] where $r_{A_\sigma}$ is the largest root of the mixed determinantal polynomial $\chi[A_\sigma,-A_\sigma]$. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient $2\sqrt2$ in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of $\chi[A_{\sigma},-A_{\sigma}]$. The second moment gives a simple matrix inequality $A_{\sigma}^2 + dI \preceq 4r_{A_\sigma}^2I$, which yields a preliminary coefficient $\sqrt{7}$. Estimates for the fourth moment use information about short walks to obtain the coefficient $(3+\sqrt{5})/2$. For triangle-free graphs, the coefficient improves to $\sqrt6$, and for graphs with girth at least five, it improves to $\sqrt{35/6}$. As a result of independent interest, we extend the construction to $\chi[A_1,\ldots,A_k]$ for Hermitian matrices $A_1,\ldots,A_k$ with zero diagonal, and compute the first two moments explicitly. Finally, an explicit signing of $K_8$ shows that the mixed-root condition alone cannot guarantee a coefficient below $(4+\sqrt5)/\sqrt6$.
Read the full abstract
Combinatorics
Laurent Symmetric Functions
We describe the ring of Laurent symmetric polynomials in terms of generators and relations, giving an analogue of the Fundamental Theorem of Symmetric Polynomials. We extend the Hall inner product, and give an algebraic proof that the Laurent Schur polynomials form an orthonormal basis of this ring. In the case of infinitely many variables, we realize the ring of Laurent symmetric functions as a direct limit of inverse limits, and relate them to characters of rational and algebraic representations of general linear groups.
Read the full abstract
Combinatorics
Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree
Let $\sigma_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. Previous work determined $C(\sigma_{n,d})$ when $d$ is odd or a power of two, but the general even non-power-of-two case remained open. We determine the certificate complexity for every degree $1\le d\le n$, thereby completing the classification for elementary symmetric Boolean functions. Writing $d=2^t m$ with $m$ odd, we obtain an explicit formula in which the possible deficit from the maximal value $n$ is controlled by $2^t$, while the exact value is determined by a binary containment condition involving $m$. In particular, \[ n-2^{\nu_2(d)}+1\le C(\sigma_{n,d})\le n, \] and we characterize when the upper bound is attained. Moreover, we determine the least positive period of the certificate-complexity deficit $\Delta_d(n)=n-C(\sigma_{n,d})$: it is $1$ for odd $d$, equals $d$ when $d$ is a power of two, and equals $2^{\lfloor\log_2 d\rfloor+1}$ for even non-power-of-two $d$. This least-period problem is distinct from the classical periodicity of the underlying value sequence $\binom{j}{d}\bmod 2$. The known odd-degree and power-of-two formulas are recovered as special cases.
Read the full abstract
Combinatorics
Algebraic Structures on Sets of Partitions
Motivated by Robert Schneider's trailblazing work toward developing a unifying algebraic theory of integer partitions, we explore various binary operations on partitions to identify algebraic structures on sets of partitions. In particular, we discover that several sets of restricted partitions form abelian groups under reduced versions of concatenation, component-wise addition, and component-wise multiplication. One type of restricted partition from a group structure also enjoys a bijection with ordinary partitions of any given size. We extend two partition groups to vector spaces over the finite field $\mathbb{Z}_p$, where $p$ is a prime. We further discover that partitions are equipped with a commutative ring structure. Finally, we consider subgroups, subspaces, and ideals of our algebraic partition structures to investigate properties of related types of restricted partitions. The new examples of algebraic structures described in this paper open the door to partition analysis via algebraic tools, decompositions, extensions, and geometry.
Read the full abstract
Combinatorics
Multivariate stability of powered triangular recurrences and parametrised Eulerian polynomials
We prove multivariate stability for a class of affine triangular recurrences whose two coefficients are raised to an arbitrary positive integer power. The variables keep track of cross-step heights in a weighted lattice-path model. The applications include stability and real rootedness of parametrised Eulerian, Stirling, and Lah families. For the parametrised Eulerian polynomials, we obtain multivariate refinements of known real-rootedness results and prove simplicity and strict interlacing of consecutive rows. A kernel-preserving bijection with increasing binary trees yields a synchronised Foata–Strehl action on pairs and a combinatorial interpretation of their gamma coefficients along with a recurrence. The same bijection identifies refinement posets that admit symmetric Boolean and chain decompositions for parameter one and cover-supported $\mathfrak{sl}_2$ operators prove their PECKness. We extend the stability and strict interlacing results to synchronised Stirling permutations and prove PECKness for ordinary Stirling permutations with a fixed number of plateaux.