# Paperlane: Combinatorics (math.CO), Wednesday 18 November 2026

Announced by arXiv on 2026-11-18. 325 new papers, 63 cross-lists and 280 new versions. Fetched 2026-11-18T14:31:40Z, built 2026-11-18 15:41 UTC.

Titles, authors and abstracts come from arXiv. Read the full text on arXiv. Signals are checked by code: code links found in the abstract or comments, whether a linked GitHub repository contains a Lean project (a lakefile or lean-toolchain file) and whether `lake build` passes on it, and whether the entry is a new version of an older paper. Paperlane does not rank papers or authors.

## New papers (56)

### Quantum $K$-theoretic Whitney relation for Lagrangian Grassmannian

- arXiv: 2611.21654 · https://arxiv.org/abs/2611.21654v1 · PDF https://arxiv.org/pdf/2611.21654v1
- Authors: Takafumi Kouno
- Categories: math.AG (primary), math.CO, math.KT, math.QA, math.RT
- Comments: 13 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21654.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21654.md

We give a quantum $K$-theoretic analogue of the Whitney relation for the torus-equivariant $K$-ring of the Lagrangian Grassmannian. As a consequence, we give a presentation of the torus-equivariant quantum $K$-ring of the Lagrangian Grassmannian. The strategy for obtaining such relations is to use the quantum $K$-theoretic Whitney relation for the full-flag manifold in type $C$ established by the author and Kato's pushforward map from the quantum $K$-ring of the full-flag manifold to that of the partial flag manifold. Then the Nakayama-type argument established by Gu et al., together with the classical Whitney presentation for the torus-equivariant $K$-ring of the Lagrangian Grassmannian, gives a proof of such a presentation.

### Maximum number of cells in a matroid subdivision of hypersimplex

- arXiv: 2611.22754 · https://arxiv.org/abs/2611.22754v1 · PDF https://arxiv.org/pdf/2611.22754v1
- Authors: Mahyar Hasani
- Categories: math.AG (primary), math.CO, math.RT
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22754.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22754.md

David Speyer proved that the maximum number of cells in a regular matroid subdivision of the hypersimplex $Δ(m,t)$ is $\binom{t-2}{m-1}$ , using the language of tropical geometry and properties of the Tutte polynomial of a matroid \cite[Theorem 6.1]{Speyer}. In this paper, we prove this result in general, i.e. for arbitrary matroid subdivisions including the non-regular ones. We perform a different combinatorial way using our results in \cite{HHH} and independent of tropical language.

### Counting formulas and refined generating functions for inversion-sequence Classes 152 and 207

- arXiv: 2611.21657 · https://arxiv.org/abs/2611.21657v1 · PDF https://arxiv.org/pdf/2611.21657v1
- Authors: Haobo Ma, Toufik Mansour, Wenlin Zhang
- Categories: math.CO (primary)
- Comments: 25 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21657.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21657.md

For the two Class 152 pattern sets, we prove that the common number of inversion sequences of length \(n\geq 1\) is \(a_n=1+\sum_{j=1}^{n-1}\binom{2j}{j}\). The Class 152 proof uses first-descent and last-zero decompositions, with weighted Dyck paths evaluating the resulting generating functions. For Class 207, we prove equality of the three total-count series and give their common generating function as an explicit Lambert-series expression after the substitution \(z=q/(1+q)^2\). Complete legal-site and catalytic recurrences lead to a Lambert series for one class and \(q\)-product orbit sums for another. A cubic limit of the balanced nonterminating \({}_3φ_2\) \(q\)-Saalschutz summation identifies these expressions. Fixed-maximum expansions, finite verification data, refined analytic obstructions, and signed specializations are recorded in the supplementary material.

### Co-edge-regular graphs with two $λ$-values and four distinct eigenvalues

- arXiv: 2611.21664 · https://arxiv.org/abs/2611.21664v1 · PDF https://arxiv.org/pdf/2611.21664v1
- Authors: Suil O
- Categories: math.CO (primary)
- Comments: 14 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21664.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21664.md

A connected $k$-regular graph $G$ on $n$ vertices is co-edge-regular if any two distinct non-adjacent vertices have the same number of common neighbors. For adjacent vertices $u$ and $v$, let $λ(u,v)=|N(u)\cap N(v)|$. Ge and Koolen asked whether the theorem of Neumaier on strongly regular graphs with fixed smallest eigenvalue extends to co-edge-regular graphs with exactly four distinct eigenvalues in which $λ(u,v)$ takes exactly two values over the edges $uv$. In this paper, we answer this question. For every integer $t\ge2$ there is $n_t$ such that if $G$ is such a graph with smallest eigenvalue at least $-t$, $n\ge n_t$, and $k<n-2-(t-1)^2/4$, then either $G$ is a clique extension of a strongly regular graph, or $G$ is obtained from a strongly regular graph with a Hoffman coloring by adding all edges inside the color classes. Consequently, $G$ is a clique extension of a strongly regular graph, a $p\times q$ grid with $p\ne q$, or the block graph of a resolvable Steiner $2$-design in which every parallel class is made into a clique.

### Resistance-regular graphs need not be regular

- arXiv: 2611.21670 · https://arxiv.org/abs/2611.21670v1 · PDF https://arxiv.org/pdf/2611.21670v1
- Authors: Murad ul Islam Khan, Ghulam Haidar
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21670.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21670.md

A connected graph is resistance-regular if the sum of the effective resistances from a vertex to all other vertices does not depend on the vertex, or equivalently if the Moore-Penrose inverse of its Laplacian has constant diagonal. Walk-regular graphs have this property, and Zhou, Wang and Bu asked in 2016 whether every resistance-regular graph is regular, a question that also arises in the study of graphs with constant resistance curvature. We answer this question in the negative and examine both what resistance-regularity forces and how far from regular such graphs can be. On the spectral side, we prove that a connected graph is walk-regular if and only if the first $m-1$ powers of its Laplacian pseudoinverse have constant diagonal, where $m$ is the number of distinct nonzero Laplacian eigenvalues. Because resistance-regularity constrains only the first power, it forces regularity when $m\le2$ and allows at most two vertex degrees when $m=3$. Any non-regular resistance-regular graph has minimum degree at least $3$ and a connected complement, and an exhaustive computer search shows that it must have at least $13$ vertices. For every even $p\ge4$, we construct a resistance-regular graph on $4p$ vertices with degrees $2p-2$ and $2p-1$, obtaining closed formulas for its Laplacian spectrum and for all pairwise effective resistances. Using module blow-ups, we then construct $n$-vertex resistance-regular graphs whose two degrees differ by $(\sqrt{4n+1}-5)/4$ for infinitely many $n$, as well as examples with three and four distinct degrees, whereas the maximum and minimum degrees of any resistance-regular graph on $n$ vertices differ by less than $n/2$. We close by conjecturing that in a resistance-regular graph the sum of squared resistances at a vertex increases strictly with its degree.

### Gallai's path decomposition conjecture for $K_5$-minor-free graphs

- arXiv: 2611.21673 · https://arxiv.org/abs/2611.21673v1 · PDF https://arxiv.org/pdf/2611.21673v1
- Authors: Junhao Zhang, Qinghai Liu, Yanmei Hong
- Categories: math.CO (primary)
- Comments: 21 pages,5 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21673.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21673.md

Gallai conjectured that the edges of every connected graph on $n$ vertices can be partitioned into at most $\ceil{n/2}$ paths. We prove that every connected $K_5$-minor-free graph other than $K_3$ and $K_5-e$ admits such a partition into at most $\floor{n/2}$ paths. The two exceptions require $\ceil{n/2}$ paths. In a smallest counterexample we find a $4$-connected planar part containing four vertices of degree five. Their neighborhoods meet the boundary in at most one vertex. This allows us to apply the planar configurations of Blanché, Bonamy, and Bonichon and to realize the reduced graph as a minor of the original graph.

### The Conic Tverberg plus minus

- arXiv: 2611.21868 · https://arxiv.org/abs/2611.21868v1 · PDF https://arxiv.org/pdf/2611.21868v1
- Authors: Egor Kolpakov
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21868.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21868.md

We prove a Tverberg type theorems: Given a set $A\subset \mathbb{R}^d$ and an affine subspaces $L_1,...,L_m\subset \mathbb{R}^d$. In some conditions there is a partition $A_1, ..., A_m, B_1, ..., B_m$ of $A$ such that the sets $L_i\cup A_i\cup B_i$ for $i=1,...,m$ have common barycentre with negative masses in $B_i$ and positive masses in $A_i$. The case $B_1=...=B_m=L_1=...=L_m=\varnothing$ is Tverberg's classical theorem. The case $L_1=...=L_m=\varnothing$ gives a partial answer to the question of Barany-Soberon about the possible number of negative masses.

### Forbidden Substructures Preserved by the Blob Graph Operation

- arXiv: 2611.21961 · https://arxiv.org/abs/2611.21961v1 · PDF https://arxiv.org/pdf/2611.21961v1
- Authors: Jakub Pączka, Agnieszka Przeździecka, Piotr Tyrakowski
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21961.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21961.md

The blob graph $G^\circ$ of a graph $G$ has a vertex for each non-empty connected vertex subset of $G$, with two distinct subsets adjacent whenever they intersect or are joined by an edge of $G$. This construction has been used in reductions from induced subgraph optimisation problems to maximum-weight independent set, where the preservation of forbidden substructures is essential. We completely characterise the graphs $H$ for which excluding $H$ from $G$ guarantees that $G^\circ$ also excludes $H$, under six containment relations. For subgraphs, minors, and topological minors, preservation holds exactly when $H$ has at most two vertices. For induced subgraphs, it holds exactly when $H$ is a linear forest. For induced topological minors, it holds exactly when $H$ is triangle-free and has maximum degree at most two. For induced minors, it holds exactly when $H$ is triangle-free and every neighbour of a vertex of degree at least three has degree exactly two. These classifications unify and extend preservation results previously established for particular forbidden graphs in algorithmic applications.

### Supersaturation and reconfiguration diameter of independent transversals

- arXiv: 2611.21966 · https://arxiv.org/abs/2611.21966v1 · PDF https://arxiv.org/pdf/2611.21966v1
- Authors: Wouter Cames van Batenburg, Penny Haxell, Ross J. Kang, Ronen Wdowinski
- Categories: math.CO (primary), cs.DM
- Comments: 14 pages, 1 figure
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21966.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21966.md

Consider the collection of independent transversals of a vertex-partitioned graph of maximum degree $Δ$. It is a classic result that when all parts have size at least $2Δ$, the collection is nonempty. Recently, it was found that if the parts have size at least $2Δ+1$, then every pair of independent transversals is connected, within the collection, by a sequence of one-vertex reconfigurations. We prove, among other results, that there are exponentially many independent transversals when the parts have size at least $2Δ$, and that the reconfiguration diameter is at most linear in the number of parts when the parts have size at least $4Δ$.

### Shifted Hankel determinants via Hankel continued fractions

- arXiv: 2611.21968 · https://arxiv.org/abs/2611.21968v1 · PDF https://arxiv.org/pdf/2611.21968v1
- Authors: Guo-Niu Han, Lihong Yang
- Categories: math.CO (primary)
- Comments: 136 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21968.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21968.md

The Hankel determinants $H_n(F)$ of a power series $F(x)$, as well as the shifted ones $H_n^{(1)}(F)$ and $H_n^{(2)}(F)$, can be read off from its Jacobi continued fraction, provided that all $H_n(F)$ are nonzero. Without any condition on $F$, the Hankel continued fraction ($H$-fraction) still yields all $H_n(F)$. We show that the $H$-fraction of $F$ also determines the shifted Hankel determinants $H_n^{(1)}(F)$, $H_n^{(2)}(F)$ and the backward shifted ones $H_n^{(-1)}(F)$, and we give explicit formulas for them. As applications, we provide simple proofs of Hankel determinant evaluations that were previously established by means of complicated explicit $H$-fractions.

### Laplacian Eigenvectors of Generically Weighted Graphs Have Pairwise Distinct Coordinates

- arXiv: 2611.21979 · https://arxiv.org/abs/2611.21979v1 · PDF https://arxiv.org/pdf/2611.21979v1
- Authors: Santiago Pineda Montoya, Edisson Gallego González, Jaiberth Porras Barrera, Johan Heriberto Rúa Muñoz
- Categories: math.CO (primary), math.SP
- Comments: 14 pages, 1 figure
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21979.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21979.md

Poignard, Pereira and Pade conjectured that, for a generic choice of the nonzero weights of a given graph, the Fiedler vector of the weighted Laplacian has pairwise distinct coordinates. We give a proof that also covers every nonconstant eigenvector. For each connected graph on n vertices we construct a nonzero homogeneous polynomial with integer coefficients in the edge weights, of degree n(n-1)(n^2-n+2)/4, which vanishes at a positive weighting exactly when the Laplacian has a repeated eigenvalue, an eigenvector with a zero coordinate, or a nonconstant eigenvector with two equal coordinates. The exceptional weights therefore lie in an algebraic hypersurface, which gives structural genericity in the sense of Poignard, Pereira and Pade; algebraically independent weights are never exceptional, and there are good integer weights not exceeding the degree plus one. The polynomial is a product of Krylov determinants. Its nonvanishing follows by induction on trees: when a leaf is attached with a small weight, a cut identity gives the first-order profile of the new eigenvector and separates the coordinates that coincide in the limit. Exact small cases show that exceptional weightings need not be symmetric.

### Perfect matching complexes of antiprism graphs and independence complexes of generalized Petersen graphs $GP(n,2)$

- arXiv: 2611.22021 · https://arxiv.org/abs/2611.22021v1 · PDF https://arxiv.org/pdf/2611.22021v1
- Authors: Youngsoo Kim
- Categories: math.CO (primary)
- Comments: 14 pages, 7 figures, 1 table
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22021.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22021.md

We show that the perfect matching complexes of antiprism graphs and the independence complexes of the generalized Petersen graphs $GP(n, 2)$ are homotopy equivalent to wedges of spheres, and we determine the number and dimensions of the spheres. For the former we compute the initial values of Adamaszek's recursion for the independence complexes of cubes of cycles.

### New necessary conditions on $h$-vectors of simplicial balls

- arXiv: 2611.22026 · https://arxiv.org/abs/2611.22026v1 · PDF https://arxiv.org/pdf/2611.22026v1
- Authors: Luz Elena Grisales Gómez, Satoshi Murai, Isabella Novik
- Categories: math.CO (primary), math.AC
- Comments: 13 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22026.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22026.md

Although the $h$-vectors of simplicial balls of dimension at most $4$ have been completely characterized, much less is known in dimensions $5$ and higher. We establish new necessary conditions on the $h$-vectors of simplicial balls in these dimensions. Together with the necessary conditions of Billera and Lee and the sufficient conditions of Kolins, our results yield a complete characterization of the $h$-vectors of $5$- and $6$-dimensional simplicial balls. We also give a characterization of $h$-vectors of simplicial balls of any dimension with neighborly boundary.

### An improved bound on the strong chromatic index via local flag algebras

- arXiv: 2611.22031 · https://arxiv.org/abs/2611.22031v1 · PDF https://arxiv.org/pdf/2611.22031v1
- Authors: Runze Wang
- Categories: math.CO (primary)
- Comments: Comments are welcome!
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22031.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22031.md

A strong edge coloring is an edge coloring where two edges receive different colors if they are incident or joined by a third edge. For a graph $G$, the strong chromatic index of $G$, denoted by $χ'_s(G)$, is the minimum number of colors needed for a strong edge coloring of $G$. In this paper, using a local flag algebra method, we prove that for every graph $G$ of sufficiently large maximum degree $Δ$, $χ'_s(G)\le 1.642Δ^2$, improving the previous best bound $1.73Δ^2$ due to Davey, Hurley, de Joannis de Verclos, Kang, and Volec.

### FunSearch and Structured SAT Search for Weak Schur Partitions

- arXiv: 2611.22032 · https://arxiv.org/abs/2611.22032v1 · PDF https://arxiv.org/pdf/2611.22032v1
- Authors: Rebecca Vicenzi, Pablo Christofferson, Caleb Hartman, Jingxuan Feng, Suleman Khan, Omar M. Elshinawy, Eric Ramos
- Categories: math.CO (primary)
- Comments: 9 pages, 1 figure, 4 tables
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22032.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22032.md

The weak Schur problem asks how large an interval of consecutive integers can be partitioned into a fixed number of classes with no class containing a monochromatic solution to $a+b=c$ with $a\neq b$. We investigate whether FunSearch, an evolutionary program-search method guided by a large language model, can discover effective construction strategies for this classical combinatorial problem. In our adaptation, FunSearch evolves a priority function used by a fixed greedy solver, while a separate validity check enforces the weakly sum-free condition. This approach matches the known exact values for two, three, and four classes and reaches $WS(5)\geq195$. We then explore a complementary SAT-based approach. Guided by structural information from a 207-element construction communicated by Fred Rowley (Rowley, 2026), our SAT search produces and verifies a distinct valid five-class partition of $\{1,\ldots,207\}$. Thus the strongest construction obtained in this project reaches $WS(5)\geq207$, eleven integers beyond the best published lower bound of 196. The contrast between the two approaches also exposes a limitation of our FunSearch formulation: its greedy solver makes local, irreversible decisions, whereas SAT can enforce global structure across the whole partition.

### Cubic graphs with circumference ratio 21/22 and cyclic connectivity 5

- arXiv: 2611.22037 · https://arxiv.org/abs/2611.22037v1 · PDF https://arxiv.org/pdf/2611.22037v1
- Authors: Ján Mazák
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22037.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22037.md

We construct a cyclically $5$-connected cubic graph of order $22m$ and circumference $21m$ for every $m\geq 3$. Consequently, the shortness coefficient of the class of cyclically $5$-connected cubic graphs is at most $21/22$, improving the previously known upper bound of $24/25$. We also demonstrate how I-reductions, which delete an edge and suppress its two end-vertices, can be used to prove cyclic connectivity.

### Positivity in symmetric webs and block permanents

- arXiv: 2611.22058 · https://arxiv.org/abs/2611.22058v1 · PDF https://arxiv.org/pdf/2611.22058v1
- Authors: Daniel Tubbenhauer
- Categories: math.CO (primary), math.RT
- Comments: 31 pages, many figures, Lean verification available, comments welcome
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22058.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22058.md

We use symmetric webs to prove Marcus's block-permanent inequality for up to four blocks of every size, for five blocks of size at least three, and for any fixed number of blocks above an explicit logarithmic bound on the block size. The proof idea is easy: Bending strands in the Schur relation turns the comparison into a calculation with squared norms.

### Toroidal Obstructions with No K_5 Minor

- arXiv: 2611.22089 · https://arxiv.org/abs/2611.22089v1 · PDF https://arxiv.org/pdf/2611.22089v1
- Authors: Austin Ulrigg
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22089.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22089.md

Finding the complete set of forbidden minors for the torus remains an open problem. We determine the complete list of toroidal minor obstructions with no $K_5$ minor and prove that there are exactly $74$, each with between $10$ and $14$ vertices. Combined with the known classification of toroidal obstructions with no $K_{3,3}$ minor, this determines every toroidal obstruction that excludes one of the forbidden minors for planarity. The proof uses three-vertex cuts to show that, apart from $K_{3,7}$, every three-connected obstruction in this class has two distinct independent triples, each the common neighborhood of at least two degree-three vertices. The classification proceeds by considering the possible intersections of these triples and reduces each case by planarity tests and enumeration of the possible graph forms. From the $74$ minor obstructions we also obtain a complete list of $381$ topological obstructions for the torus with no $K_5$ minor.

### Directed triangles in oriented graphs without a directed cycle of length $3t$

- arXiv: 2611.22104 · https://arxiv.org/abs/2611.22104v1 · PDF https://arxiv.org/pdf/2611.22104v1
- Authors: Shuchao Li, Mingli Wang
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22104.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22104.md

For integers $k,\ell\ge 3$, let $\operatorname{ex}(n,\Cdir_k,\Cdir_\ell)$ denote the maximum number of directed cycles of length $k$ in an $n$-vertex oriented graph containing no directed cycles of length $\ell$. Grzesik, Jaworska, Kielak, Kuc and Ślusarczyk~\cite{GJ} systematically studied the generalized Turán problem for directed cycles and conjectured that, for every fixed integer $t\ge 2$, $\operatorname{ex}(n,\Cdir_3,\Cdir_{3t})=\frac{t-1}{4}n^2+o(n^2)$. They proved this asymptotic formula for $t=2$. In this paper, we prove it for every fixed integer $t\ge 3$, thereby confirming the conjecture.

### Real-Rootedness and Log-Concavity of Zigzag Eulerian Polynomials

- arXiv: 2611.22110 · https://arxiv.org/abs/2611.22110v1 · PDF https://arxiv.org/pdf/2611.22110v1
- Authors: Ethan Torres
- Categories: math.CO (primary), math.CV
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22110.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22110.md

We prove that the zigzag Eulerian polynomials have only real, negative, simple zeros, and hence strictly log-concave coefficients, settling the first two parts of a conjecture of Petersen and Zhuang. Real-rootedness in combinatorics is usually proved inside a single algebraic framework, such as interlacing or stability. Our proof rests on a different premise: different parts of a zero set become visible in different representations of the same polynomial, and classical tools suffice once each part is viewed in the right one. The bridge between representations is a local rule. Forgetting the order in which a bounded-jump path visits positions leaves only a nearest-neighbor condition on sorted gaps, which makes an encoding via a transfer matrix much simpler to see. From there the argument passes to complex analysis. The sizes of the matrix's eigenmodes locate the zeros at the two ends of the negative axis, through Rouché's theorem. In a logarithmic coordinate the generating function becomes a combination of derivatives of the hyperbolic secant, akin to the classical derivative polynomials, and the arguments of its nearest poles produce a sine that fixes the signs between consecutive central zeros. The zeros are thus read off from the poles of an associated kernel. More broadly, the proof suggests that combinatorial polynomials defined by local constraints carry analytic structure, in their spectra and in the poles of their kernels, that is complementary to the usual algebraic methods and that classical complex analysis can exploit directly.

### On Threshold Probabilities for the Stability of the Independence Number of a Random Subgraph

- arXiv: 2611.22185 · https://arxiv.org/abs/2611.22185v1 · PDF https://arxiv.org/pdf/2611.22185v1
- Authors: Vsevolod A. Pokhachevskiy, Andrei Raigorodskii
- Categories: math.CO (primary), math.PR
- Comments: 18 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22185.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22185.md

For an arbitrary sequence of graphs $G_n$, we consider a random spanning subgraph $G_{n,p}$ in which each edge of the graph $G_n$ survives independently of the others with probability $p$. We obtain a general upper bound for the independence number $α(G_{n,p})$, from which, for an arbitrary probability $p=p(n)$, we derive sufficient conditions for asymptotic stability, i.e., for the equality $α(G_{n,p})=(1+o(1))α(G_n)$ asymptotically almost surely, as well as upper bounds for the independence number of the random subgraph, including unconditional ones; for $p=1/2$ they recover A. M. Raigorodskii's results of 2017 and 2026. Under additional conditions on the structure of the independent sets of the graph $G_n$, we find, up to a constant factor, the threshold probabilities for both asymptotic and exact stability (the equality $α(G_{n,p})=α(G_n)$). Special cases include results on the graphs $G(n,r,<s)$ for growing $r$ and $s$, including Kneser graphs for growing $r$; we also give examples of complete multipartite graphs, graphs on the blocks of Steiner systems, and $q$-analogues of Kneser graphs.

### More lower bounds for Hales--Jewett and van der Waerden numbers

- arXiv: 2611.22205 · https://arxiv.org/abs/2611.22205v1 · PDF https://arxiv.org/pdf/2611.22205v1
- Authors: Younes Mouhib
- Categories: math.CO (primary), cs.DM
- Signals: code https://github.com/ysmouhib/hj-vdw-reproducibility (no Lean project)
- Comments: 6 pages. Explicit certificates, search algorithms, and verification code are available at https://github.com/ysmouhib/hj-vdw-reproducibility and in the ancillary files
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22205.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22205.md

We give explicit colourings improving the comparison lower bounds assembled here for several Hales--Jewett and van der Waerden numbers. The main algebraic tool generalises Rabung's power-residue colouring from arithmetic progressions to arbitrary sets. If every translate of a t-element set S in F_p meets at least two classes of the r-th power character, and the integer weights have both parities, then a period-2p one-weight colouring of [t]^p has no monochromatic combinatorial line. The 19 displayed algebraic certificates comprise 18 improvements and one closed-form reproduction; they include HJ(4,3)>=164, HJ(5,4)>=7418, and HJ(5,6)>=34034. The underlying period-p construction also proves kappa_ow(t,r)>=p-1 for the one-weight bracket ceiling, in particular kappa_ow(5,4)>=7416 and kappa_ow(5,6)>=34032. Warm breakout-weighted tabu search on the type simplex gives HJ(3,4)>=51. Whole-colouring local search gives W(8,3)>522, W(11,3)>1193, and W(17,3)>3620. All accepted certificates are available separately and are checked by direct enumeration; unresolved searches are reported as UNKNOWN, not UNSAT.

### Between proper and strong edge-colorings of graphs with maximum degree at most four

- arXiv: 2611.22254 · https://arxiv.org/abs/2611.22254v1 · PDF https://arxiv.org/pdf/2611.22254v1
- Authors: Aistis Atminas, Xujun Liu, Zihui Xu
- Categories: math.CO (primary)
- Comments: 12 pages, 8 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22254.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22254.md

A $(1^j,2^k)$-packing edge-coloring of a graph $G$ is a partition of its edge set $E(G)$ into $j$ matchings and $k$ induced matchings. It can be viewed as intermediate colorings between proper and strong edge-coloring. The study of this topic on subcubic graphs has drawn considerable attention recently, with many conjectures and open problems proposed and resolved. However, very few results are known for graphs with maximum degree four or more. Henderson, Kennedy, and Santana showed that every graph with degree at most four has a $(1,2^{19})$-packing edge-coloring and a $(1^2,2^{17})$-packing edge-coloring. In this paper, we improve the results of Henderson, Kennedy, and Santana by showing every graph with degree at most four has a $(1,2^{17})$-packing edge-coloring. As a corollary of our result, every graph with degree at most four has a $(1^2,2^{16})$-packing edge-coloring.

### The Zaks--Perles--Wills volume conjecture I: three-dimensional lattice polytopes

- arXiv: 2611.22337 · https://arxiv.org/abs/2611.22337v1 · PDF https://arxiv.org/pdf/2611.22337v1
- Authors: Feihu Liu, Jinlong Tang, Sihao Tao, Zihao Zhang
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22337.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22337.md

We prove the three-dimensional Zaks--Perles--Wills volume bound for lattice polytopes with $k\ge3$ interior lattice points: the Euclidean volume of such a lattice polytope is at most $6(k+1)$, with equality if and only if the polytope is affinely unimodularly equivalent to $\operatorname{conv}(0,2e_1,3e_2,6(k+1)e_3)$. The inequality is strict when the minimum lattice width is at least three. Together with the known cases $k=1,2$, this completely resolves the three-dimensional Zaks--Perles--Wills volume conjecture.

### Minimum degree thresholds for even cycle residues

- arXiv: 2611.22346 · https://arxiv.org/abs/2611.22346v1 · PDF https://arxiv.org/pdf/2611.22346v1
- Authors: Hojin Chu, Masaki Kashima, Shun-ichi Maezawa, Boram Park
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22346.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22346.md

Dean's conjecture asserts that, for every integer $m\ge3$, every graph of minimum degree at least $m$ has a cycle whose length is divisible by $m$. This degree bound is best possible for odd $m$. For every integer $k\ge2$, we prove that every graph of minimum degree at least $2k-1$ has a cycle whose length is congruent to $r$ modulo $2k$ for every even $r\not\equiv2\pmod{2k}$. Consequently, $2k-1$ is the sharp minimum degree threshold for a cycle whose length is divisible by $2k$. For bipartite graphs, we prove that minimum degree at least $k$ guarantees the same residue classes for every $k\ge4$, and we characterize their end-blocks when no cycle has length congruent to $2$ modulo $2k$. The bipartite degree bound is also sharp, and the exclusion of residue $2$ is necessary even for connected graphs of arbitrarily large order.

### A sharp minimum degree condition for Hamiltonicity in line graphs of 3-hypergraphs

- arXiv: 2611.22507 · https://arxiv.org/abs/2611.22507v1 · PDF https://arxiv.org/pdf/2611.22507v1
- Authors: Kenta Ozeki, Leilei Zhang
- Categories: math.CO (primary)
- Comments: 11 pages. Comments are welcome!
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22507.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22507.md

Let $G$ be the line graph of a $3$-hypergraph, and let $n$ be its order. We prove that if $G$ is $3$-connected, $n\ge4936$, and $δ(G)\ge(n+5)/10$, then $G$ is Hamiltonian if and only if it does not belong to an explicitly described family of exceptional graphs. This extends the sharp minimum degree bound of Lai, Shao, and Zhan for $3$-connected claw-free graphs beyond the claw-free setting, since line graphs of $3$-hypergraphs may contain induced claws. The coefficient $1/10$ cannot be decreased, and the constant $5$ in the numerator cannot be replaced by $4$.

### Flip Combinatorial Invariance for flipclasses with small residues

- arXiv: 2611.22528 · https://arxiv.org/abs/2611.22528v1 · PDF https://arxiv.org/pdf/2611.22528v1
- Authors: Francesco Esposito, Mario Marietti, Giovanni Paolini
- Categories: math.CO (primary), math.RT
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22528.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22528.md

We establish (Normal) Flip Combinatorial Invariance for flipclasses with no residues longer than 8. Actually, we show more generally that all flipclasses of finite type with no residues longer than 8 have only one increasing path. For flipclasses of Weyl type, these are precisely the flipclasses having only one increasing path. This marks a refinement of the classical Combinatorial Invariance of Kazhdan--Lusztig polynomials.

### Asymptotic enumeration of histories and limit laws in two random graph evolution models

- arXiv: 2611.22535 · https://arxiv.org/abs/2611.22535v1 · PDF https://arxiv.org/pdf/2611.22535v1
- Authors: Nadja Azzouz, Olivier Bodini, Francis Durand, Bernhard Gittenberger
- Categories: math.CO (primary), math.PR
- Comments: 37 pages, 1 figure
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22535.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22535.md

We study growth models for random graphs where the growth is established by vertex or edge creations and where there is no dependence between vertices and edges. Creations are logged by time stamps such that the history of the resulting graph can be reconstructed. We investigate two prototypical models, an undirected and a directed one, called undirected independent growth model (UIG-model) and directed independent growth model (DIG-model). The generating functions for the number of histories have radius of convergence equal to zero. In the UIG-model, we express the asymptotic number of histories as a sum that is amenable to the discrete Laplace method. We derive the asymptotic number of histories, study the number of vertices of a random history, and prove a central limit theorem. In the DIG-model we use a rescaled Borel transform to get an entire function. Then we show that this function is Hayman admissible, which enables us to derive the asymptotic number of histories in this model. The counting sequence is closely related to the framework of generalized Legendre-Stirling numbers. To determine the number of vertices in a random history, we prove that the bivariate generating function is e-admissible and infer that again a normal limit law holds. Finally, we discuss a correspondence to set partitions with even block sizes and present an algorithm based on Boltzmann samplers that generates such graphs uniformly at random.

### On (Pathwidth, Clique)-boundedness

- arXiv: 2611.22552 · https://arxiv.org/abs/2611.22552v1 · PDF https://arxiv.org/pdf/2611.22552v1
- Authors: Amir Nikabadi
- Categories: math.CO (primary), cs.DM
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22552.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22552.md

We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor $K_{σ,σ}$ as an induced minor, where $\B_ρ$ is the complete binary tree of height $ρ$ and the bound depends only on $ρ$ and $σ$. We then obtain an asymptotically sharp bound on the path-independence number of $n$-vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest $F$ and every $\ell\in\N$, there is a constant $k=k(F,\ell)\in\N$ such that every graph $G$ with no induced theta or $\ell$-long prism and no induced subgraph isomorphic to $F$ satisfies tree-independence number at most $k$. This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer $s\ge2$, we characterize the forests $F$ for which excluding $F$ as an induced minor and $K_{s,s}$ as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with $K_{s,s}$ excluded as a subgraph.

### The Cooperstein conjecture and additive alternating $d$-codes

- arXiv: 2611.22622 · https://arxiv.org/abs/2611.22622v1 · PDF https://arxiv.org/pdf/2611.22622v1
- Authors: Paolo Santonastaso
- Categories: math.CO (primary), math.RA
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22622.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22622.md

Let $\bigwedge^2 V$ be the second exterior power of a vector space $V$ over a finite field. The Cooperstein conjecture asserts a dimension bound for flats external to varieties consisting of points of bounded rank in $\mathrm{PG}(\bigwedge^2 V)$. This geometric problem can be translated into a question about linear spaces of alternating matrices whose nonzero elements have rank at least a prescribed value. For matrices of odd order, the sharp cardinality bound was already established by Delsarte and Goethals (1975). In this paper, we prove the Cooperstein conjecture for matrices of even order and, more generally, we prove its additive analogue by determining, for all admissible parameters, the maximum size of an additive subgroup of alternating matrices in which every nonzero matrix has at least the prescribed rank. Our proof uses Pfaffian equations to characterize alternating matrices of rank below the prescribed minimum. We study the minimal graded free resolutions of the corresponding Pfaffian rings. The Cohen--Macaulay property and the $a$-invariant of each Pfaffian ring determine the largest shift in its resolution. We use trace functions on evaluation quotients to construct polynomial indicators for the matrices of small rank in an additive subgroup. The largest shift controls their degrees, yielding the upper bound by a counting argument. Finally, we give explicit trace constructions attaining the bound.

### Golomb rulers with real marks: the real and integer optima agree up to ten marks

- arXiv: 2611.22656 · https://arxiv.org/abs/2611.22656v1 · PDF https://arxiv.org/pdf/2611.22656v1
- Authors: Esther Notik
- Categories: math.CO (primary)
- Comments: 9 pages, 5 tables. Programs, proof files and exact checkers: https://doi.org/10.5281/zenodo.23843508
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22656.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22656.md

A Golomb ruler is a set of integer marks whose pairwise differences are distinct. We let the marks be real numbers and ask that every difference be at least 1 and that any two differences be at least 1 apart. Every integer Golomb ruler satisfies these conditions, so the least length $G_R(n)$ of such a real ruler with $n$ marks is at most the optimal Golomb length $G_Z(n)$. Fixing the order of all differences splits the real problem into finitely many polyhedral chambers. A branch-and-bound over these chambers, with an exact rational certificate at every leaf, proves $G_R(n) = G_Z(n)$ for $n \le 10$. Each proof takes under a minute and is verified by an independent checker that uses only exact arithmetic. An exhaustive exact enumeration of all chamber vertices confirms the result for $n \le 7$, and shows that there the shortest real rulers are exactly the optimal integer rulers and their mirror images. For every $n$ we show $n(\sqrt{n}-1)^2 \le G_R(n) \le G_Z(n)$, so that $G_R(n) \sim G_Z(n) \sim n^2$. Non-integral chamber vertices first appear at $n = 7$: there are 84, all half-integral. Already there, 80 of them are shortest points of their chambers, 40 of them the only one, although the global optimum is integral; a twelve-mark example of the same kind comes from Singer's construction. On the other hand, every Singer ruler with at most 104 marks, cut at the largest gap, is the only shortest point of its own chamber; we conjecture this for all prime powers.

### The minimum degree of minimally k-extendable graphs for some k

- arXiv: 2611.22690 · https://arxiv.org/abs/2611.22690v1 · PDF https://arxiv.org/pdf/2611.22690v1
- Authors: Zhiyong Gan, Yi Huang
- Categories: math.CO (primary)
- Comments: 12 pages, 1 figure. Submitted to Graphs and Combinatorics
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22690.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22690.md

A graph on at least 2k+2 vertices is k-extendable if every matching of size k extends to a perfect matching, and it is minimally k-extendable if it is k-extendable but deleting any edge is not. Plummer proved that every k-extendable graph is (k+1)-connected. So its minimum degree is at least k+1. Lou and Yu conjectured that a minimally k-extendable graph on at most 4k vertices has minimum degree in {k+1,2k,2k+1}; the case k=1 and the claw-free case of k=2 have been settled previously. We determine the minimum degree of minimally k-extendable graphs for k=2 and k=3, thereby settling the Lou--Yu conjecture for these two values. For k=2 the minimum degree is in {3,4,5}. For k=3 it is in {4,7} at orders 8 and 10, and in {4,6,7} at order 12. The proofs pass to the complement graph and combine Tutte's perfect matching theorem with a classification of four-vertex and six-vertex obstructions. All predicted values are realized by explicit constructions.

### Positivity of Signed Odd-Multiplicity Partitions

- arXiv: 2611.22720 · https://arxiv.org/abs/2611.22720v1 · PDF https://arxiv.org/pdf/2611.22720v1
- Authors: Mircea Merca
- Categories: math.CO (primary)
- Comments: 10 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22720.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22720.md

We establish coefficientwise nonnegativity for the signed partition $q$-series \[ A_k(q)= \sum_{1\le j_1<\cdots<j_k} \prod_{i=1}^k\frac{q^{j_i}}{1+q^{2j_i}} =\sum_{n\ge0}a_k(n)q^n, \qquad k\ge0, \] with $A_0(q)=1$. The coefficient $a_k(n)$ counts, with signs, partitions of $n$ having exactly $k$ distinct part sizes, each occurring with odd multiplicity. A partition with multiplicities $2t_1+1,\ldots,2t_k+1$ is assigned the sign $(-1)^{t_1+\cdots+t_k}$. We prove that $a_k(n)\ge0$ for all $k,n\ge0$, thereby resolving a conjecture on signed odd-multiplicity partitions. Our proof combines a positive theta--MacMahon factorization for the generating functions restricted to odd part sizes with a dyadic product decomposition that extends positivity to arbitrary part sizes. Moreover, we establish strict positivity $a_k(n)>0$ for every $k\ge2$ and $n\ge\binom{k+1}{2}$.

### Sharp lower bounds for weighted bisections of graphs with bounded maximum degree

- arXiv: 2611.22760 · https://arxiv.org/abs/2611.22760v1 · PDF https://arxiv.org/pdf/2611.22760v1
- Authors: Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou
- Categories: math.CO (primary), cs.DM
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22760.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22760.md

A bisection of a graph is a partition of its vertex set into two parts the sizes of which differ by at most one. We prove that every finite simple graph of maximum degree at most an odd positive integer $k$, with arbitrary nonnegative real edge weights, has a bisection of weight at least $(k+1)/(2k)$ times its total edge weight. The corresponding bound $(k+2)/(2(k+1))$ for even $k$ follows immediately. Both coefficients are best possible. Somewhat surprisingly, these are exactly the sharp coefficients known for maximum weighted cuts, despite the additional balance requirement.

### Heap-type permutation generation with a prescribed final arrangement

- arXiv: 2611.22780 · https://arxiv.org/abs/2611.22780v1 · PDF https://arxiv.org/pdf/2611.22780v1
- Authors: Luís M. S. Russo
- Categories: math.CO (primary), cs.DM, cs.DS
- Comments: 22 pages. Software archived at https://doi.org/10.5281/zenodo.24311260
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22780.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22780.md

Heap's algorithm generates all permutations of an array of n items, obtaining each one from its predecessor by a single swap. We determine the net permutation applied to the array by every complete recursive call: a transposition when the number of items is odd and at least three, and a cycle through all items when it is even. We show that the output of each call is a concatenation of right cosets of the symmetric group on one item fewer, and we prove a general formula: the order in which the items are parked at the last position may be chosen freely, every such order corresponds to exactly one valid schedule, and it determines the net permutation of the call. Two variants follow. In the cyclic variant a complete sweep over an even number of items rotates the array by one position. In the extremal variant, for even n, a sweep started from the identity ends in the lexicographically largest arrangement that any single-swap enumeration can leave; by a parity argument this is the reversal exactly when n is congruent to 2 modulo 4. The construction of the extremal variant is proved correct when n is divisible by 4 and verified by computer for all even n up to 10000.

### An extremal question of Erdős et al. on cycles

- arXiv: 2611.22824 · https://arxiv.org/abs/2611.22824v1 · PDF https://arxiv.org/pdf/2611.22824v1
- Authors: Zhiyong Gan, Zhiliang Tan, Yi Huang
- Categories: math.CO (primary)
- Comments: 31 pages, 2 figures, submitted to Journal of Combinatorial Theory, Series B
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22824.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22824.md

This paper addresses an extremal problem on long cycles proposed by Erdős, Faudree, Schelp and Simonovits in 1989. Let \(2\le k\le d<n\) be positive integers. For an n-vertex simple graph G, let \(θ_+^G\) count vertices of degree at least d, and \(C_{\ge k+1}\) denote a cycle of length at least \(k+1\). The original conjecture claimed that G contains a \(C_{\ge k+1}\) whenever \(θ_+^G \ge \lfloor k/2 \rfloor \lfloor (n-1)/d \rfloor+2\). Li, Ma and Ning disproved it with infinite counterexamples and gave linear lower bounds. Gan, Yi and Jiang later obtained piecewise sufficient conditions depending on the parity of k, whose bounds are sharp only when \(k=d\) and loose for \(k\ne d\). We derive a new sufficient condition for \(C_{\ge k+1}\). For odd \(k=d\), we use Woodall's sharp bound \(θ_+^G \ge k(n-2)/(2(k-1))+1\). For all other admissible parameters, our threshold is unified and independent of the parity of k: \(θ_+^G \ge \lfloor k/2 \rfloor (n-1)/d + (n-d-1)\lfloor k/2 \rfloor/(d(d-\lfloor k/2 \rfloor))+1\). We construct \(C_{\ge k+1}\)-free graphs to prove tightness for all admissible k. This resolves this long-standing Erdős-type extremal problem concerning high-degree vertices and long cycles.

### Independent sets in the 2-token graph of a cycle and kings on the torus

- arXiv: 2611.22830 · https://arxiv.org/abs/2611.22830v1 · PDF https://arxiv.org/pdf/2611.22830v1
- Authors: Luis Manuel Rivera
- Categories: math.CO (primary)
- Comments: 12 pages, 1 figure
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22830.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22830.md

The 2-token graph of the cycle $C_n$ and the king graph on the $n\times n$ torus are known to have the same independence number. Answering a question of Reyes, Dalfó and Fiol, for every $n\ge4$ we give an explicit bijection between a maximum independent set of the king graph and a maximum independent set of the $2$-token graph: each pair of tokens is represented by a king placed in the row of one of its two tokens and in the column given by their sum. We also show that the $2$-token graph of $C_n$ has exactly one maximum independent set, or exactly $n$ when $n\equiv3\pmod 4$, all of them rotations of each other. The argument is self-contained and yields a new proof of the value of the independence number.

### Equivalence of Small and Large Quasi-kernels

- arXiv: 2611.22881 · https://arxiv.org/abs/2611.22881v1 · PDF https://arxiv.org/pdf/2611.22881v1
- Authors: Sam Spiro
- Categories: math.CO (primary)
- Comments: 11 pages. The proofs are due to Astra 6, the writing is our own. Comments welcome!
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22881.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22881.md

A quasi-kernel of a digraph $D$ is an independent set which can reach every vertex of $D$ by a directed path of length at most 2. The Small Quasi-kernel Conjecture states that every $n$-vertex source-free digraph $D$ contains a quasi-kernel $Q$ with $|Q|\le n/2$, and the Large Quasi-kernel Conjecture states that every $n$-vertex digraph $D$ contains a quasi-kernel $Q$ with $|N^+[Q]|\ge n/2$. Our main result shows for any $\frac{1}{2}<β<1$ an equivalence between the following two statements: \[\textrm{Every }n\textrm{-vertex source-free digraph contains a quasi-kernel with } |Q|\le n-Ω(n^β).\] \[\textrm{Every }n\textrm{-vertex digraph contains a quasi-kernel with } |N^+[Q]|\ge Ω(n^{2-\frac{1}β}).\] That is, any sublinear bound for one problem is equivalent to a corresponding sublinear bound for the other. This combined with previous work establishing an equivalence for linear bounds shows that the two problems are largely equivalent to each other. We additionally give a slight refinement to the recent breakthrough of Rutschmann for these problems which, together with the result above, gives the best known bounds of $n-Ω(n^{3/4})$ and $Ω(n^{2/3})$ for the Small and Large Quasi-kernel Conjectures, respectively. Our proofs are due to ChatGPT's Astra 6; the writing is all our own.

### Minimum outdegree forcing directed cycles

- arXiv: 2611.22909 · https://arxiv.org/abs/2611.22909v1 · PDF https://arxiv.org/pdf/2611.22909v1
- Authors: Andrzej Grzesik, Justyna Jaworska, Piotr Kuc
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22909.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22909.md

The Caccetta-Häggkvist conjecture, one of the best known open problems on oriented graphs, asserts that every oriented graph on $n$ vertices with minimum outdegree at least $n/\ell$ contains a directed cycle of length at most $\ell$. Motivated by it, Kelly, Kühn and Osthus asked for the minimum degree condition that forces a directed cycle of length exactly $\ell$. The semidegree version of this problem was recently solved, but the methods used there rely on bounding the directed diameter, which requires control over the indegrees. In the setting of the Caccetta-Häggkvist conjecture, where only the outdegrees are bounded, the answer was known only for $\ell$ not divisible by $3$. We determine the optimal minimum outdegree forcing a directed cycle of length $\ell$ for every sufficiently large $\ell$ and $n$. This establishes the outdegree version of the Kelly-Kühn-Osthus conjecture for all large $\ell$, up to a small correction of the additive term, which in general cannot be avoided.

### Sums and Products in Dynamically Central Syndetic Sets

- arXiv: 2611.22957 · https://arxiv.org/abs/2611.22957v1 · PDF https://arxiv.org/pdf/2611.22957v1
- Authors: Arpita Ghosh
- Categories: math.CO (primary), math.DS
- Comments: Comments are welcome
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22957.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22957.md

Glasscock and Le introduced the notion \textit{dynamically central syndetic sets} in a minimal topological dynamical system under the minimal action of the semigroup $(\mathbb{N}, +).$ In this short note, we introduce these large sets in the semigroup $(\mathbb{N}, \cdot)$ and establish that dynamically central syndetic sets contain the Hindman configuration $\{x,y,x+y,xy\}$. Furthermore, we show that there are dynamically central piecewise syndetic sets that do not contain such configurations.

### Complete characterization of graphs with common maximal abelian cover

- arXiv: 2611.22993 · https://arxiv.org/abs/2611.22993v1 · PDF https://arxiv.org/pdf/2611.22993v1
- Authors: Frederico Cançado, Gabriel Coutinho, Thomás Jung Spier
- Categories: math.CO (primary), math.AT
- Comments: 29 pages, 1 figure. Comments welcome
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22993.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22993.md

The maximal abelian cover of a connected graph is the quotient of its universal cover by the commutator subgroup of its fundamental group. We provide a complete classification of finite connected graphs with isomorphic maximal abelian covers. For trees or for connected graphs with at least two cycles, the cover determines the base up to isomorphism; in cycle rank one, it determines the primitive cyclic pattern of rooted trees attached to the unique cycle. We also characterize when every automorphism descends to the base and give an orbit-size criterion for splitting the canonical lift extension, answering two questions raised by Baez in 2026.

### An infinite family of bipartite hypotraceable graphs

- arXiv: 2611.23018 · https://arxiv.org/abs/2611.23018v1 · PDF https://arxiv.org/pdf/2611.23018v1
- Authors: Jorik Jooken
- Categories: math.CO (primary)
- Comments: 12 pages, 4 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.23018.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.23018.md

A graph is hypotraceable if it has no Hamiltonian path but every vertex-deleted subgraph does. In 1978, Grötschel asked whether a bipartite hypotraceable graph exists. We resolve this long-standing question in a strong sense by proving that such graphs exist for every sufficiently large even order. Moreover, we show that bipartite hypotraceable graphs can have $\left(1/4+o(1)\right)n^2$ edges, asymptotically attaining the maximum possible number of edges of a bipartite graph, and that there are at least $2^{(1/4+o(1))n^2}$ nonisomorphic examples of order $n$, as $n$ tends to infinity through even integers. Finally, we prove that every bipartite graph occurs as an induced subgraph of a bipartite hypotraceable graph.

### Divisible design graphs from a construction of antipodal distance-regular graphs based on Ree groups and Suzuki groups

- arXiv: 2611.23077 · https://arxiv.org/abs/2611.23077v1 · PDF https://arxiv.org/pdf/2611.23077v1
- Authors: Bart De Bruyn, Sergey Goryainov, Yilin Xie
- Categories: math.CO (primary), math.GR
- Comments: 15pp
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.23077.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.23077.md

In this paper, we present a new construction of divisible design graphs with new parameters, obtained by plugging a difference set into a known construction of antipodal distance-regular graphs of diameter 3 that is based on Ree groups and Suzuki groups.

### New bounds on simplex-avoiding sets in two dimensions

- arXiv: 2611.23097 · https://arxiv.org/abs/2611.23097v1 · PDF https://arxiv.org/pdf/2611.23097v1
- Authors: Domonkos Czifra, Ákos Dúcz, Péter Madarasi, Dániel Varga, Pál Zsámboki
- Categories: math.CO (primary)
- Comments: 16 pages, 3 figures, 2 tables. Exact rational certificates and verification code available at https://users.renyi.hu/~akos/triangles/triangle_reproduction/site/
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.23097.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.23097.md

We study extremal densities of measurable subsets of metric spaces avoiding prescribed finite geometric configurations. We prove two new upper bounds for three-point avoidance problems: a measurable subset of $S^2$ containing no orthonormal basis has normalized spherical measure at most $7/11$, and a measurable subset of $\mathbb{R}^2$ containing no unit equilateral triangle has upper Banach density at most $9/16$. The first bound appears to be the first improvement over the trivial averaging bound for this problem, while the second improves the previously best known upper bound. The proofs are applications of the geometric fractional chromatic number method introduced by Ambrus et al. For this purpose, we formulate the method in a framework that applies both to compact homogeneous spaces and to Euclidean spaces with upper Banach density.

### Determining Compatible Groups in $Γ$-Zonal Labelings

- arXiv: 2611.23164 · https://arxiv.org/abs/2611.23164v1 · PDF https://arxiv.org/pdf/2611.23164v1
- Authors: Andrew Bowling, Richard M. Low
- Categories: math.CO (primary)
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.23164.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.23164.md

Let $G$ be a plane graph with vertex, edge, and region sets $V(G),$ $E(G),$ and $F(G)$ respectively, and let $Γ$ be a nontrivial abelian group with identity element $0$. A $Γ$-zonal labeling of a plane graph $G$ is a labeling $\ell: V(G)\rightarrow Γ\setminus\{0\}$ such that for every region $f\in F(G)$, the sum of labels on the boundary of $f$ is $0$ in $Γ$. We say a $Γ$-zonal labeling is generative if the labels used generate $Γ$, and strong if the additive order of each label matches the degree of the corresponding vertex. Given a graph $G$ or a family of graphs $\mathcal{G}$, we explore restrictions on the groups $Γ$ for which there can exist a $Γ$-zonal labeling. Here we specifically determine restrictions on compatible groups when $\mathcal{G}$ is the family of $2$-connected multigraphs or $2$-connected simple graphs. We also demonstrate how the Smith normal form decomposition of the face incidence matrix of a plane graph $G$ can help characterize the groups $Γ$ for which there exists a generative $Γ$-zonal labeling.

### On the V-toothpick sequence

- arXiv: 2611.23172 · https://arxiv.org/abs/2611.23172v1 · PDF https://arxiv.org/pdf/2611.23172v1
- Authors: Benoît Cloitre
- Categories: math.CO (primary), math.NT
- Comments: 33 pages, 6 figures. Python code and numerical data included as ancillary files
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.23172.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.23172.md

We give a generating function for the V-toothpick sequence and an algorithm that computes any term in time polynomial in the number of binary digits of its index. We determine its quadratic growth and periodic fluctuations, and give convergent series for the constants in its asymptotic bounds.

### Sidorenko Inequalities in Oriented Graphs

- arXiv: 2611.23222 · https://arxiv.org/abs/2611.23222v1 · PDF https://arxiv.org/pdf/2611.23222v1
- Authors: Veronica Bitonti, Emma Hogan, Jonathan A. Noel, Dmitry Tsarev
- Categories: math.CO (primary)
- Comments: 27 pages, 3 figures. Comments welcome
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.23222.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.23222.md

We introduce relative Sidorenko and relative anti-Sidorenko inequalities for oriented graphs, strengthening the corresponding well-studied notions for tournaments by allowing arbitrary host graphs. An orientation $\vec H$ of a graph $H$ is relatively Sidorenko if $\hom(\vec H,\vec G) \ge 2^{-e(H)}\hom(H,G)$ for every oriented graph $\vec G$ with underlying graph $G$, and relatively anti-Sidorenko if the reverse inequality holds. We provide a complete characterisation of the class of connected relatively Sidorenko graphs in terms of weakly norming graphs, and exhibit several families of relatively Sidorenko and relatively anti-Sidorenko oriented graphs. Despite the substantially stronger definitions, many known tournament Sidorenko and anti-Sidorenko examples satisfy the relative inequalities, suggesting a broader theory of these phenomena in arbitrary host graphs and motivating several new structural and classification problems.

### The system of length sets of transfer Krull monoids over $C_3 \oplus C_3 \oplus C_3$

- arXiv: 2611.21699 · https://arxiv.org/abs/2611.21699v1 · PDF https://arxiv.org/pdf/2611.21699v1
- Authors: Alfred Geroldinger, Benjamin Hackl, Qinghai Zhong
- Categories: math.GR (primary), math.AC, math.CO, math.NT
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21699.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21699.md

Let $H$ be a Krull monoid with class group $G$ and suppose that each class contains a prime divisor. There are precisely nine groups (up to isomorphism) for which the set of distances of $H$ is contained in $\{1, 2\}$. For all these groups, except for $C_3 \oplus C_3 \oplus C_3$, the system of length sets has been written down explicitly. In this paper we close this gap and determine the system of length sets when the class group is isomorphic to $C_3 \oplus C_3 \oplus C_3$.

### Permutation groups, derangements and connections

- arXiv: 2611.21894 · https://arxiv.org/abs/2611.21894v1 · PDF https://arxiv.org/pdf/2611.21894v1
- Authors: Scott Harper
- Categories: math.GR (primary), math.CO
- Comments: 69 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21894.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21894.md

What is the chance that a random shuffling of a deck of cards leaves no card in its original place? More precisely, what is the chance that a random permutation has no fixed points? A permutation with no fixed points is known as a derangement. Questions about derangements, like the ones above, go back centuries, but there are also several unsolved problems in this very active area of permutation group theory. Based on a minicourse given at "Groups and Algebras in Bicocca for Young Algebraists" in June 2026, this survey provides a general introduction to permutation group theory, with a specific focus on derangements. The survey features modern methods for studying permutation groups, recent developments and open problems concerning derangements and connections between this topic and other areas, such as combinatorics, graph theory, number theory, representation theory and topology.

### Enumerating orbits of finite classical groups on their Lie algebras

- arXiv: 2611.22082 · https://arxiv.org/abs/2611.22082v1 · PDF https://arxiv.org/pdf/2611.22082v1
- Authors: Jason Fulman, Robert M. Guralnick, Richard Stong
- Categories: math.GR (primary), math.CO
- Comments: 31 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22082.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22082.md

We enumerate the orbits of a finite classical group in the adjoint action on its Lie algebra, giving exact generating functions and very good upper bounds. We treat the general linear, unitary, symplectic and orthogonal groups, in both odd and even characteristic. In even characteristic, we get very nice formulas for the number of orbits on nilpotent classes both in the finite and algebraically closed case. We discuss the connection with commuting varieties.

### An upper bound on non-overlapping codes

- arXiv: 2611.21913 · https://arxiv.org/abs/2611.21913v1 · PDF https://arxiv.org/pdf/2611.21913v1
- Authors: Simon R. Blackburn
- Categories: cs.IT (primary), math.CO
- Comments: 22 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21913.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21913.md

Non-overlapping codes (also known as bifix-free codes or strong comma-free codes) have now been studied for over 60 years as part of information theory, with regular new applications appearing and much recent interest. Let $X$ be a binary non-overlapping code of length $n$. The paper contains a self-contained proof that \[ |X|\leq \left(\frac{5}{6e} +O(n^{-1})\right)\frac{2^n}{n} \] as $n\rightarrow\infty$. This improves, by a factor of $5/6$, the best previously known bound due to Levenshtein (1970). The paper builds on work by Fimmel, Michel, Pirot, Sereni and Strüngmann (2019), and by Stanovnik, Mo\v skon and Mraz (2024).

### On Contractibility of Geometric Joins

- arXiv: 2611.22182 · https://arxiv.org/abs/2611.22182v1 · PDF https://arxiv.org/pdf/2611.22182v1
- Authors: Dohyeon Lee
- Categories: math.MG (primary), math.CO
- Comments: 3 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22182.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22182.md

The geometric join of a family of sets in $\mathbb R^d$ is the union of the convex hulls of all colorful sets. For every $d \geq 4$, we construct $\lceil\frac{(d-1)^2}{2}\rceil$ sets in $\mathbb R^d$ whose geometric join is not contractible, disproving the conjecture of Bárány, Holmsen, and Karasev that the geometric join of at least $d+1$ sets is contractible.

### Tilings of integer sets of prime-power cardinality

- arXiv: 2611.22849 · https://arxiv.org/abs/2611.22849v1 · PDF https://arxiv.org/pdf/2611.22849v1
- Authors: Wenchuan Hu, Chao Wang, Erxiao Wang, Fuhai Zhu
- Categories: math.NT (primary), math.CO
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22849.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22849.md

Let $A$ be a finite integer tile of cardinality $p^k$, where $p$ is prime and $k\geq1$. We first determine all possible fundamental periods of tilings of $A$. A cyclotomic argument gives a common period $PD$, where $P$ is a power of $p$ and $D$ is a greatest common divisor of normalized differences in $A$. Each $Pd$ with $d\mid D$ occurs as a fundamental period. At modulus $Pd$, a chain of greatest common divisors controls the compatibility of the Chinese remainder fibres. This yields independent digit functions and exact counts of the tilings. For tilings of fundamental period $Pd$, we classify their partitions into translates modulo $Pd$ and count the tilings that induce each partition. The same arithmetic data classify tiles with identical tiling families. Each class has a unique normalized tile of minimum diameter whose mask polynomial divides the masks of all normalized tiles in the class.

### Obstructions to Hadamard Deformations of Fourier Matrices

- arXiv: 2611.21871 · https://arxiv.org/abs/2611.21871v1 · PDF https://arxiv.org/pdf/2611.21871v1
- Authors: Shuler Hopkins, Remus Nicoara
- Categories: math.OA (primary), math.CO
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21871.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21871.md

We study deformations of the Fourier spin model commuting square in the space of commuting squares, or equivalently deformations of the matrix $\sqrt nF_n$, where $F_n$ denotes the Fourier matrix, by complex Hadamard matrices. If $n$ is neither a prime power nor twice a prime, we show that there exist unit vectors in the enveloping tangent space that cannot be realized as directions of convergence of sequential deformations. Consequently, the derivative of any differentiable Hadamard family through $\sqrt nF_n$ has rank strictly smaller than the dimension of the enveloping tangent space at $\sqrt nF_n$ (i.e., the defect of $F_n$). This is particularly surprising because for every $n$ there exist enough one-parameter analytic families to provide a basis of directions in the enveloping tangent space. We obtain cubic obstructions when $n$ has at least three distinct prime divisors, quartic obstructions when it has exactly two and a repeated factor, and quintic obstructions when it is the product of two distinct odd primes. These results extend our order $30$ result from \cite{HN}.

### A Proof of the Achlioptas-Friedgut Convergence Conjecture

- arXiv: 2611.21665 · https://arxiv.org/abs/2611.21665v1 · PDF https://arxiv.org/pdf/2611.21665v1
- Authors: Gaia Carenini
- Categories: math.PR (primary), math.CO
- Comments: Comments are welcome!
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21665.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21665.md

For every fixed integer $q\ge3$, we show that the $q$-colourability transition in a sparse random graph takes place at a limiting edge density, thus proving the Achlioptas-Friedgut convergence conjecture. The proof adapts the argument we recently introduced to settle the satisfiability conjecture.

### On representation-theoretic and homological properties of distance algebras of finite graphs

- arXiv: 2611.22478 · https://arxiv.org/abs/2611.22478v1 · PDF https://arxiv.org/pdf/2611.22478v1
- Authors: Aaron Chan, Bohan Xing
- Categories: math.RT (primary), math.CO, math.RA
- Comments: 34 pages. All comments are welcome!
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22478.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22478.md

Distance algebras were introduced by Asao and Ivanov to realize magnitude homology and cohomology as bigraded Tor and Ext groups. We study the representation-theoretic and homological properties of the distance algebra $Σ_G$ of a finite connected graph $G$. We characterize the graphs for which $Σ_G$ is representation-finite, multiserial, biserial, or self-injective by an explicit graph-theoretic classification. We also compute the finitistic, self-injective, and dominant dimensions for several natural families of graphs. For a finite modular lattice $L$, we consider the distance algebra $Σ_L$ associated to the Hasse graph of $L$, and show that $Σ_L$ is Auslander--Gorenstein precisely when $L$ is a finite direct product of chains. We also present a family of minimal Auslander--Gorenstein distance algebras, namely, those associated to punctured hypercubes, whose finitistic (equivalently, self-injective; equivalently, dominant) dimension can be arbitrarily large.

## Cross-lists from other fields (3)

### Optimal Network Design under Node Failures

- arXiv: 2611.21856 · https://arxiv.org/abs/2611.21856v1 · PDF https://arxiv.org/pdf/2611.21856v1
- Authors: Michele Lombardi, Francesco Umutcan, Enjun Liu
- Categories: econ.TH (primary), math.CO
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.21856.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.21856.md

Networks are frequently constructed before it is determined which nodes will persist. We address the design problem in scenarios where nodes fail independently, links are costly and must be established in advance, and the benefits to surviving nodes diminish with distance. Examples include supplier, interbank, and infrastructure networks. Among all possible networks, the complete, star, and empty configurations are each welfare-optimal within specific ranges of link costs. However, with four or more nodes, failures introduce a range of costs in which every optimal network contains more links than the star but fewer than the complete network. At the lower end of this range, we show that the optimal networks are exactly those obtained by removing a matching from the complete network. We develop an exact algorithm for complete multipartite networks. It finds an optimal network by dynamic programming in a number of operations that grows with the fourth power of the number of nodes, although the class itself grows superpolynomially. For networks with up to six nodes, restricting the design to this class results in no loss under explicit conditions. We also characterize pairwise-stable networks within this class and establish their existence for every level of link cost. Finally, we quantify the cost of misjudging failure risk. Overestimating node survival leads to overbuilding and can yield lower welfare than building nothing, whereas underestimating it never does. Under uncertain failure risk, design should therefore favor conservative reliability estimates.

### Single-Vertex Metropolis on Minor-Free Graphs: A General EPTAS

- arXiv: 2611.22023 · https://arxiv.org/abs/2611.22023v1 · PDF https://arxiv.org/pdf/2611.22023v1
- Authors: Daniel Skachkov, Yuriy Dorn
- Categories: cs.DS (primary), math.CO
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.22023.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.22023.md

We consider a class of combinatorial optimization problems where the goal is to find a largest induced subgraph with a prescribed property. We assume that the property is preserved by taking induced subgraphs and disjoint unions, holds for all edgeless graphs, and can be tested in polynomial time. We study the single-vertex Metropolis process for this class of problems. We show that on graphs excluding an arbitrary fixed minor $H$, this process is a randomized efficient polynomial-time approximation scheme. Starting from any feasible solution on a graph with $n$ vertices, it finds a $(1-\varepsilon)$-approximation within $\exp(O_H(\varepsilon^{-2})) n(n+\log(1/δ))$ steps with probability at least $1-δ$. This includes maximum independent set, maximum induced forest, maximum induced bipartite subgraph, and maximum induced subgraph of degree at most one. The proof uses improving exchanges on one fixed division of the input graph into regions. A recursive separator construction performs each exchange inside a region of size $r$ in at most $2r$ moves, with temporary loss $O_H(\sqrt r)$. We count move sequences through each transition and bound the probability of avoiding all near-optimal states. The general theorem bounds the number of Metropolis steps in terms of the temporary loss along improvement paths. We extend the result to bounded weight imbalance and give a weighted-star obstruction for unrestricted weights.

### Derandomized Sunflowers and Radical Lower Bounds

- arXiv: 2611.23109 · https://arxiv.org/abs/2611.23109v1 · PDF https://arxiv.org/pdf/2611.23109v1
- Authors: Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff
- Categories: cs.CC (primary), math.CO
- Comments: Full version of FOCS 2026 paper
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.23109.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.23109.md

Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or i.i.d. distributions, they also hold for $O(w^2)$-wise independent distributions by Bazzi's theorem (Bazzi (SICOMP 2009); Tal (CCC 2017)), which states that width-$w$ DNFs cannot distinguish between such distributions and the uniform distribution. We prove a derandomization of robust sunflower lemmas for $O(w)$-wise independent distributions, which recovers the derandomization above with slightly weaker parameters. Notably, our result also holds for distributions whose marginals are "locally independent" and "approximately identically" distributed. It is not known whether such distributions fool general DNFs, which makes the derandomization via DNF-fooling techniques unavailable. Our proof of this derandomization is via the method of moments, which might be of independent interest. We apply this result to obtain improved separations between non-monotone arithmetic circuits and the radical of monotone circuits. Specifically, we construct an explicit family of multilinear polynomials $P_n$ that have small non-monotone arithmetic circuits such that any power of $P_n$ cannot be computed by monotone arithmetic circuits of sub-exponential size. This improves on a recent result of Cavalar, Fabris, Mukhopadhyay, Srinivasan and Yehudayoff (STOC 2026), who proved a non-explicit separation that was quasipolynomial. Our construction uses Nisan-Wigderson designs with an additional linear-algebraic expansion property.

## New versions (33)

### Weak Hurwitz stability of extended Turán expressions for Stirling--Whitney--Riordan and Laguerre polynomials

- arXiv: 2610.35783 · https://arxiv.org/abs/2610.35783v2 · PDF https://arxiv.org/pdf/2610.35783v2
- Authors: Wenle Shi
- Categories: math.CA (primary), math.CO
- Signals: new version v2
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2610.35783.html · Markdown https://pragyaangaur.dev/Paperlane/p/2610.35783.md

In this paper, we establish a sufficient condition for weak Hurwitz stability of extended Turán expressions associated with polynomial sequences satisfying a first-order differential recurrence. As applications, we prove weak Hurwitz stability of extended Turán expressions for the Stirling--Whitney--Riordan polynomials, several families of Eulerian polynomials, the Bell polynomials, and the reflected generalized Laguerre polynomials. These results settle two conjectures of Chasse, Grabarek, and Visontai concerning the Bell and Laguerre polynomials.

### Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs

- arXiv: 2502.07769 · https://arxiv.org/abs/2502.07769v3 · PDF https://arxiv.org/pdf/2502.07769v3
- Authors: Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma, Siani Smith
- Categories: math.CO (primary), cs.CC
- Signals: new version v3
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2502.07769.html · Markdown https://pragyaangaur.dev/Paperlane/p/2502.07769.md

We investigate how allowing self-loops and multi-edges (i.e. moving from simple graphs to pseudographs) impacts the complexity of graph problems on finitely defined monotone graph classes. We do this by extending the C123-framework beyond simple graphs. We use several testbed problems to illustrate some of the new and varied behaviours introduced by the transition to pseudographs. We show that Pseudograph Matching Cut and Pseudograph d-Cut are C123-problems. Consequently, for every finite set HH of simple graphs, we obtain a complete complexity classification for these problems on HH-subgraph-free graphs. This sharply contrasts with their simple-graph counterparts, which are not C123-problems and their complexity remains open even for classes defined by a single forbidden subgraph H. We also show that Pseudograph Stable Cut is not a C123-problem. Nevertheless, for graph classes defined by a single forbidden subgraph, the problem mirrors the C123 classification; this correspondence already fails for sets of size 2. This gives the first example of a problem that aligns with C123-problems for a single forbidden subgraph but not for larger sets. Motivated by the interpretation of Stable Cut as a surjective homomorphism to a partially reflexive path, we also study surjective homomorphisms to partially reflexive cycles on k vertices with one irreflexive vertex. These problems share structural similarities with Pseudograph Stable Cut. We prove that for k at least 6, they are NP-complete on triangle-free pseudographs. However, unlike Pseudograph Stable Cut, they are polynomial-time solvable on all graph classes with bounded-degree.

### A polynomial-time algorithm to compute the co-boxicity of block-structured graphs

- arXiv: 2510.02199 · https://arxiv.org/abs/2510.02199v2 · PDF https://arxiv.org/pdf/2510.02199v2
- Authors: Marco Caoduro, Will Evans, Tao Gaede
- Categories: math.CO (primary)
- Signals: new version v2
- Comments: 18 pages, 5 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2510.02199.html · Markdown https://pragyaangaur.dev/Paperlane/p/2510.02199.md

The boxicity of a graph $G$ is the minimum dimension $d$ that admits a representation of $G$ as the intersection graph of a family of axis-parallel boxes in $\mathbb{R}^d$. Boxicity has applications in ecology and operations research, where it models competition for shared resources. Computing boxicity is an NP-hard problem. Despite considerable theoretical interest, few graph classes are known for which the boxicity can be computed in polynomial time. Following the approach of Cozzens and Roberts (1983), we study directly the boxicity of graph complements, which we call co-boxicity. In this setting, the geometric intersection problem in $\mathbb{R}^d$ becomes a graph cover problem involving only complements of interval graphs. We give a polynomial-time algorithm that computes the co-boxicity of $G$ from two pieces of information about each block: its co-boxicity, and how the co-boxicity changes when certain subsets of its vertices become cut-vertices. Using this algorithm, we obtain polynomial-time algorithms for the co-boxicity of trees, graphs with bounded block order, block graphs, and cactus graphs. More generally, our method implies the union of these results: for any fixed $k \geq 3$, there is a polynomial-time algorithm to compute the co-boxicity of $G$ whenever every block of $G$ is complete, a cycle, or has at most $k$ vertices.

### Seaweed algebras with restricted part sizes

- arXiv: 2512.05890 · https://arxiv.org/abs/2512.05890v3 · PDF https://arxiv.org/pdf/2512.05890v3
- Authors: Kassie Archer, Aaron Geary, Robert P. Laudone
- Categories: math.CO (primary)
- Signals: new version v3
- Comments: 28 pages. v3: added additional exposition, fixed errors in some of generating functions
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2512.05890.html · Markdown https://pragyaangaur.dev/Paperlane/p/2512.05890.md

Seaweed algebras are a class of Lie algebras that are naturally characterized by a pair of compositions, which in turn are represented visually as planar graphs called meanders. These meanders provide a straightforward method for computing the index of the associated algebra. The goal of this paper is to enumerate those seaweed algebras with a fixed index and whose associated compositions have restricted part sizes. In particular, we enumerate those with composition part sizes from so-called acyclic sets. We also establish a bijection between sets of indecomposable seaweed algebras with meanders with certain restricted part sizes and sets of permutations with restricted displacements. In certain cases, the index of the algebra can be determined by a simple statistic on the permutation.

### Grundy Values of Node-Kayles on Level-Regular Trees

- arXiv: 2512.24221 · https://arxiv.org/abs/2512.24221v2 · PDF https://arxiv.org/pdf/2512.24221v2
- Authors: Nuttanon Songsuwan
- Categories: math.CO (primary)
- Signals: new version v2
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2512.24221.html · Markdown https://pragyaangaur.dev/Paperlane/p/2512.24221.md

Node-Kayles is an impartial combinatorial game played on graphs, in which the two players alternately select a vertex and remove it together with all of its neighbours. By the Sprague--Grundy theorem, every position has a Grundy value that determines its outcome under optimal play. In this paper we study the Grundy values of Node-Kayles on level-regular trees $\T{a}$, $a=(a_1,\dots,a_d)$, in which every vertex at level $i-1$ has exactly $a_i$ children. We determine the Grundy values of all level-regular trees of depth at most two, show that $\G(\T{a})\le d+1$, and prove that $\G(\T{a})>0$ whenever $a_1a_2a_3$ is even, using an explicit mirror strategy. We prove a Leaf-Pair Lemma, which shows that the last branching parameter $a_d$ matters only through its parity, and a Twin Lemma for subgraphs that come in isomorphic pairs; as a consequence, $\G(\T{1,2k,s})=1$ for every $k\ge1$ and every finite sequence $s$. For trees containing a long run of ones, we give a general periodicity criterion: if the Grundy values of a tree with a pendant path of length $h$ are $34$-periodic on a finite window, then they are $34$-periodic for all larger $h$. This criterion extends to paths joining two fixed subtrees, and it explains the eventual periodicity of the families $\T{1^k,2}$ and $\T{2,1^k,2}$. We also show that, in this setting, eventual periodicity is equivalent to the boundedness of the Grundy values. Finally, supported by computations, we conjecture that the Grundy values are eventually periodic, with period $2$, in each branching parameter, and eventually periodic in the length of every run of ones.

### Plane partitions and spin adapted quantum states

- arXiv: 2601.06295 · https://arxiv.org/abs/2601.06295v2 · PDF https://arxiv.org/pdf/2601.06295v2
- Authors: Abigail Price, Ada Stelzer, Svala Sverrisdóttir
- Categories: math.CO (primary), math.AC, physics.chem-ph
- Signals: new version v2
- Comments: v2: major revisions. The standard monomial basis for $S_{m, k}$ is now obtained via a representation theoretic argument regarding ideals of "generalized permanents" rather than Macaulay2 computations. Additional details and revisions for clarity have been made throughout the paper. We are grateful to the anonymous journal referees whose comments inspired these changes. 15 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2601.06295.html · Markdown https://pragyaangaur.dev/Paperlane/p/2601.06295.md

We describe an explicit basis for the $\operatorname{SU}(2)$-invariant space of the exterior power $\wedge_{2k} \mathbb{C}^{2m}$ via the combinatorics of plane partitions. In quantum chemistry, this is the space of spin adapted quantum states of an electronic system with $m$ spin orbitals and $k$ electron pairs. We construct our basis by identifying the invariant space with an Artinian commutative ring called the excitation ring. We compute a Gröbner basis and enumerate its standard monomials via an explicit bijection to Dyck paths counted by the Narayana numbers.

### The Inverse Symplectic Eigenvalue Problem of a Graph

- arXiv: 2601.11912 · https://arxiv.org/abs/2601.11912v2 · PDF https://arxiv.org/pdf/2601.11912v2
- Authors: Himanshu Gupta, Leslie Hogben, Bryan Shader, Tony Wong
- Categories: math.CO (primary)
- Signals: new version v2
- Comments: 44 pages, 5 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2601.11912.html · Markdown https://pragyaangaur.dev/Paperlane/p/2601.11912.md

Symplectic geometry plays an increasingly important role in mathematics, physics, and applications. The concept of symplectic eigenvalues, whose existence for positive definite matrices is known as Williamson's Theorem, naturally gives rise to inverse problems. We introduce the inverse symplectic eigenvalue problem for positive definite matrices described by a labeled graph and solve it for several families and all labeled graphs of order four. We develop various tools such as the Strong Symplectic Spectral Property (SSSP) together with its consequences, graph couplings to describe collections of labelings of a graph that produce the same symplectic eigenvalues, and coupled graph zero forcing. We establish numerous results for symplectic positive definite matrices, including a sharp lower bound on the number of nonzero entries of such an irreducible matrix (or equivalently, the number of edges in its graph). This lower bound is a consequence of a lower bound on the sum of the number of nonzero entries in an irreducible positive definite matrix and its inverse.

### On the distribution of multiplicative energy

- arXiv: 2602.01781 · https://arxiv.org/abs/2602.01781v2 · PDF https://arxiv.org/pdf/2602.01781v2
- Authors: Norbert Hegyvári
- Categories: math.CO (primary)
- Signals: new version v2
- Comments: Major revision. Comments are welcome
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2602.01781.html · Markdown https://pragyaangaur.dev/Paperlane/p/2602.01781.md

This paper extends the investigation of energy distribution in finite settings, building on results established in our earlier work. We analyze the distribution of multiplicative energies of different orders using Fourier-analytic methods. Our results provide new structural insights into energy phenomena in finite fields, complementing earlier discrete analyses. In the last section, as a corollary, we obtain a 'sum-multiplicative energy'-type result.

### Bicyclic graphs with the smallest and largest numbers of connected sets

- arXiv: 2603.26812 · https://arxiv.org/abs/2603.26812v2 · PDF https://arxiv.org/pdf/2603.26812v2
- Authors: Audace A. V. Dossou-Olory
- Categories: math.CO (primary)
- Signals: new version v2
- Comments: 22 pages, 11 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2603.26812.html · Markdown https://pragyaangaur.dev/Paperlane/p/2603.26812.md

For a graph $G$ with vertex set $V$, let N(G) denote the number of nonempty subsets of $V$ that induce a connected graph in $G$. In this paper, we focus on determining N(G) for $G$ in the family $\mathbb{B}_n$ of $n$-vertex bicyclic graphs. We find in $\mathbb{B}_n$ the structures of those graphs that possess the smallest, the largest, as well as the second-largest values of N(G). Moreover, we compute the extreme values of N(G) over $ \mathbb{B}_n$.

### A counterexample to a basis conjecture of Brualdi, Friedland, and Pothen

- arXiv: 2605.30401 · https://arxiv.org/abs/2605.30401v3 · PDF https://arxiv.org/pdf/2605.30401v3
- Authors: Mohsen Aliabadi
- Categories: math.CO (primary)
- Signals: new version v3
- Comments: We replaced the \(4\times8\) example with a \(4\times6\) sparse generic matrix, with complete verification of elementary vectors, rank inequalities, and dependence. We also proved that the four vectors are minimally dependent: every proper subfamily is independent. 6 pages. Comments welcome!
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2605.30401.html · Markdown https://pragyaangaur.dev/Paperlane/p/2605.30401.md

Brualdi, Friedland, and Pothen conjectured that certain rank inequalities characterize bases consisting of elementary vectors in the row space of a matrix whose nonzero entries are algebraically independent. We give a $4\times6$ counterexample: all the inequalities hold, but the four elementary vectors form a minimally dependent family. A construction using two planes in a common three-dimensional subspace explains the dependence and gives a second counterexample pattern with only four prescribed zeros. We also prove that the proposed criterion is valid over every field when the number of columns exceeds the row rank by at most one. A direct-sum extension gives counterexamples of size $m\times(m+2)$ for every $m\ge4$. Thus the minimum column excess permitting a counterexample is exactly two in every such rank.

### Subhypergraph counts and proofs of two conjectures of Alon

- arXiv: 2606.18321 · https://arxiv.org/abs/2606.18321v2 · PDF https://arxiv.org/pdf/2606.18321v2
- Authors: Peiru Kuang, Shuang Sun, Yan Wang, Jiasheng Zeng
- Categories: math.CO (primary)
- Signals: new version v2
- Comments: 24 pages. This version extends the main asymptotic counting result from graphs to uniform hypergraphs. Comments are welcome
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2606.18321.html · Markdown https://pragyaangaur.dev/Paperlane/p/2606.18321.md

For a fixed integer $r\ge2$ and a finite simple $r$-uniform hypergraph $H$ without isolated vertices, let $N_r(m,H)$ be the maximum number of unlabelled copies of $H$ among all finite simple $r$-uniform hypergraphs with $m$ edges. Friedgut and Kahn [Isr. J. Math., 1998] proved that $N_r(m,H)=Θ_H(m^{ρ^*(H)})$, where $ρ^*(H)$ is the fractional edge-cover number of $H$. We sharpen this to $N_r(m,H)=(λ_r(H)+o(1))m^{ρ^*(H)}$ as $m\to\infty$, with $λ_r(H)>0$, and characterize the limiting $λ_r(H)$ by a variational problem over finite hypergraphs. We develop a globally rainbow compression argument combining color-coding with successive vertex cloning. In particular, when $r=2$, the asymptotic formula confirms a conjecture of Alon [Isr. J. Math., Conjecture 1, 1986]. Moreover, for graphs we express the limiting constant $λ_2(H)$ as a supremum over finite cores. We also prove that, for every prescribed number of edges, an extremal graph for a star forest can be chosen to be a star forest, confirming another conjecture of Alon [Isr. J. Math., Conjecture 2, 1986].

### A General Inequality for Walks in Graphs

- arXiv: 2609.11846 · https://arxiv.org/abs/2609.11846v2 · PDF https://arxiv.org/pdf/2609.11846v2
- Authors: Chase Wilson
- Categories: math.CO (primary)
- Signals: new version v2
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2609.11846.html · Markdown https://pragyaangaur.dev/Paperlane/p/2609.11846.md

Let $G$ be a graph and $w_k(G)$ denote the number of walks in $G$ of length $k$. For sequences $a_1, \cdots, a_n$ and $b_1, \cdots, b_n$ of non-negative integers such that $a_1 + \cdots + a_n = b_1 + \cdots + b_n$, we determine a simple necessary and sufficient condition on $a_1, \cdots, a_n, b_1, \cdots, b_n$ for the inequality \[ w_{a_1}(G) \cdots w_{a_n}(G) \geq w_{b_1}(G) \cdots w_{b_n}(G) \] to hold for any graph $G$.

### Hull Games of Induced Path Convexities in Graphs

- arXiv: 2609.30302 · https://arxiv.org/abs/2609.30302v5 · PDF https://arxiv.org/pdf/2609.30302v5
- Authors: Eurinardo Costa, Leon Almeida, Rudini Sampaio
- Categories: cs.DM (primary), math.CO
- Signals: new version v5
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2609.30302.html · Markdown https://pragyaangaur.dev/Paperlane/p/2609.30302.md

In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths. In 2024, Araújo et al. obtained the first PSPACE-hardness proofs on some of these geodesic games and generalized them to any graph convexity. In this paper, we investigate convexity games on several known induced path convexities: the monophonic $\mathrm{m}$-convexity and the $\ell_k$-convexities, based on induced paths and on induced paths of size at most $k$. We prove that the hull games $\mathrm{CHG}_{\mathrm{m}}$, $\mathrm{CHG}_{\ell_k}$ and their misère variants are PSPACE-complete for every $k\ge2$ even in graphs with diameter at most 3. We also use the Sprague-Grundy Theory to obtain a polynomial time algorithm to decide the winner of the games $\mathrm{CHG}_{\mathrm{m}}$ and $\mathrm{CHG}_{\ell_k}$ for any $k\ge2$ in disjoint unions of paths and cycles. For $k\ge3$ odd, we prove that Alice (1st player) wins $\mathrm{CHG}_{\ell_k}$ in the path $P_n$ if and only if $n$ is odd and she wins in the cycle $C_n$ if and only if $n=3$ or $n=α\cdot (k+1)-1$ with $α\ge2$. For $k\ge2$ even, the only periodic nimber sequences of $\mathrm{CHG}_{\ell_k}$ obtained through extensive computational testing occurred for $k=2^h-4$ with $h\ge3$, e.g, $k\in\{4,12,28,60,\ldots\}$. In this case ($k=2^h-4$ with $h\ge3$), we prove that the nimber sequences of $\mathrm{CHG}_{\ell_k}$ in $P_n$ and in $C_n$ are periodic and Alice loses (resp. wins) in $P_n$ (resp. $C_n$) with $n>k$ only when $n=3k+4$ (resp. $n\in\{2k+1,5k+3\}$). Finally, we show that, for $k=2$, the game $\mathrm{CHG}_{\ell_2}$ in paths $P_n$ is closely related to the classical game \emph{Couples-are-Forever} of J. H. Conway: it is still an open problem if the nimber sequence is periodic or not and Alice loses only for 12 values of $n$ up to $200$ million.

### Two families of Hermite normal form simplices

- arXiv: 2609.36818 · https://arxiv.org/abs/2609.36818v4 · PDF https://arxiv.org/pdf/2609.36818v4
- Authors: Feihu Liu, Jinlong Tang, Sihao Tao, Zihao Zhang
- Categories: math.CO (primary)
- Signals: new version v4
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2609.36818.html · Markdown https://pragyaangaur.dev/Paperlane/p/2609.36818.md

We study Ehrhart coefficients, the integer decomposition property, and unimodular triangulations for two families of Hermite normal form simplices considered by Bruckamp, Caicedo, and Juhnke. The first family consists of simplices of the form $S_{\boldsymbol{a}}=\mathrm{conv}(0,e_1,\ldots,e_{d-1},\boldsymbol{a})$, where $\boldsymbol{a}=(a_1,\ldots,a_{d-1},N)$, and the second consists of the simplices $T_{d,N}=\mathrm{conv}\bigl(0,e_1,\ldots,e_{d-2},(d-2,\ldots,d-2,d-1,0),(1,\ldots,1,N)\bigr)$. For the family $T_{d,N}$, we prove unimodality of the Ehrhart coefficients in every dimension and determine the log-concave and real-rooted cases. For the subfamily $S_{\boldsymbol{a}}$ with $\boldsymbol{a}=(N-q,\ldots,N-q,N)$, we characterize both the integer decomposition property and the existence of a regular unimodular triangulation via a congruence condition on a negative continued fraction. We also give an arithmetic test for the integer decomposition property and finite triangulation tests for $S_{\boldsymbol{a}}$ with arbitrary $\boldsymbol{a}$. These results address three open questions of Bruckamp, Caicedo, and Juhnke.

### Non-isomorphic graphs have distinct vertex-Ramsey classes

- arXiv: 2610.03704 · https://arxiv.org/abs/2610.03704v2 · PDF https://arxiv.org/pdf/2610.03704v2
- Authors: Maria Axenovich, Patrick Schmitteckert
- Categories: math.CO (primary), cs.IT
- Signals: new version v2
- Comments: Added a result on vertex-Ramsey equivalent families of graphs. 5 pages, 1 figure
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2610.03704.html · Markdown https://pragyaangaur.dev/Paperlane/p/2610.03704.md

For a graph $H$, its $k$-colour vertex Ramsey class is the set of all graphs $G$ such that any colouring of the vertices of $G$ in $k$ colours results in a monochromatic (induced) copy of $H$. We prove that for any $k$, the $k$-colour vertex Ramsey classes of any non-isomorphic graphs are distinct. Moreover, we show that this property does not hold when individual graphs are replaced with families of graphs.

### Infinite Derivatives and Local Extrema of the Delange Function of Every Base

- arXiv: 2610.21265 · https://arxiv.org/abs/2610.21265v3 · PDF https://arxiv.org/pdf/2610.21265v3
- Authors: Chengyi Zhu
- Categories: math.CO (primary), math.NT
- Signals: new version v3
- Comments: 125 pages, 29 figures, 2 tables. v3: the main results are extended from base 3 to every base q >= 2, and the title is changed accordingly
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2610.21265.html · Markdown https://pragyaangaur.dev/Paperlane/p/2610.21265.md

For an integer $q\ge2$, the Delange function of base $q$ is $T_q(x)=\sum_{j=0}^\infty q^{-j}τ_q(q^jx)$, where $τ_q$ has period $1$, is linear on $[k/q,(k+1)/q]$ for integers $0\le k<q$, and satisfies $τ_q(k/q)=k(q-k)/q$ for $0\le k\le q$. Thus $T_2$ is Takagi's function. In the Hamming graph on $\{0,1,\ldots,q-1\}^n$, two words are adjacent exactly when they differ in one letter. For integers $n\ge1$ and $0\le m\le q^n$, $q^nT_q(m/q^n)$ is the smallest number of edges leaving a set of $m$ vertices, which is known. We characterize infinite derivatives by the base $q$ digits $ξ_1,ξ_2,\ldots$ of $x\in[0,1)$. Outside the $q$-adic rationals $m/q^n$ with integers $m$ and $n\ge0$, the right derivative is $+\infty$ exactly when $\sum_{j=1}^n(q-1-2ξ_j)\to+\infty$. The condition for the left derivative to be $+\infty$ also involves the lengths of the maximal strings of zeros. For $-\infty$, the sides and the digits $0$ and $q-1$ are exchanged. The local minima are exactly the $q$-adic rationals. The local maxima are exactly the points $(m+u)/q^n+k$ with integers $k$, $m$, $n$ such that $n\ge0$, $0\le m<q^n$, and the base $q$ digit sum of $m$ is $(q-1)n/2$, where $u$ maximizes $T_q$ on $[0,1]$. For odd $q$, we have $u=1/2$ and every local maximum is strict. For even $q$, there are uncountably many such $u$ and no local maximum is strict. We also find the maximum on each interval $[m/q^n,(m+1)/q^n]$ and all points attaining it. For an integer $h$ with $1\le h\le q^n/2$, we determine the minimum number of edges whose deletion disconnects the graph into components with at least $h$ vertices, including a digit criterion for equality with the minimum boundary at size $h$. Almost every level set $\{x\in[0,1]:T_q(x)=y\}$ is finite, whereas the level set through almost every point is uncountable. Here almost every refers to Lebesgue measure.

### Optimal self-orthogonal binary linear codes

- arXiv: 2610.39870 · https://arxiv.org/abs/2610.39870v2 · PDF https://arxiv.org/pdf/2610.39870v2
- Authors: Sascha Kurz
- Categories: math.CO (primary), cs.DM, cs.IT
- Signals: new version v2
- Comments: 40 pages; typos corrected; comments more than welcome
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2610.39870.html · Markdown https://pragyaangaur.dev/Paperlane/p/2610.39870.md

We complete the determination of the minimum possible length of eight-dimensional binary self-orthogonal codes with given minimum distance. For dimension nine we give exact values and bounds for minimum distance at most $64$. By exploiting the geometric reformulation of linear codes as multisets of points, we fully redo the classification for dimension at most seven in a simplified and computer-free manner. As a by-product we prove the non-existence of $[93,9,44]_2$ codes and show several divisibility results for putative optimal nine-dimensional binary codes.

### Macdonald intersections and the $N!/k$ conjecture

- arXiv: 2611.09638 · https://arxiv.org/abs/2611.09638v2 · PDF https://arxiv.org/pdf/2611.09638v2
- Authors: Peter L. Guo, Mingyang Kang, Changjian Su, Rui Xiong
- Categories: math.CO (primary), math.AG
- Signals: new version v2
- Comments: 29 pages. Added Theorem E. Comments are welcome
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.09638.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.09638.md

We prove the Frobenius characteristic formula for the intersection of Garsia--Haiman modules predicted in the Science Fiction of Bergeron and Garsia. As a consequence, we resolve the $N!/k$ conjecture. The proof uses the geometry of the Hilbert scheme of points in the plane developed by Haiman.

### Rotating Walks, Derandomized Squares, and Permutation Conjugated Walks

- arXiv: 2611.13693 · https://arxiv.org/abs/2611.13693v2 · PDF https://arxiv.org/pdf/2611.13693v2
- Authors: Vedat Levi Alev, Shravas Rao
- Categories: math.CO (primary), cs.DM, math.PR
- Signals: new version v2
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.13693.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.13693.md

Using the recent strong convergence results of Bordenave and Collins (Annals of Mathematics) and Chen et al. (Annals of Mathematics), we study the average case behavior of rotating random walks of Cohen and Maor (STOC 2023) and the derandomized square construction of Rozenman and Vadhan (RANDOM 2005). Concretely, we prove a conjecture of Cohen et al. (ITCS 2025) regarding the average case behavior of derandomized squaring for random graphs and show that the existential bounds of Cohen and Maor for their rotating random walk construction hold with high-probability for random graphs. Using the results of O'Donnell and Wu (FOCS 2020), we can in polynomial time construct a family of graphs and rotations which almost saturate the bounds of Cohen and Maor, and meet the bounds conjectured by Cohen et al. for all vertex-transitive auxiliary graphs of fixed degree in the derandomized square. Finally, we study independent random permutation conjugates of deterministic regular graph adjacency matrices. We prove quantitative weak convergence to freely independent tree adjacency operators when the degrees are fixed and the girths tend to infinity. Separately, a covering argument gives deterministic spectral lower bounds for polynomials with non-negative coefficients, recovering the lower bound of Cohen et al. for rotating walks.

### Bipartite Matchings, Matrix Permanents, and Zeon Power Series

- arXiv: 2611.14802 · https://arxiv.org/abs/2611.14802v2 · PDF https://arxiv.org/pdf/2611.14802v2
- Authors: Muhammad Waqar Ul Hassan, G. Stacey Staples
- Categories: math.CO (primary), math.RA
- Signals: new version v2
- Comments: 24 pages, 7 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.14802.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.14802.md

Perfect matchings of a bipartite graph are counted by the permanent of the graph's biadjacency matrix, and permanents of sequences of structured biadjacency matrices lead to integer sequences. We consider a number of such sequences and illustrate how zeon-algebraic representations of bipartite graphs lead to recursively defined zeon sequences. Then, using formal power series methods, we show that the ``$Ω$-exponentials'' of these zeon sequences reveal numbers of perfect matchings in the graphs.

### $Z_\infty$-algebras: Zinbielification of $B_\infty$ and quasi-shuffle algebras

- arXiv: 2611.17133 · https://arxiv.org/abs/2611.17133v2 · PDF https://arxiv.org/pdf/2611.17133v2
- Authors: Adam Keilthy
- Categories: math.CO (primary)
- Signals: new version v2
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.17133.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.17133.md

Commutative $B_\infty$-algebras provide a natural generalisation of the shuffle and quasi-shuffle algebras, giving deformations of the shuffle algebra. We introduce a Zinbiel analogue in $Z_\infty$-algebras, giving deformations of the half-shuffle Zinbiel algebra. All commutative $B_\infty$-algebras have been shown to be isomorphic to the shuffle algebra, though this isomorphism is not canonical. We show that all $Z_\infty$-algebras are canonically isomorphic to the half-shuffle algebra, which gives a canonical isomorphism to the shuffle algebra for $B_\infty$-algebras arising from $Z_\infty$-algebras. Finally, we explore which $B_\infty$-algebras can be ``Zinbielified'' to a $Z_\infty$-algebra, working through a number of explicit examples in the case of quasi-shuffle algebras and uncovering a very explicit classification of simple Zinbielifications via semigroup cocycles.

### Log-concavity of rank and crank statistics for integer partitions

- arXiv: 2611.17357 · https://arxiv.org/abs/2611.17357v2 · PDF https://arxiv.org/pdf/2611.17357v2
- Authors: Jianxi Mao, Wenle Shi
- Categories: math.CO (primary)
- Signals: new version v2
- Comments: I submitted this manuscript on October 22, and it remained on hold until November 16. During this period, I requested that it be processed but received no response. I then requested withdrawal, and a coauthor uploaded a revised version, which became publicly available the next day. I therefore request withdrawal of the original submission to avoid duplication.
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.17357.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.17357.md

Let $M(m,n)$ and $N(m,n)$ denote the numbers of partitions of $n$ with crank $m$ and rank $m$, respectively. Ji and Zang [Adv. Math. 2021] conjectured that $M(m,n)$ is log-concave in $m$ for $n\ge72$ and $|m|\le n-72$, and that $N(m,n)$ is log-concave in $m$ for $n\ge73$ and $|m|\le n-73$. In this paper, we prove these two conjectures.

### Asymptotic Order of the Minimum Number of Graph-Saturating Edges I

- arXiv: 2611.19750 · https://arxiv.org/abs/2611.19750v2 · PDF https://arxiv.org/pdf/2611.19750v2
- Authors: Xianglei Chen, Changxiang He
- Categories: math.CO (primary)
- Signals: new version v2
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.19750.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.19750.md

Given an $H$-free graph $G$, a non-edge $e$ of $G$ is called $H$-saturating if $G+e$ contains a copy of $H$. The function $f_H(n,m)$ denotes the minimum number of $H$-saturating non-edges over all $n$-vertex $H$-free graphs with exactly $m$ edges. In this paper, we fully characterize the asymptotic order of $f_H(n,\operatorname{ex}(n,R)+1)$ for any fixed graph $H$ with $χ(H)\ge χ(R)$, where $R$ is any fixed edge-critical graph, and resolve the conjecture proposed by He et al. (J. Combin. Theory Ser. B 159 (2023), 42-60).

### Jordan types for pairs of commuting nilpotent matrices: A survey

- arXiv: 2606.02026 · https://arxiv.org/abs/2606.02026v2 · PDF https://arxiv.org/pdf/2606.02026v2
- Authors: Tomaž Košir
- Categories: math.AC (primary), math.AG, math.CO
- Signals: new version v2
- Comments: 16 pages
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2606.02026.html · Markdown https://pragyaangaur.dev/Paperlane/p/2606.02026.md

The aim of the paper is to survey results on Jordan types for pairs of nilpotent commuting matrices. We also review recent proof of the Box Conjecture on Jordan types that have equal dense orbit in the nilpotent commutator.

### Two problems about bases and independent sets in free groups

- arXiv: 2609.00382 · https://arxiv.org/abs/2609.00382v3 · PDF https://arxiv.org/pdf/2609.00382v3
- Authors: Lucy Koch-Hyde, Éamonn Olive
- Categories: math.GR (primary), math.CO
- Signals: new version v3
- Comments: 10 pages, 2 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2609.00382.html · Markdown https://pragyaangaur.dev/Paperlane/p/2609.00382.md

We will answer a problem of Dotsenko that asks for a tight upper bound on the rank of subgroups given a maximum length for its generators. Then, we will use the same tools to answer a longstanding problem of Grigorchuk in the 10th edition of the Kourovka notebook. We accomplish this using Stallings foldings and simple graph theory.

### The cohomology of finite simple groups is unbounded

- arXiv: 2611.11677 · https://arxiv.org/abs/2611.11677v2 · PDF https://arxiv.org/pdf/2611.11677v2
- Authors: Chris Bowman, Damian de la Fuente, Nicolas Libedinsky, David Plaza
- Categories: math.GR (primary), math.CO, math.RT
- Signals: new version v2
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2611.11677.html · Markdown https://pragyaangaur.dev/Paperlane/p/2611.11677.md

In every fixed positive degree, we show that the cohomology of finite simple groups, algebraic groups and quantum groups, with coefficients in simple modules, can have arbitrarily large dimension. In particular, we disprove Guralnick's conjecture.

### Twisted Conjugacy and the Construction of Induced Centrosymmetric Alternant Codes

- arXiv: 2608.11056 · https://arxiv.org/abs/2608.11056v2 · PDF https://arxiv.org/pdf/2608.11056v2
- Authors: Ousmane Ndiaye, Massamba Sow
- Categories: cs.IT (primary), math.CO
- Signals: new version v2
- Comments: Keywords: Alternant codes, Generalized Reed--Solomon codes, automorphism groups, twisted conjugacy, projective semilinear group
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2608.11056.html · Markdown https://pragyaangaur.dev/Paperlane/p/2608.11056.md

This paper presents a construction of induced centrosymmetric alternant codes based on the automorphism structures inherited from Generalized Reed-Solomon (GRS) codes. We introduce a twisted conjugacy relation naturally arising from projective semilinear transformations and establish its connection with ordinary conjugacy in the corresponding projective semilinear coset. By means of the Shintani norm, we show that, in the quadratic extension case, all admissible transformations inducing centrosymmetry have a trivial Shintani norm and therefore belong to a unique conjugacy class in the semilinear coset. We further characterize the explicit forms of these transformations and establish a transport theorem describing how twisted conjugation acts on the supports and multipliers of GRS codes. These results provide an algebraic framework for constructing and analyzing induced centrosymmetric alternant codes.

### Hilbert's Tenth problem and NP-completeness of Boolean Syllogistic with unordered cartesian product

- arXiv: 2101.00198 · https://arxiv.org/abs/2101.00198v3 · PDF https://arxiv.org/pdf/2101.00198v3
- Authors: Domenico Cantone, Pietro Ursino
- Categories: math.LO (primary), math.CO
- Signals: new version v3
- Comments: One of the announced result is false
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2101.00198.html · Markdown https://pragyaangaur.dev/Paperlane/p/2101.00198.md

We relate the decidability problem for BS with unordered cartesian product with Hilbert's Tenth problem and prove that BS with unordered cartesian product is NP-complete.

### Cohomological VC-density: Bounds and Applications

- arXiv: 2411.09670 · https://arxiv.org/abs/2411.09670v3 · PDF https://arxiv.org/pdf/2411.09670v3
- Authors: Saugata Basu, Deepam Patel
- Categories: math.LO (primary), math.AG, math.CO
- Signals: new version v3
- Comments: 53 pages. Corrected version
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2411.09670.html · Markdown https://pragyaangaur.dev/Paperlane/p/2411.09670.md

The concept of Vapnik-Chervonenkis (VC) density is pivotal across various mathematical fields, including discrete geometry, probability theory and model theory. In this paper, we introduce a topological generalization of VC-density. Let $Y$ be a topological space and $\mathcal{X}$ a family of closed subspaces of $Y$. For each $p \geq 0$, we define a number, $\mathrm{vcd}^{p}_{\mathcal{X}}$, which we refer to as the degree $p$ VC-density of the family $\mathcal{X}$. The classical notion of VC-density within this topological framework can be recovered by setting $p=0$. Our definition of degree $p$ VC-density extends to higher orders as well. For $p \geq 0$, $q \geq 1$, we define the degree $p$, order $q$ VC density $\mathrm{vcd}^{p,q}_{\mathcal{X}}$ of $\mathcal{X}$, which recovers Shelah's notion of higher order VC-density for $q$-dependent families when $p=0$. Our definition introduces a completely new notion when $p > 0$. We examine the properties of $\mathrm{vcd}_{\mathcal{X}}^p$ (as well as $\mathrm{vcd}^{p,q}_{\mathcal{X}}$) when the families $\mathcal{X}$ are definable in structures with some underlying topology (for instance, the Euclidean topology for o-minimal structures over $\mathbb{R}$, the analytic topology over $\mathbb{C}$, or the étale site for schemes over arbitrary algebraically closed fields). Our main result establishes that in any model of these theories \[ \mathrm{vcd}_{\mathcal{X}}^p \leq (p+1) \dim X, \] and more generally for any $q \geq 1$ \[ \mathrm{vcd}^{p,q}_{\mathcal{X}} \leq (p+q) \dim X. \] We give examples to show that our bounds are optimal. We also present combinatorial applications of our higher-degree VC-density bounds, deriving higher degree topological analogs of well-known results such as the existence of $\varepsilon$-nets and the fractional Helly theorem.

### Rado's covering problem for cubes and balls: a survey

- arXiv: 2604.17509 · https://arxiv.org/abs/2604.17509v3 · PDF https://arxiv.org/pdf/2604.17509v3
- Authors: Gian Maria Dall'Ara, Adrian Dumitrescu
- Categories: math.MG (primary), cs.DM, math.CA, math.CO
- Signals: new version v3
- Comments: 15 pages, 6 figures
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2604.17509.html · Markdown https://pragyaangaur.dev/Paperlane/p/2604.17509.md

What is the largest constant $c\in [0,1]$ with the property that every finite collection $\mathcal{C}$ of axis-parallel squares in the plane admits a disjoint sub-collection $\mathcal{S}$ occupying at least a fraction $c$ of the area covered by $\mathcal{C}$? This problem was first raised by T.~Radó in 1928, who was motivated by a classical covering lemma in real analysis due to Vitali. R.~Rado later generalized the problem from axis-parallel squares in the plane to homothetic copies of any given convex body $K$ in $\mathbb{R}^d$, where now we are looking for an optimal constant $F(K)$. In this paper we survey the literature on this problem, with a focus on the case where $K$ is a cube or a ball in the high-dimensional regime $d\rightarrow \infty$. The estimates that we currently have for cubes are much more precise than those for balls: namely if $Q^d$ is a $d$-dimensional cube, then \[ (e^{-1}+o(1))\frac{2^{-d}}{d \log{d}} \leq F(Q^d)\leq 2^{-d}, \] while denoting $B^d$ a $d$-dimensional Euclidean ball, then \[ 2.910^{-d} \leq F(B^d) \leq 2.447^{-d}.\] Except for the upper bound for cubes, which is classical, the other estimates are due to the authors.

### The Hofstadter Consecutive-Sum Sequence Omits Infinitely Many Positive Integers

- arXiv: 2603.09939 · https://arxiv.org/abs/2603.09939v3 · PDF https://arxiv.org/pdf/2603.09939v3
- Authors: Quanyu Tang
- Categories: math.NT (primary), math.CO
- Signals: new version v3
- Comments: 23 pages, 1 figure. Published in the Journal of Integer Sequences. This version incorporates the revisions made for publication
- Journal reference: Journal of Integer Sequences 29 (2026), Article 26.6.1
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2603.09939.html · Markdown https://pragyaangaur.dev/Paperlane/p/2603.09939.md

We study Hofstadter's greedy self-generating sequence, which begins with 1 and 2 and repeatedly chooses the least integer larger than the preceding term that is a sum of at least two consecutive earlier terms. We prove that the excess of its $n$th term over its index is bounded below by a positive constant times $\log\log n$, up to an additive constant, and that the sequence satisfies a polynomial upper bound. In particular, the sequence omits infinitely many positive integers.

### Super-Arrhenius relaxation of the triangular plaquette model in any dimension

- arXiv: 2606.16259 · https://arxiv.org/abs/2606.16259v2 · PDF https://arxiv.org/pdf/2606.16259v2
- Authors: Laurent Bartholdi, Ivailo Hartarsky, Ivan Mitrofanov
- Categories: math.PR (primary), cond-mat.stat-mech, math.CO, math.DS, math.GR
- Signals: new version v2
- Comments: 49 pages, 8 figures, improved presentation, added Sections 1.3.4 and 6 on linear error-correcting codes
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2606.16259.html · Markdown https://pragyaangaur.dev/Paperlane/p/2606.16259.md

Consider the following plaquette model from statistical physics: a lamp lies at every vertex of the triangular lattice and a switch lies at every even vertex of the (bipartite) dual hexagonal lattice. Each switch toggles the three lamps on its face. The energy of a configuration is the number of ON lamps. For the Glauber dynamics associated with the Gibbs measure defined by this Hamiltonian at any inverse temperature $β>0$, we show that, in any dimension $d\ge 2$, the infinite volume relaxation time satisfies \[e^{β^2/C}/C \le T_{\mathrm{rel}}\le Ce^{e^{Cβ}}\] for some $C>0$. Our result entails that the Gibbs measure is unique. The $e^{β^2}$ scaling was conjectured by Garrahan and Newman in 2000 and matches the behaviour of supercritical rooted kinetically constrained models such as the East model, thus recovering fragile glass phenomenology in the absence of kinetic constraints. More precisely, we show that, on a torus of side length $2^k$, when $β\to\infty$ and $k/β\to0$, we have $T_{\mathrm{rel}}=e^{2βk(1+o(1))}$, confirming a prediction of Newman and Moore. Quite surprisingly, however, we also prove that, on non-periodic finite domains of size $n\le e^{β/C}$ for large $C>0$, we have the much larger asymptotics $\ln T_{\mathrm{rel}}=βn^{Θ(1)}$. The main ingredients of the proofs are new results in extremal and enumerative combinatorics and rely on renormalisation ideas for the dynamics and its groundstates also known as the Ledrappier subshift. Our combinatorial results also have consequences in geometric group theory (more precisely to the complexity of the word problem for the Baumslag finitely presented group), ergodic theory and linear coding theory.

### Symplectic extension graphs and Ribet's lemma

- arXiv: 2610.19434 · https://arxiv.org/abs/2610.19434v2 · PDF https://arxiv.org/pdf/2610.19434v2
- Authors: Aniruddha Sudarshan
- Categories: math.RT (primary), math.CO, math.NT
- Signals: new version v2
- Comments: 40 pages, 1 figure
- Paperlane: https://pragyaangaur.dev/Paperlane/p/2610.19434.html · Markdown https://pragyaangaur.dev/Paperlane/p/2610.19434.md

Let $p$ be an odd prime, and let $ρ\colon G\to \mathrm{GSp}_{2n}(\mathbb Z_p)$ be an irreducible symplectic residually multiplicity-free representation. We define the symplectic extension graph $Γ_ρ^{\mathrm{GSp}}$ associated with $ρ$ to be the directed graph whose vertices are the residual factors of $ρ$ and a directed edge between two vertices corresponds to a nonsplit extension between the vertices realized by a $G$-stable symplectic lattice. Using the Euclidean Bruhat--Tits building associated with $\mathrm{GSp}_{2n}(\mathbb Q_p)$, we prove, under suitable assumptions, the existence of certain paths in $Γ_ρ^{\mathrm{GSp}}$ and show that $Γ_ρ^{\mathrm{GSp}}$ is a disjoint union of nonempty strongly connected subgraphs. Moreover, we provide examples to show that the result we obtain is optimal.
