New on arXiv
Sort: by field | by arXiv number | trending
Mathematics
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...
Hamilton cycles in bicirculants with non-coprime connection sets
A bicirculant is a regular graph that admits an automorphism having two vertex-orbits of the same size. A bicirculant can be described as follows. Given an integer $m \ge 1$ and sets $R, S, T \subseteq \mathbb{Z}_m$ such that $R=-R$, $T=-T$, $0 \not\in R \cup T$ and $0 \in S$, the graph $B(m;R,S,T)$ has vertex set $V=\{u_0,\dots,u_{m-1},v_0,\dots,v_{m-1}\}$ and edge set $E=\{u_iu_{i+j}| \ i \in...
Stabiliser codes over prime fields as weighted graphs and as quantum sets of lines
We further develop the theory of quantum stabiliser codes and its links with graph theory and finite geometry. We prove that an [[n,k,d]]_p stabiliser code over a finite field with p elements, p prime, gives rise to a graph on n-k vertices together with two disjoint independent sets of size k. Its edges are weighted with elements of a finite field of size p. If k=0, such codes are known as graph...
Extremal even-cycle-free subgraphs of the $k$-ary $n$-cube
A graph is said to be $H$-free if it contains no subgraph isomorphic to $H$. The generalized Tur\'{a}n number $\mathrm{ex}(G, H)$, a natural extension of the classical Tur\'{a}n number, is defined as the maximum number of edges in an $H$-free spanning subgraph of $G$. For any integer $\ell\geq 2$, let $C_{2\ell}$ denote the even cycle of length $2\ell$. So far, extensive studies of the...
On the most informative Boolean function under noise
Let $X$ be a uniform random bit string and $Y$ be obtained by flipping each bit of $X$ independently with probability $p$. Let $C$ be a random bit obtained as a function of $Y$. We show that $\mathbf{I}(C:X)\le \mathbf{I}(Y_1:X)$ for all $p\in[0,1]$, which resolves a conjecture posed by Courtade and Kumar in 2013.
The Borodin--Kostochka inequality from degree 750
We prove that every finite simple graph $G$ with maximum degree at least $750$ satisfies $\chi(G)\le\max\{\omega(G),\Delta(G)-1\}$. The proof starts with a random partial colouring and completes it on large cliques using a list-colouring condition that remains valid as the rest of the graph is coloured. Disjoint stars provide the required colours. We estimate the number of stars that can be...
Isosceles sets in Euclidean spaces of dimension nine to twenty-two
A finite set of points in $\mathbb{R}^d$ is isosceles if every three of its points form an isosceles triangle. Erd\H{o}s asked in 1946 for the largest size $\mathrm{iso}(d)$ of an isosceles set in $\mathbb{R}^d$. The answer was known for $d\le 8$, the last cases being due to Ionin. We prove that $\mathrm{iso}(d)=\binom{d+1}{2}+1$ for $9\le d\le 21$ and $\mathrm{iso}(22)=276$, and that the...
Applying Changes to LDPC Codes by Using 3-Induced Matchings and Eigenvalues
The 2-switch operation for reducing the number of short cycles in Tanner graphs of LDPC codes has been utilized in some works. If this operation is appropriately applied to a 2-induced matching in a bipartite graph, then it surely preserves the bipartiteness of the graph. With a 2-induced matching, we have only one choice for applying this type of change to the graph. Using 3-induced matchings...
The Liouville property for geometric graphs in the plane
We show that every bounded discrete harmonic function with respect to the cotangent Laplacian on a Delaunay triangulation of the Euclidean plane is constant; equivalently, the cotangent-weighted triangulation has the Liouville property. Our main theorem establishes this property for a more general class of connected weighted geometric graphs in the plane. Furthermore, we show that a planar...
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.