Papers

We study a variant of the $k$-in-a-row game in which players alternatively claim positions until a $k$-in-a-row is created among all claimed positions. This leads to the constraint near $k$-in-a-row avoiding on configurations and the associated problem of determining their extremal densities of such configurations. We investigate this problem on two types of boards: the grid $\mathbb{Z}^2$ and hypercubes $[k]^d$. For the grid $\mathbb{Z}^2$, we establish nearly tight bounds on the maximum density $D(k,\mathbb{Z}^2)$, showing that $D(k,\mathbb{Z}^2)=1-\frac{2}{k}$ whenever $3\nmid k$, and determine both $D(3,\mathbb{Z}^2)$ and $d(3,\mathbb{Z}^2)$ exactly. We also bound the minimum density $d(k,\mathbb{Z}^2)$ up to a gap of $(8+o(1))k^{-1}$. For hypercubes $[k]^d$, we derive asymptotic bounds on $D(k,[k]^d)$ up to order $k^{-2}$ and obtain the exact value of $d(k,[k]^d)$. Our results contrast with the classical no-$(k+1)$-in-line problem, a similar problem imposing different constraint, where the trivial upper bound is conjectured to be attainable.

We introduce a partition-selection method to generalize the flow, chromatic, and Tutte polynomials of a graph by restricting the standard edge subgraph expansions to subgraphs given by prescribed connected vertex partitions. We establish similar deletion-contraction formulas and specialization relations for these polynomials, recovering all classical polynomial invariants when the selection is the set of all partitions. Next we study a relation between Jaeger et al.'s nonhomogeneous flows and a special class of partition-selected flow polynomials (called affine flow polynomials). Specifically, we give a geometric realization of nowhere-zero nonhomogeneous flows by restricting the edge-coordinate arrangement to affine flow spaces. The resulting characteristic polynomials coincide with Kochol's admissible assigning polynomials and with affine flow polynomials, which enumerate nowhere-zero nonhomogeneous flows over finite fields. To see the key role of the partition-selection framework, we further introduce boundary arrangements determined by the bond structure of a graph. Using the intersection posets of boundary arrangements, we obtain the classification of all restricted arrangements mentioned above, the comparison of unsigned coefficients of affine flow polynomials, and the decomposition formulas for affine flow polynomials.

Let $T_{1}, T_{2}, \dots, T_{k}$ be $k$ spanning trees of a graph $G$. For any pair of vertices $u$ and $v$, if the $u$–$v$ paths in the $k$ spanning trees are pairwise openly disjoint, then the spanning trees are called completely independent spanning trees (CISTs) of $G$. In this paper, we first prove that every 3-connected 2-outerplanar triangulated disc has two completely independent spanning trees. Next, for a 3-connected 3-outerplanar triangulated disc $G$, we provide sufficient conditions for $G$ to have two completely independent spanning trees. We provide an example of a 3-connected 4-outerplanar triangulation that does not have two completely independent spanning trees.

We associate to each positroid variety in the Grassmannian $\mathrm{Gr}(k,n)$ a polyhedral complex, which we call a fence complex. Fence complexes consist of unions of faces of the Gelfand-Tsetlin polytope $P_{k,n}$ associated to a fundamental weight $\omega_k$. We show that these fence complexes are homeomorphic to closed balls. Furthermore, they endow the Gelfand-Tsetlin polytope with the structure of a regular CW complex, giving a polyhedral complex presentation of the regular CW complex structure on $\mathrm{Gr}(k,n)_{\geq 0}$. We also show that the Ehrhart polynomial of a fence complex equals the Hilbert polynomial of the associated positroid variety. We prove that under the Sturmfels-Gonciulea-Lakshmibai degeneration of $\mathrm{Gr}(k,n)$ to the toric variety of the Gelfand-Tsetlin polytope, positroid varieties degenerate to the reduced union of toric varieties corresponding to their fence complexes. As an application, we classify when positroid varieties contained inside hook Schubert varieties are arithmetically Gorenstein. We also derive a recursive character formula for cyclic Demazure modules, which we show is equivalent to a formula of Almousa, Gao and Huang.

In this paper, we introduce and prove a set of rank recurrence relations for $q$-Whittaker and Macdonald operators. We also derive an explicit expression for the $k$-th power of the $q$-Whittaker operators in terms of the $q$-deformed binomial probability distribution, and we express the rank recurrence relations for the Macdonald operators in terms of the Cauchy determinant.

We examine upper bounds on Nordhaus-Gaddum type problems for parameters related to graph connectivity. Our main result is that for a graph $G$ on $n$ vertices where both $G$ and its complement $G^c$ are connected, then the sum of the algebraic connectivity of $G$ and the algebraic connectivity of $G^c$ cannot exceed $n-3$ (with finitely many exceptions with a small number of vertices). We obtain similar results for the isoperimetric number of a graph, and explore similar Nordhaus-Gaddum type questions for the Cheeger constant and the second eigenvalue of the normalized Laplacian matrix.

We develop a theory of partial matchings between finite-dimensional subspaces $A,B$ in a field extension $K \subsetneq L$, providing structural, quantitative, and extremal results for their deficiency. Our main results include (1) a characterization of those pairs $(A,B)$ that are partially matchable up to a specified defect, (2) a decomposition theorem for pairs $(A,B)$ having positive deficiency, (3) an existence criterion for pairs having a prescribed dimension and satisfying a deficiency bound, and (4) a formula for the maximum attainable deficiency at each dimension, assuming $1 \notin B$ and the extension has a proper nontrivial intermediate field of finite $K$-dimension. We use these results to recover and extend various parts of this area of matching theory. Our approach blends algebraic techniques with tools from matroidal transversal theory, and utilizes a linearized version of the $e$-transform from additive number theory.

We introduce a censored version of the stochastic six-vertex model. We show that for parameters $b_1 < b_2$, this model started from the initial condition ${1}_{x>0}$ is stochastically dominated at any time by the blocking measure. This is a partial analog of the censoring inequality for monotone spin systems. In particular, this result allows us to control the behavior of second-class particles. The proof uses parabolic Kazhdan–Lusztig $R$-polynomials, whose appearance is explained using a connection between the stochastic six-vertex model and the Iwahori–Hecke algebras of symmetric groups. Furthermore, we find an intertwining relation for this process using normalized parabolic Kazhdan–Lusztig $R$-polynomials as an intertwining kernel.

We give two combinatorial presentations for the algebraic cobordism ring $\Omega^*(M)$ of the toric variety of the Bergman fan of any loopless matroid $M$. As a consequence of our presentations, we obtain an $\Omega^*(\mathrm{pt})$-algebra isomorphism $\Omega^*(M) \simeq CH^*(M) \otimes_{\mathbb{Z}} \Omega^*(\mathrm{pt})$, where $CH^*(M)$ is the Chow ring of $M$ and $\Omega^*(\mathrm{pt})$ is the algebraic cobordism ring of the point. This isomorphism generalizes, in part, the exceptional integral isomorphism between the Chow ring and $K$-ring of a matroid, studied in the recent works of Berget–Eur–Spink–Tseng and Larson–Li–Payne–Proudfoot. For a complex hyperplane arrangement $\mathcal{H}$, we prove that the algebraic cobordism ring of the wonderful variety $W_\mathcal{H}$ of $\mathcal{H}$ and the algebraic cobordism ring of the toric variety of the matroid underlying $\mathcal{H}$ are isomorphic, and that both rings coincide with the complex cobordism ring of $W_\mathcal{H}$.

We study the random variable that counts the number of specific arrangements of clustered consecutive numbers in permutations under the Mallows distribution. We provide an asymptotic expression for the expected value of this random variable. This result extends and tightens the previously known result by Pinsky (2022) concerning clustered consecutive numbers in Mallows permutations. Moreover, we identify a range of parameters for which the distribution of the number of arrangements of clustered consecutive numbers in Mallows permutations is close to a Poisson distribution.

A family of $m \times n$ matrices $\mathcal{F} \subseteq \mathbb{F}_q^{m \times n}$ is {$(t-1)$-intersection-free} if $\dim \ker(A-B) \neq t-1$ for all $A,B \in \mathcal{F}$. A \emph{forbidden $(t-1)$-intersection problem} for a collection of matrices asks for the size and structure of extremal $(t-1)$-intersection-free families within that collection. We solve this problem in $\mathrm{GL}(n,q)$ for all pairs $(n,t)$ such that $t<c\cdot n$ where $c$ is a universal constant. We show that the $t$-umvirates and their duals, are the only maximal $(t-1)$-intersection-free families $\mathcal{F} \subset \mathrm{GL}(n,q)$. Here, a $t$-umvirate is defined as the family of all matrices that agree on a fixed $t$-dimensional subspace, and its dual as those whose transposes agree on it. The best previously known result, due to Ellis, Kindler, and Lifshitz, established this bound under the assumption $n \geq e^{Ct\log t}$ for some constant $C>0$. We also give Frankl–Rödl-type constructions showing that this range of $t$ is almost the best possible: we show that for values of $t>n/2$ the extremal behavior changes and no clean analogue is expected. Our proof builds upon recent global hypercontractivity results for matrix spaces due to Evra, Kindler, and Lifshitz, and broadly applies to any sufficiently dense class of matrices.

In a recent paper, the authors introduced an infinite hierarchy of $q$-hypergeometric identities, of which the first three orders, $0$, $1$, and $2$, relate to the partition theorems of Euler, Lebesgue, and Capparelli, and stated a partition theorem at order 4 which lies beyond Capparelli's theorem. Here, we first state certain partition theorems that hold at all even orders beyond Capparelli and provide bijective proofs for these theorems. In doing so, we show that there is a fourfold infinite hierarchy of partition theorems that emanates from Capparelli's theorem, which is the base case. It is also shown that the equality of two of the four generating functions holds for all orders, odd and even. Lastly, a very general framework for the remaining two functions is constructed via the method of weighted words, encompassing all possible orders and yielding several infinite hierarchies with different dilations and translations.

In 1988, Las Vergnas conjectured that if $M$ is a binary matroid with bicycle dimension $d$, then for $0 \leq k \leq d$, the $k$th derivative of the diagonal Tutte polynomial $T(M;z,z)$ evaluated at $z=-1$ is an integer multiple of $2^{d-k}$. While this was rapidly disproved for binary matroids and for graphs in general, extensive computations strongly suggested that it might be true for planar graphs. In this paper we prove that this is indeed the case. To do this, we consider a stronger divisibility property that we call the LV property, and a larger class of graphs, namely the class of delta-wye-reducible graphs. By a detailed analysis of how a delta-wye exchange affects the coefficients of the diagonal Tutte polynomial, we show that delta-wye-reducible graphs have the LV property. That Las Vergnas' conjecture holds for planar graphs immediately follows because planar graphs are delta-wye reducible and the LV property is stronger than Las Vergnas' divisibility conditions.

A cyclic meander is an embedded oriented loop in the plane intersecting a fixed infinite line, or circle, transversely in a linearly ordered set of $2n$ points. By keeping track of the order in which the loop visits these points, the cyclic meander induces a cyclic permutation on these marked points. Correspondingly, given a permutation on $n$ letters, one can ask whether or not a cyclic meander induces the permutation in this manner, and if not, what is the most efficient way of doing so if we allow more points of intersection? This process gives a way of associating to a permutation on $n$ letters a measurement of complexity of the permutation in question. The principal result of this work shows that the maximum of this quantity, the meander number, over all cyclic permutations on $n$ letters, is bounded above and below quadratically in $n$. This result resolves a conjecture of Schwartz~\cite{richtpss} in relation to his work on the topological salesman problem. We conclude this work by proving the existence of families of cyclic permutations on $n$ letters whose meander numbers realize a continuum of growth rates between linear and quadratic.

The cooling number measures the speed at which a slow-moving influence or contagion spreads on a graph. In this paper, we investigate the cooling number of four classical graph products: the Cartesian product, the strong product, the lexicographic product, and the direct product. We also determine the cooling number of a disconnected graph in terms of the cooling numbers of its components. We conclude with open problems.

In arXiv:2311.10069, Matolcsi et al. show that the fractional chromatic number of the plane is at least 4. Their proof uses a 27-vertex unit-distance graph in the Moser lattice, with geometric fractional chromatic number exactly 4. We show that this bound is tight for graphs in the Moser lattice by exhibiting geometric 4-colorings of the entire lattice. The same colorings also extend to the entire Moser ring.

Let $G$ be a loopless multigraph with maximum degree $\Delta(G)$, average degree $\overline{d}(G)$, density $\Gamma(G)$, and chromatic index $\chi'(G)$. A multigraph $G$ is called edge-$\Delta$-critical if $\Delta(G)=\Delta$, $\chi'(G)=\Delta(G)+1$ and $\chi'(H) \le \Delta(G)$ for every proper subgraph $H\subset G$. Vizing conjectured that if $G$ is an edge-$\Delta$-critical simple graph on $n$ vertices, then $\overline{d}(G) \ge \Delta-1+\tfrac{3}{n}$. Motivated by this, we conjecture that every edge-$\Delta$-critical multigraph $G$ satisfies $\overline{d}(G) \ge \tfrac{2\Delta+2}{3}$, which is best possible. We first give a general lower bound in this direction. For any such graph $G$, \[ \overline{d}(G) \ge \begin{cases} \frac{\sqrt{17}-3}{2}(\Delta+1) & \text{if } \Delta \le 112;\\[4pt] \frac{\Delta+\sqrt{2\Delta-1}}{2} & \text{if } \Delta \ge 113. \end{cases} \] This bound can be further improved under an additional condition on the multiplicity $\mu$. In this case, \[ \overline{d}(G)\ge \min\left\{ \frac{2\mu\Delta+2\mu(2\mu-1)}{4\mu-1},\; \frac{\sqrt{17}-3}{2}(\Delta+1) \right\}. \] We also confirm the conjecture for $\Delta \in \{2,3,4,5,6,7,8\}$. As a consequence, Goldberg's conjecture~\cite{Goldberg1984} holds for $\Delta(G)\in\{2,3,4,5\}$, that is, every multigraph $G$ with $\chi'(G)\ge \Delta(G)+1$ satisfies $\Gamma(G)\ge \Delta(G)$.

We resolve a question of Bailey, Hollars, Li and Luo. For all sufficiently large $n$, let $r=\lfloor(n-1)/2\rfloor$. We prove that the edges of any Hamiltonian Berge cycle in a simple $n$-vertex $r$-uniform hypergraph, together with any one additional edge, contain Berge cycles of every length from $2$ to $n$. In odd order we prove a stronger prescribed-unused-edge theorem using rigidity of large subsets of odd cyclic groups and an alternating matching exchange. In even order we introduce a two-gap edge-reassignment method. Split locks cover all lengths outside a seven-term middle band. The absence of the central length forces an exact reflected translation-wave structure, which is eliminated by an additive covering theorem derived from sum-free stability. The remaining near-central lengths follow from a two-defect recurrence and bounded-run forcing.

Brouwer's Laplacian conjecture states that the sum of the largest $k$ eigenvalues of a graph's Laplacian is less than or equal to the number of edges plus $\binom{k+1}{2}$. We give a proof of this conjecture. Our proof relies on the Grone–Merris–Bai theorem for split graphs. We also show the converse, thereby establishing an equivalence between Brouwer's conjecture and the Grone–Merris–Bai theorem.

We show that for any $A\subseteq \mathbb{F}_q^n$ lacking non-trivial solutions to a translation-invariant linear equation of genus one, meaning that no nonempty proper subset of the coefficients sums to $0$, there is a set $B\subseteq \mathbb{F}_q^m$ in some higher dimension which also lacks non-trivial solutions, such that \[|B|^{1/m}>|A|^{1/n}.\] In particular, this implies that no fixed cap set in $\mathbb{F}_3^n$ gives an asymptotically optimal lower bound by direct products alone.

We prove the group version of the Matrix Spencer conjecture. For every finite group $G$, there exist signs $\varepsilon\in\{\pm1\}^G$ such that $$\left\| \sum_{g\in G} \varepsilon_g\rho(g) \right\|\leq C\, \sqrt{|G|},$$ where $\rho$ is the left regular representation of $G$ and $C$ is a universal constant. This conjecture was posed in [BKMZ24], which settled it for simple groups; we establish it for all finite groups, combining the Peter–Weyl decomposition with the intrinsic-freeness inequalities of [BBvH23] in an iterated partial-coloring argument.

Let $M \subset \{0,\pm1\}^n$ be a set such that $(m,m)=4$ for every $m\in M$, and $(m_1,m_2)\in\{-4,-3,-2,-1,0,3\}$ for any two distinct vectors $m_1,m_2\in M$. We determine the maximum possible cardinality of such a set $M$ for all sufficiently large $n$.

Let $S$ and $T$ be disjoint sets with $|S|=i$ and $|T|=r-1$ for $2\le i\le r-1$, and let $B_i^{(r)}$ be the $r$-graph on $S\cup T$ whose edges are the $r$-subsets containing $S$ or $T$. We study the deficit $q_{r,i}:=1-\pi(B_i^{(r)})$ in its Turán density. Balogh, Bohman, Bollobás, and Zhao previously obtained bounds for these deficits with logarithmic gaps near both ends of the sequence $B_i^{(r)}$, namely, when $i=O(1)$ or $i=r-O(1)$. We close these gaps by showing that, as $r\to\infty$, for every fixed integer $a\ge1$, $q_{r,a+1}=\Theta_a(r^{-a})$, and for every fixed integer $b\ge2$, $q_{r,r-b}=\Theta_b(r^{-b}\log r)$.

For a given Coxeter group, we study distributive lattices called middle orders refining the weak order and refined by the Bruhat order. In type $A$, we construct such lattices indexed by binary trees using a direct bijection between permutations and lower sets of a certain partition of the root poset into rectangles. When the binary tree is a left-comb tree, we recover the middle order defined by Bouvel, Ferrari, and Tenner (2025). We study combinatorial properties of these lattices, and show they are the only distributive lattices between the weak and Bruhat orders in type $A$. For general Coxeter groups, we study middle orders on parabolic quotients and use these to generalize our construction in type $A$ to other Weyl groups, obtaining so-called “minuscule middle orders”. We show that they are a subset of sorting orders defined by Armstrong (2009), and we give conjectural descriptions of all middle orders that are not minuscule.

For integers $k\ge 1$ and $n\ge k+1$, let $\operatorname{ex}^{\mathrm{HIST}}_k(n)$ denote the maximum number of edges in a $k$-connected graph of order $n$ which contains no homeomorphically irreducible spanning tree (or briefly HIST). We determine these extremal numbers for $k=1$ and $k=2$. More precisely, we prove that $\operatorname{ex}^{\mathrm{HIST}}_1(n)=\binom{n-2}{2}+2$ for $n\ge 9$, with $L_n$ as the unique extremal graph, and that $\operatorname{ex}^{\mathrm{HIST}}_2(n)=\binom{n-3}{2}+4$ for $n\ge 13$, with $B_n$ as the unique extremal graph. This provides a Turán-type extremal result for spanning trees with no vertices of degree two.

We develop a framework for comparing probability measures on finite posets via hockey-stick domination, an order relation defined through interval-counting test functions. The theory introduces poset integrals, derivatives, power functions and the associated moment functionals, all of which are invariant under poset isomorphisms. We prove that hockey-stick domination admits an exact quantitative characterization: whenever $\mu$ is dominated by $\nu$ in the hockey-stick order, the corresponding Zolotarev-type distance is equal to one half of the second-order poset moment of $\nu-\mu$. We further develop a constructive theory for generating such domination relations. In particular, we show that hockey-stick domination is preserved under direct products, disjoint unions, ordinal sums, and suitable ideal restrictions, yielding natural families of examples on chains, Boolean posets, rectangular lattices, rooted trees, and Young diagrams.

Let $\varepsilon\in (0,1/2]$ and let $G$ be a balanced bipartite graph on $2n$ vertices with minimum degree at least $(1/2 + \varepsilon)n$. Then, whp, the hitting time for minimum degree 2 coincides with the hitting time for Hamiltonicity. This extends Bollobás–Kohayakawa and gives a bipartite analogue of Johansson's theorem. As an immediate corollary, we deduce a sharp threshold result for Hamiltonicity in such graphs.

Lifted product codes are an important family of quantum low-density parity-check (QLDPC) codes, as they were the first QLDPC code family shown to be asymptotically good. Understanding the structure of their parity-check matrices $H_{\mathsf{X}}$ and $H_{\mathsf{Z}}$, as well as the associated Tanner graphs, is essential for analyzing their decoding behavior and error-floor performance. In this work, we show that the Tanner graphs of $H_{\mathsf{X}}$ and $H_{\mathsf{Z}}$ are indeed isomorphic, and investigate their graph-theoretical structure. We establish conditions ensuring the connectivity of these graphs and provide bounds on their minimal absorbing sets, providing new insight into the combinatorial structures influencing decoding performance.

We describe a computational search for quadratic APN (Almost Perfect Nonlinear) functions over $\mathbb{F}_{2^8}$ within a structured algebraic subspace defined by a self-equivalence constraint. The search space is the 40-dimensional $\mathbb{F}_2$-linear subspace $V_A = \{F : F \circ A = A \circ F\}$ for a specific linear automorphism $A$ of order 5 (class index 22 in the taxonomy of Beierle, Brinkmann, and Leander); this subspace was previously reported to contain no APN functions under their recursive tree search method. We combine two phases: (1) random sampling inside $V_A$ via an explicit RREF parameterization to find APN center functions, and (2) Groebner basis computation in Magma over the Boolean polynomial ring to enumerate all APN functions in a 24-dimensional hyperplane through each center. From 428 hyperplane computations (covering 0.65% of the 65,536 total hyperplanes in $V_A$) we obtained 566 quadratic APN functions falling into six CCZ-equivalence classes under the ortho-derivative invariant. Four of these classes, comprising 500 functions, match no entry in the Beierle et al. 2025 database of 3,775,599 quadratic APN functions and no entry in the pre-2020 compilation of 12,921 instances. Two classes (66 functions) are identified as CCZ-equivalents of the Gold functions x^3 and x^9, confirming pipeline correctness. For quadratic APN functions, a signature mismatch rigorously certifies CCZ-inequivalence, by Yoshiara's theorem (CCZ = EA for quadratic APN) together with the ortho-derivative invariant; the absence of a signature match in the above databases therefore constitutes a rigorous proof of CCZ-inequivalence for the new classes. The complete dataset, source code, and verification scripts are publicly available.

For a set $X$ of integer points, the relaxation complexity $\operatorname{rc}(X)$ is the smallest number of facets of any polyhedron $P$ such that $P \cap \mathbb{Z}^d = X$. In this paper, we focus on the case where $X$ is the discrete standard simplex $\Delta_d = \{\mathbf{0}, \mathbf{e}_1, \dots, \mathbf{e}_d\}$. We show that $\operatorname{rc}(\Delta_d) = O(\log d)$ by an explicit, elementary construction. This improves upon the previously best-known upper bound $\operatorname{rc}(\Delta_d) = O(d / \sqrt{\log d})$ due to Aprile, Averkov, Di Summa, and Hojny (2024) and matches an asymptotic lower bound by Averkov and Schymura (2022).