New on arXiv
Sort: by field | by arXiv number | trending
Combinatorics
Off-Diagonal Induced Ramsey Numbers
Given graphs $F$ and $H$, the induced Ramsey number $r_{\mathrm{ind}}(F,H)$ is the smallest integer $n$ for which there exists a graph $G$ on $n$ vertices such that every red-blue colouring of $E(G)$ contains either a blue induced copy of $F$ or a red induced copy of $H$. A conjecture of Kohayakawa, Pr\"omel and R\"odl asserts that, for every fixed graph $F$, this number is polynomial in $v(H)$....
Heavy-Light Wall Crossings and Motivic Asymptotics of Moduli Spaces of Curves. Part I: Stabilization Graphs and Euler Characteristics
In this paper, we develop an explicit calculation of ordinary topological Euler characteristics of the coarse moduli spaces underlying Hassett spaces in the minimal all-light chamber and the Deligne-Mumford compactification. For genus $g\ge2$, we organize the calculation through a decomposition indexed by stabilization graphs and their decorations. The Burnside-Lefschetz formula allows us to...
Largest Sperner families with bounded VC-dimension
A conjecture of Frankl proposed in the 1980s states that for $n\ge2d$, every Sperner family $\mathcal{F}\subseteq 2^{[n]}$ of VC-dimension at most $d$ has at most $\binom{n}{d}$ members. We prove this conjecture for every fixed $d$ and large $n$, and show that equality holds only when $\mathcal{F}$ is $\binom{[n]}{d}$ or $\binom{[n]}{n-d}$.
Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space
A fault-tolerant (FT) connectivity oracle for an $n$-vertex graph $G=(V,E)$ determines whether $G- F$ is connected for any query set $F\subseteq E$. When the number of failures is unrestricted, prior constructions exhibited a sharp contrast between randomization and determinism: randomized oracles use only $\widetilde{O}(n)$ space [Duan and Pettie, SICOMP 2020], whereas no deterministic...
Hessenberg character
Let $G$ be a connected reductive group with Borel subgroup $B$, flag variety $\mathcal B=G/B$, and Weyl group $W$. We define the \emph{Hessenberg functor} on the geometric Hecke category by microlocalizing along the diagonal in $\mathcal B\times\mathcal B$ and pushing forward along the Springer map. It induces the \emph{Hessenberg character} of the Iwahori--Hecke algebra, with values in graded...
Boxicity of Power Graphs of Finite Nilpotent Groups
The \textit{boxicity} of an undirected graph $\Gamma$, denoted as $\operatorname{box}(\Gamma)$, is the smallest non-negative integer $d$ such that $\Gamma$ can be represented as the intersection graph of axis-parallel rectangular boxes in $\mathbb{R}^d$. The \emph{power graph} of a group $G$, denoted as $\operatorname{Pow}(G)$, is an undirected graph whose vertex set is the group itself, with two...
Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic. We prove that every monadically dependent graph class has almost bounded merge-width, thereby confirming a conjecture of the first and the last author [STOC '25]. Our proof is algorithmic and the witnessing decompositions...
Finding full immersions is fixed-parameter tractable in labeled tour graphs
We give an $O_H(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $H$. A labeled tour graph is a connected $4$-regular graph whose edges are labeled by binary vectors of fixed length. To obtain a full immersion, a vertex may be removed only by pairing up its four incident edges and "splitting off" both pairs, summing the...
Proof of two conjectures on the log-concavity of partition ranks and cranks
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 proved that the crank sequence $(M(m,n))_{|m|\le n-1}$ is unimodal for every $n\ge44$. Bringmann, Man, and Rolen subsequently established the unimodality of the rank sequence $(N(m,n))_{|m|\le n-2}$ for every $n\ge39$. Ji and Zang also conjectured that $(M(m,n))_{|m|\le n-71}$...
The Exact Number of Pentagons in Book-Free Graphs
Let $B_k$ denote the book consisting of $k$ triangles sharing a common edge. We prove that there exist absolute constants $\rho>0$ and $N$ such that, for every pair of integers $n,k$ with $n\ge N$ and $2\le k\le \rho n$, writing $n=5q+r$ with $0\le r<5$, \[ \operatorname{ex}(n,C_5,B_k)=q^{\,5-r}(q+1)^r, \] with the balanced complete $C_5$-blow-ups as the only extremal graphs. The linear order of...
Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs
We prove Conjecture 4 of Chan, Chang, Gao, Kisfaludi-Bak, Le, and Zheng (SoCG 2026): for every fixed integer $r\ge0$, the radius-$r$ neighbourhoods of a unit-cube graph in $\mathbb{R}^3$ have bounded VC-dimension. Our bound is $2^{2^{O(r)}}$, independent of the number of vertices. The main ingredient is a VC-dimension bound for reachability through arbitrary fixed-length sequences of...
A family of symmetric counterexamples to the bent sum decomposition conjecture
In this paper, we provide an infinite family of counterexamples to Tokareva's conjecture on sums of two bent functions. The conjecture states that every Boolean function in an even number of variables $n$ of algebraic degree at most $n/2$ can be written as the sum of two bent functions. We show that for every $n=2^k\geq 8$, the symmetric function...
Counting graphs admitting a strictly matched involution
We study graphs admitting a strictly matched involution, i.e., graphs for which a strictly matched involution exists. A strictly matched involution of a graph $G$ is a self-inverse graph automorphism $f$ with the properties that the fixed point set of $f$ induces a complete subgraph in $G$ and, for the vertices that are no fixed points, every vertex is connected to its image under $f$ by an edge....
Polylogarithmic bound for the Gy\'arf\'as-Sumner conjecture
The classical Gy\'arf\'as-Sumner conjecture asserts that for any fixed forest $F$, any graph $G$ not containing $F$ as an induced subgraph, with bounded clique number $\omega(G)$, has bounded chromatic number $\chi(G)$. Recently, Nguyen, Scott, and Seymour proved that every such graph has chromatic number at most $|G|^{o(1)}$. We improve this bound to a polylogarithmic one $(\log |G|)^{O(1)}$.
Non-induced inherent graphs
Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete...
A Sub-$3^n$ Upper Bound on the Number of Stable Matchings
We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new $2.999^n$ upper bound on the number of stable matchings with $n$ men and $n$ women. This improves the best-known previous result by Palmer and P\'alv\"olgyi. This result gets much closer to the well-known lower bound...
Baxter Structures and the Odd-Even Enumeration of Red-Blue Motzkin Paths
We study Motzkin paths satisfying the red-blue rule introduced by Wu, Eu, Ku and Shih. We answer their Question 8.5 and exhibit two new Baxter structures. Let $\mathcal M_m$ denote the set of such paths of length $m$ and $a_m=|\mathcal M_m|$. We give a combinatorial proof of \[ a_{2n-1}=\mathrm{A005802}(n),\qquad a_{2n}=\mathrm{A216947}(n) \qquad (n\geq 1). \] For the odd subsequence, we...
A characterization of a family of integral Cayley graphs
Let $G$ be a finite group and $H$ be a subgroup of $G$. In our earlier work, we proved that the quasi-strongly regular Cayley graph $\Gamma_H(G)$ is integral whenever $H$ is normal in $G$, and raised the question of whether the converse also holds. In this paper, we answer this question affirmatively. We prove that if $\Gamma_H(G)$ is integral, then $H$ must be a normal subgroup of $G$....
Ideals of 2-minors of nearly determinantal matrices
We introduce nearly determinantal matrices and study their ideals of $2$-minors. We classify nearly determinantal matrices whose ideals of $2$-minors are prime. Furthermore, we characterize those nearly determinantal matrices whose ideals of $2$-minors are prime and Cohen--Macaulay with linear resolutions.
A $2.81^n$ upper bound on the number of stable matchings
We study the maximum number ${\rm SM}(n)$ of stable matchings in an instance with $n$ men and $n$ women. Karlin, Oveis Gharan, and Weber (STOC 2018) proved the first single-exponential upper bound; their argument gives ${\rm SM}(n)\le 2^{17n}$ for sufficiently large $n$. Palmer and P\'alv\"olgyi (FOCS 2021) improved this bound to $3.55^n+O(1)$. We prove that ${\rm SM}(n)<2.81^n$. This brings the...
How many sorted projections determine n points in k dimensions?
Let $d_1,\dots,d_m$ be directions in $\mathbb{R}^k$, where $k\ge 2$. A multiset $X$ of $n$ points of $\mathbb{R}^k$ projects to the $m$ multisets of numbers $\{\{x\cdot d_j : x\in X\}\}$, or equivalently to the $m$ sorted lists of these numbers. How many directions are needed for these projections to determine every multiset of $n$ points? Two simple bounds are known in every dimension: more than...
Cycles in Regular Multipartite Tournaments
We study balanced cycles in regular multipartite tournaments. A cycle in a $c$-partite tournament is $k$-balanced if it contains exactly $k$ vertices from each partite class. We prove that there exists an absolute integer $r_0$ such that every regular $c$-partite tournament with each partite class size of $r\ge r_0$ contains a $k$-balanced cycle for every $1\le k\le r$ when $c=3$ or $c\ge5$, and...
Planar Central Configurations of Four Equal Masses: Classification and Morse Indices
We study the planar central configurations of four equal positive masses under homogeneous interactions with force exponent $A>2$. For $2<A\le 3$, we prove that there are exactly four types of configurations up to similarity and relabeling: the square, the centered equilateral triangle, a unique nontrivial concave kite, and a unique collinear configuration. Combined with known results for $A>3$,...
Scopes arrangements and product formulas
We develop normalized abacus combinatorics for affine type \(C\). We also give explicit product formulas for the number of Scopes classes at every level and every positive depth in affine types \(A\) and \(C\).
On Partitions with Constant-Sum Gap Sequences
We introduce and study \emph{constant-sum gap partitions}: for a fixed nonnegative integer $C$, these are partitions $\lambda=(\lambda_1,\ldots,\lambda_k)$ whose successive differences $d_i=\lambda_{i+1}-\lambda_i$ satisfy $d_i+d_{k-i}=C$ for all valid $i$. We derive the generating function for this family, treating partitions of odd and even length separately, and compute it explicitly for $C=0,...
On the proof of multi-variable $n/d$-conjecture for hyperplane arrangements
In this article, we use Wu's method to prove Budur's multi-variable $n/d$-conjecture for completeness.
Four-colour counterexamples for monochromatic path partitions
In 1989, Gy\'arf\'as conjectured that the vertex set of every $r$-edge-coloured complete graph can be partitioned into at most $r$ monochromatic paths. The case $r=2$ follows from a theorem of Gerencs\'er and Gy\'arf\'as, and Pokrovskiy proved the conjecture for $r=3$. Recently, Li and Wang disproved the conjecture for all sufficiently large $r$, leaving open the smallest number of colours for...
Hamiltonicity and cycle factors in k-quasi-transitive digraphs of large diameter
A digraph is $k$-quasi-transitive if the endpoints of every directed path of length $k$ are adjacent. In this paper, we prove that every strong non-bipartite $k$-quasi-transitive digraph of diameter at least $k+2$ is Hamiltonian when $k\ge7$ is odd. Moreover, combined with the known even case, for $k\ge6$, we also prove that a strong bipartite $k$-quasi-transitive digraph of diameter at least...
On generalized $k$-token graphs with distinguishable tokens and a maximum capacity of $s$ tokens per vertex
Supertoken graphs \(F^s_{k\times1}(G)\), also known as generalized token graphs, model configurations of \(k\) distinguishable tokens on a graph \(G\), with at most \(s\) tokens at each vertex. We study structural and metric properties of these graphs in terms of the base graph. For regular \(G\), we characterize when \(F^s_{k\times1}(G)\) is regular. We show that bipartiteness is inherited from...
Small 5-chromatic unit-distance graphs in disks of radius 3/2, 5/4 and 23/20
We give three explicit unit-distance graphs in the plane with chromatic number 5 whose vertices lie in small disks: a graph with 773 vertices inside an open disk of radius 3/2, one with 5713 vertices inside an open disk of radius 5/4, and one with 8168 vertices inside an open disk of radius 23/20. The smallest examples previously reported for these radii have 11725, 11725 and 31171 vertices. All...
A Polynomial Erd\H{o}s-P\'osa bound for Eulerian digraphs
In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erd\H{o}s-P\'osa property. Specifically, they showed that every directed graph $D$ contains either $k$ arc-disjoint cycles or a set of at most $f(k)$ arcs that intersect every directed cycle. The function $f$, depending only on $k$, is however...
Constructing Cospectral Hypergraphs Using Adjacency Preserving Permutations
In this paper, we use permutations of the vertices of hypergraphs that preserve their adjacency matrices defined in banerjee 2021. These permutations form a group which lies between the automorphism group and the full symmetric group $S_n$ where $n$ is the number of vertices. Using elements from that group which are not automorphisms, we construct cospectral non-isomorphic hypergraphs. We use...
Highly connected uniquely $k$-linked digraphs
Extending a result of Thomassen, we prove that for every choice of positive integers $K\geq k$ there exist a $K$-strong digraph which has two disjoint sets $S,T$ each of size $k$ so that the only linkage from $S$ to $T$ in $D$ is the one whose existence follows from Menger's theorem.
Geodesic Transversal of Hypercube and Butterfly networks
A geodesic $P$ of a connected graph $G(V,E)$ is called a maximal geodesic if there exists no geodesic $P'$ in $G$ that contains $P$ as its sub-path. The geodesic transversal problem determines a subset $S\subseteq V(G)$ such that every possible maximal geodesic of $G$ includes at least one vertex of $S$. Such a set with minimum number of elements is called a gt-set and its cardinality is the...
Neighbourhood second Zagreb matrix of graphs: spectral radius bounds and extremal graphs
Let $G$ be a connected graph on at least two vertices, and let $\delta(i)$ be the sum of the degrees of the neighbours of a vertex $i$. The \emph{neighbourhood second Zagreb matrix} $\NF(G)$ has $(i,j)$-entry $\delta(i)\delta(j)$ if $i\sim j$ and $0$ otherwise; its spectral radius is denoted by $\rNF(G)$. We prove that $\rNF(G)\ge\rho(G)^{5}$, where $\rho(G)$ is the adjacency spectral radius,...
On the Cameron-Praeger conjecture for Steiner 6-designs
A long-standing and far-reaching conjecture of Cameron and Praeger (1993) asserts that no non-trivial block-transitive $6$-$(v,k,\lambda)$ designs exist. Huber (2010) reduced the Steiner case ($\lambda=1$) to a single infinite family of possible exceptions, where the automorphism group is $G=\PGaL(2,p^e)$ acting on the points of the projective line, with $p\in\{2,3\}$ and $e$ an odd prime power....
Finiteness of Non-decomposable Critically Frustrated Signed Graphs
A signed graph $(G,\sigma)$ is a graph $G$ with a signature $\sigma$ labeling each edge with a positive or negative sign. Two signatures of $G$ are switching equivalent if one is obtained from the other by sequentially changing the signs of all edges in an edge-cut. The frustration index of a signed graph $(G, \sigma)$ is the minimum number of negative edges among all signatures switching...
Coherent configuration on 3-uniform hypergraph over strongly regular graph
This paper investigates coherent configurations on 3-uniform hypergraphs constructed from strongly regular graphs. We establish that the hypergraph preserves the automorphism group of the original graph and induces a nonhomogeneous Schurian coherent configuration. Using the case of Petersen graph, we obtain a configuration with two fibers and thirteen basic relations. We further determine their...
Exact $3$-Adic Periods of Symmetric Dellac Numbers and Their Polynomial Extensions
The odd and even symmetric Dellac numbers are the specializations $a_n=f_n(0)$ and $e_n=f_n(1)$ of the Randrianarivony--Zeng family $f_n(s)=2^{-n}D_n(s)$. Using a finite Stieltjes-fraction truncation, we establish the sharp congruence $v_3(a_n)=1$ for $n\ge2$ and obtain explicit congruences modulo $81$ for both sequences. We also establish universal eventual periodicity modulo arbitrary positive...
One-Vertex Lifts of Looped Circle Graphs: Obstructions and Interlace Polynomials
Let $M$ be the adjacency matrix of a looped simple graph over $\mathbb{F}_2$ and let $t=\operatorname{diag} M$. We study the one-vertex lift with adjacency matrix $\left(\begin{smallmatrix}M+tt^T&t\\t^T&0\end{smallmatrix}\right)$. A looped circle graph is called stable if its lift is a circle graph. We prove that stability is equivalent to the existence of a pseudo-orientable bouquet realizing...
An Asymptotic for E. P. Stein Numbers
Epstein's put-or-take-a-square game is an impartial combinatorial game in which a player may, in each turn, add or subtract the largest square not exceeding the current integer. We study E. P. Stein numbers, the positions from which both legal moves lead directly to positive squares, and prove the following asymptotic formula for the counting function $S_2(X)$ of these positions: \[...
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Let $\mathcal{C}_k$ be the doubly-extended Reed--Solomon code with parameters $[q+1, k, q-k+2]_q$. We give a complete characterization of when its codewords of a fixed weight form $q$-ary 2-designs. The main ingredient is an exact criterion showing that the number of $r$-subsets of $\mathbb{F}_q^*$ with a prescribed product is independent of that product if and only if $\gcd(r, q-1)=1$. Applying...
Cyclotomic factorization and fixed-point insertion in colored permutation groups
We extend cyclotomic Euler--Mahonian factorization to colored permutation groups for two inversion statistics: Biagioli--Zeng length and the inversion number of the underlying unsigned permutation. At a primitive $m$th root and rank $n=mk+i$, each normalized enumerator is a Hadamard product of a rank-$i$ colored enumerator and a weighted rank-$k$ type-B enumerator. Separate color variables are...
A toric approach to social choice theory
This paper initiates a systematic study of objects in convex geometry and toric algebraic geometry arising from status quo systems in social choice theory. Our main application is to classify all cones arising from a large class of status quo systems that are smooth or simplicial.
Orthogonal polynomials on two or more intervals: the Sprugnoli context
We show how the group of Sprugnoli arrays on three elements can be used to define families of polynomials that are orthogonal on two intervals, and we indicate how the group can be extended in the hierarchy of Sprugnoli groups to yield families of orthogonal polynomials with more complex supports. In particular, we examine the defining three term recurrences and the Jacobi matrices of these...
Linear Cotype Bounds for Nonlinear Spectral Gaps of Scalar Expanders
Let $G$ be a finite simple $d$-regular graph, $d\geq 3$, whose second largest adjacency eigenvalue satisfies $\lambda_2(G)\leq (1-\delta)d$, where $0<\delta\leq 1$. We prove that the Poincar\'e constant satisfies $$\gamma(G,\|\cdot\|_X)\lesssim \frac{qCK}{\delta}$$ whenever $X$ is a real Banach space with a $K$-unconditional Schauder basis and cotype $q$ with constant $C$. This constant compares...
Linear-length cycles in the supercritical percolated hypercube
Let $Q_p^d$ be the random subgraph of the $d$-dimensional binary hypercube obtained by retaining each edge independently with probability $p$. A long-standing folklore conjecture states that the emergence of the giant component in $Q_p^d$, at $p\approx 1/d$, is accompanied by the emergence of cycles of linear length. We confirm this conjecture and determine the order of the longest cycle near the...
On Diameter Graphs Problems: A proof of Brass's Conjecture
The diameter graph of a finite set $S\subset\mathbb{R}^d$ has vertex set $S$ and two points are adjacent when their distance equals $\operatorname{diam} S$. In this paper we study the following question: given $k$ and $d$, is there a constant $c=c(k,d)$ such that from every finite point set $S\subset\mathbb{R}^d$ one can remove at most $c$ points so that the subgraph of the diameter graph induced...
Almost All 3-uniform Hypergraphs are Class 1
The chromatic index $\chi'(H)$ of a hypergraph $H$ is the smallest number of colors needed to color its edges so that no two adjacent edges share the same color. The chromatic index is trivially bounded below by the maximum degree $\Delta(H)$, and when $\chi'(H)= \Delta(H)$, we say that $H$ is Class 1. It is well known that almost every 2-graph is Class 1, and we extend this result to 3-graphs....
Non-redundant Independence Atoms
Independence atom is a key concept in relational database theory. In the present paper, we prove that the maximum possible size of a non-redundant set of independence atoms on $n$ attributes is asymptotically $(1+o(1))\binom{n}{\floor{n/2}}$. It turns out that this problem is closely related to two extremal set theory problems, the Katona-Tarj\'an question on ``V''-free families of subsets of...
Only titles, authors and the start of each abstract are shown here, as arXiv published them. Open a paper to read its whole abstract and, with your own AI key, a plain-language summary. Papers on arXiv are preprints and may not have been peer reviewed.
Data from arXiv, used through the arXiv API. Thank you to arXiv for use of its open access interoperability.