Papers

Let $F$ be a connected color-critical graph with $\chi(F)=r+1\ge4$, let $S_{n,\Delta}^{(r)}=(n-\Delta)K_1\vee T(\Delta,r-1)$. We determine the graph of maximum adjacency spectral radius among all $n$-vertex $F$-free graphs with prescribed maximum degree $\Delta$. There is a constant $s_F\in[0,1)$ such that, for all sufficiently large $n$, $\left\lceil\frac{(r-1)n}{r}\right\rceil\le \Delta\le n-\Theta(n^{s_F})$ implies that every $n$-vertex $F$-free graph $G$ with $\Delta(G)=\Delta$ satisfies $\rho(G)\le \rho\bigl(S_{n,\Delta}^{(r)}\bigr)$, with equality if and only if $G\cong S_{n,\Delta}^{(r)}$. This is the spectral counterpart of the edge theorem of [European J. Combin. 106 (2022), 103576.] and extends the clique result in [arXiv:2608.26634, 2026.]. This result also provides a benchmark for unbalanced spectral Turán problems arising from other extremal parameters.

Recently, Ehrenborg, Hetyei and Readdy expressed the toric $g$-polynomial of a simple polytope as a linear combination of a family of polynomials, called $g$-contribution polynomials, with coefficients given by the entries of its gamma-vector. They conjectured that these toric $g$-contribution polynomials are real-rooted. This paper proves this conjecture.

A longstanding fundamental problem of Burr, Erdős, Faudree, Rousseau and Schelp (Trans. Amer. Math. Soc., 1982) is to determine the exact value of the least integer $f(m)$, for odd $m\ge3$, such that every tree $T_n$ on $n\ge f(m)$ vertices satisfies $R(T_n,C_m)=2n-1$. We settle this problem for all sufficiently large odd $m$. Indeed, we establish $$f(m)=\left\lceil \frac{2m-1}{3} \right\rceil$$ for all such $m$, where the lower bound follows from a result by Faudree, Lawrence, Parsons and Schelp. This also confirms a conjecture of Huang, Zhang and Chen for all such $m$.

Let $\Cvec$ be a fixed orientation of the cycle $C_\ell$, $\ell\ge3$, which is not directed. For an oriented graph $D$, let $d_D^*(v):=\max\{d_D^+(v),d_D^-(v)\},$ and let \[ \sigore(D):=\min\bigl\{d_D^*(x)+d_D^*(y):x\ne y,\ xy,yx\notin A(D)\bigr\}, \] with $\sigore(D)=\infty$ if the underlying graph of $D$ is complete. We prove that, for every $\mu>0$, there exist $\gamma>0$ and $n_0$ such that every $n\ge n_0$ with $\ell\mid n$ and every $n$-vertex oriented graph $D$ satisfying \[ \alpha(D)\le\gamma n \text{ and } {\sigore(D)\ge\left(\frac34+\mu\right)n} \] contains a $\Cvec$-factor. {Additionally, for every fixed $s\ge2$ and every fixed real constant $C$, we construct arbitrarily large oriented graphs with $\sigore(D)\ge \frac34n+C$ that contain no $C_{2s}^{\ad}$-factor. More precisely, $C:=\frac34\alpha(D)-2$ for $s=2$ and $C:=\frac14\alpha(D)-\frac32$ for $s\ge3$.} This paper develops a weighted reduction framework adapted to dominant degree condition, proves the absorption lemma via closed-cluster merging with even-walk, and derives almost-perfect tiling structures by virtue of Farkas-lemma-based fractional decomposition.

We prove that every monic palindromic real-rooted polynomial with nonnegative integer coefficients is the $h$-polynomial of a simplicial convex polytope. This resolves in the affirmative a longstanding problem circulated by Brenti since 2004.

In Lazy Cops and Robbers, at most one cop moves on each cop turn. We study the lazy cop number of the generalized hypercube $Q(n,m)$, whose vertex set is ${\{0,1,\ldots,m\}}^n$. For each fixed integer $m\geq2$, we prove the asymptotic upper bound $$c_{\mathrm{L}}(Q(n,m))=O\!\left(\frac{{(m+1)}^n}{n^{3/2}}\right).$$ This result improves the upper bound of Sim, Tan, and Wong by a factor of $\log n$. The proof combines a moving dominating-set argument with an explicit dominating-set construction inside the support classes of each level. As a separate domination result, we show that, for fixed integers $m\geq2$ and $d\geq1$, the Hamming graph $K_m^{\square k}$ has a distance-$d$ dominating set of asymptotic size $O(m^k/k^d)$. This order is optimal up to a constant factor.

We prove that for every integers $d \ge 1$ and $s\ge2$ there exists an integer $D$, that depends only on $d$ and $s$, such that for every graph $P$ with maximum degree at most $ d$, there is a graph $H$ with maximum degree at most $D$ in which every $s$-coloring of $V(H)$ yields a monochromatic subdivision of $P$.

Erdős and Graham asked whether every finite coloring of the plane must contain a monochromatic rectangle of any prescribed area. Kovač gave a negative answer by constructing a $25$-coloring with no monochromatic rectangle of area $1$. We reduce the number of colors to $21$ by replacing the square cells in his construction with regular hexagons.

We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its original one. We define the stable chromatic number $\chi_\mathrm{stable}(G)$ of a graph $G$ as the minimum integer $k$ such that every preference profile admits a stable $k$-coloring of $G$. We establish several upper and lower bounds. In particular, for any acyclic orientation of the edges of $G$, the largest number of vertices reachable from a vertex by directed paths, including the vertex itself, is an upper bound on $\chi_\mathrm{stable}(G)$. This shows that $\chi_\mathrm{stable}(G)$ is well-defined. We also show that $O(t \log (1+n/t))$ colors suffice for an $n$-vertex graph $G$ of treewidth $t$, and complement this with a lower bound in terms of the Grundy number. Turning to the problem of finding a minimum stable coloring for a given profile, we show that stable $2$-colorability is polynomial-time solvable, whereas stable $k$-colorability is NP-complete for every fixed $k\ge 3$. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.

In this paper we study the resultant of systems of homogeneous multivariate polynomials which are equivariant under the action of a direct product of symmetric groups. We first treat, in detail, the case of a product of two symmetric groups, and establish a decomposition formula for the resultant of such systems. We then show that this decomposition, together with the underlying combinatorics, extends to an arbitrary (finite) direct product of $r$ symmetric groups. Thanks to these decomposition formulas, we prove that the discriminant of a multivariate homogeneous polynomial invariant under a direct product of $r$ symmetric groups splits into a product of resultants of smaller size that are easier to compute.

Call a permutation of a set of positive integers admissible if it contains no increasing or decreasing three-term arithmetic progression in position order. Davis, Entringer, Graham, and Simmons proved that the positive integers are not admissibly permutable, partitioned them into three admissibly permutable sets, and asked whether two sets suffice. We study the canonical dyadic candidate S_A, the union of the blocks (2^{k-1}, 2^k] over even k >= 2. We establish several structural restrictions on admissible permutations, including an orbit obstruction, an asymmetric balance law, and the impossibility of placing all sufficiently large dyadic blocks as contiguous runs. For the main result, we reduce admissibility of S_A to feasibility of an order gadget on (M, 2M]: the order must avoid monotone three-term progressions and satisfy fifteen precedence constraints induced by the values 15 and 16. We then prove that a three-constraint core of this gadget is inconsistent for every M congruent to 0 mod 8, using zigzag propagation on arithmetic-progression ladders, a transfer lock, and mirror-flood induction. Since every relevant dyadic scale lies in this residue class, S_A admits no admissible permutation. Thus the canonical dyadic partition does not solve the two-set problem, which remains open. Independent SAT encodings and certificate checks provide auxiliary verification of the human-readable proof.

We introduce folded-algebraic matroids. In such a representation, every matroid element is replaced by a finite tuple of algebraic quantities, and transcendence degree agrees with matroid rank after one uniform scaling. The resulting class contains both algebraic and folded-linear matroids and is contained in the class of almost-entropic matroids, whose rank functions are limits of scaled entropy functions. We prove that the latter containment is proper. Our main result concerns the classical rank-three matroids $M(p)$ of Gordon. For every prime $p$, we show that $M(p)$ has a folded-algebraic representation over a field $K$ if and only if $K$ has characteristic $p$. We then use a point-identification construction that preserves almost-entropicity to obtain a $13$-element rank-three $3$-connected matroid $C_{2,3}$ that is almost entropic but not folded algebraic. Choosing a common element as dealer also yields a connected $12$-participant port with incompatible characteristic requirements. Finally, we record compact explicit witnesses and size bounds for several other separating regions among the representation classes.

Which vertex-transitive graphs of prime order have quantum symmetry? The question of Banica, Bichon and Chenevier is open in the dense regime of Paley graphs, where coherent-algebra methods give no information. To each such graph we attach a two-basepoint Terwilliger algebra of its cyclotomic scheme and study the module it generates from the basepoints: fullness forces the quantum permutation algebra to be commutative, and the module admits no intermediate state, containing either exactly two point masses or all $p$ of them. One point mass, captured at any depth, therefore suffices, and Chassaniol's orbital criterion is the depth-one case. Three consequences follow. A sharp counting argument replaces the Banica–Bichon–Chenevier threshold $p>6^{\varphi(k)}$ by the quadratic bound $p>(k-1)(k-2)+2$, where $k$ is the type. Four certificates, each a short list of additions modulo $p$, settle $C_{31}(2,4,8,15)$ and $C_{41}(4,10,16,18)$, the two graphs left open by Chassaniol, and complete the classification for type at most $10$ without machine assistance. An exact computation extends the dichotomy “quantum symmetry if and only if complete or empty” to all prime orders $p\le250$, settling the Paley graphs $P_{p}$ with $p\le241$, the first beyond $P_{17}$. What remains is the capture of a single explicit vector: the midpoint $2^{-1}$ of the two basepoints.

Let $X_1,X_2,\ldots$ be i.i.d. finitely supported random variables in a torsion-free abelian group, and write $S_k=X_1+\cdots+X_k$, and $H(S_k)$ is the Shannon entropy $S_k$, for all $k \ge 1$. We prove that, for every fixed $n\geq1$, \[ H(S_{n+1})-H(S_n) \geq \frac12\log\frac{n+1}{n} -o_{H(X_1)\to\infty}(1), \] uniformly over the ambient group and the input law. This proves a conjecture of Tao [29] in 2010.

Kalai's cube–simplex conjecture asserts that for all positive integers $\ell,k$, there is an integer $f(\ell,k)$ such that every polytope of dimension at least $f(\ell,k)$ has either a simplex $\ell$-face or a cube $k$-face; let $f_s(\ell,k)$ denote the threshold restricted to simple polytopes. Finiteness of $f(\ell,k)$ is known only for $\ell,k \leq 2$. In addition, Kalai proved that $f_s(2,k) \leq 2k^2$. Here we prove that $f_s(\ell,k)$ is finite for all $\ell \geq 2$ and $k \geq 3$, the first such result beyond $\ell = 2$, with $f_s(2,k) \leq 2k^2-1$ and $f_s(\ell,k) \leq \tfrac{1}{2}k^2\ell\,2^k$ for $\ell \geq 3$. In the opposite direction, we obtain the lower bounds $f(\ell,k) \geq (5\lfloor \ell/2 \rfloor + (\ell \bmod 2) - 1)(k-1)+1$ and $f_s(\ell,k) \geq \max\{4,\,2(\ell-1)\}(k-1)+1$. A companion question asks for the minimum possible size of a 3-face within a higher-dimensional polytope. Meisinger, Kleinschmidt and Kalai proved that every rational $d$-polytope with $d \geq 9$ has a $3$-face with fewer than $78$ vertices or fewer than $78$ facets. Here we improve their bound: every convex polytope of dimension at least $15$ has a $3$-face with at most $13$ facets. One step of our proof requires an explicit exact rational certificate or identity on flag numbers. This certificate is computed using linear programming.

Pseudosimilar vertices are vertices in distinct automorphism orbits whose deletions produce isomorphic graphs. Classical work has studied the existence, group-theoretic origin, and construction of large sets of such vertices. We ask a different recursive question: how long can one repeatedly delete a vertex that is pseudosimilar at the moment of deletion? We define the pseudosimilarity depth of a graph and construct connected graphs in which this process continues through all but a sublinear number of vertices. A two-clock construction gives a square-root deficit uniformly in the order, while a Chinese-remainder construction with many cyclic clocks yields an infinite family of asymmetric graphs with only a polylogarithmic number of vertices left outside the active chain. The mechanism realizes pseudosimilarity by breaking a long hidden automorphism orbit and enlarging the break one vertex at a time. Thus pseudosimilarity can persist through an asymptotically full sequence of vertex deletions, even though every graph encountered in the main construction is asymmetric.

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.

A graph $G$ is $k$-choosable if it has a proper coloring for every $k$-list assignment. While every $C_3$-free planar graph is $4$-choosable, some of them are not $3$-choosable, as constructed by Voigt. Hu and Zhu conjectured that if $G$ is a $C_3$-free planar graph and $X \subseteq V(G)$ induces a bipartite subgraph, then $G$ has a proper $L$-coloring whenever $|L(x)| = 3$ for $x \in X$ and $|L(v)| = 4$ for $v \in V(G) \setminus X$. As evidence, they proved the conjecture when $X$ is an independent set. We provide further evidence by proving the conjecture when the induced subgraph $G[X]$ is an induced sparse matching. This is the first result supporting the conjecture in which the set $X$ receiving smaller lists may induce a subgraph with edges.

The Kneser graphs $\text{KG}(n,k)$ are a classically studied family of graphs. One known invariant of graphs is gonality (also called divisorial gonality), which is the minimum degree of a rank 1 divisor on the graph. Using known bounds on gonality of simple, connected graphs, one may obtain that the gonality of $\text{KG}(n,k)$ is bounded above by $\binom{n-1}{k}$. In 2014, Harvey and Wood showed that the treewidth (a lower bound on gonality) for $\text{KG}(n,k)$ is $\binom{n-1}{k}-1$ for $n\geq 4k^2-3k+2$. In this paper, using scramble number, another lower bound on gonality, we improve this polynomial bound and show that the gonality of $\text{KG}(n,k)$ is exactly $\binom{n-1}{k}$ for $n\geq \frac{3k^2+k+2}{2}$, and conjecture an even stricter polynomial bound using the uniform edge scramble. We then extend our argument to the family of generalized Kneser Graphs, computing the scramble number and gonality using the same polynomial bound.

We confirm a conjecture of Brause, Randerath, Rautenbach and Schiermeyer (2016) by proving a localized lower bound on the independence number of a graph that strengthens the classical bounds of Fajtlowicz (1978) and of Caro (1979) and Wei (1981), which in turn settles a conjecture by Bertram and Horák (1996). Our proof is based on a new Motzkin–Straus-type inequality involving local clique numbers and the independence number. We then apply the developed methods to study spectral and algebraic measures of graph bipartiteness. In particular, we extend a theorem of Brandt (1998) on spectral bipartiteness from regular $K_{r+1}$-free graphs to all $K_{r+1}$-free graphs, we improve a general upper bound for the least signless Laplacian eigenvalue of $K_{r+1}$-free graphs, and we disprove a conjecture of de Lima, Nikiforov and Oliveira (2016) in the case of $K_4$-free graphs.

A quiver representation consists of a collection of vector spaces along with a set of arrows, which are linear maps between these spaces. In this work, we study quiver representations in equioriented type $A$ which are also chain complexes; that is, in which consecutive arrows compose to zero. We show that orbits of these representations under a change of basis action are in bijection with mixed dimer covers of a $2 \times n$ grid graph. The latter object can be endowed with a partial order which is a distributive lattice, and we show that the degeneration order on the orbits of chain complexes is a coarsening of this partial order. In addition, we use recent matrix formulae of Claussen and Ovenhouse to enumerate these orbits. This also computes the Kostant partition function applied to height-restricted, type $A$ roots. When the dimension vector is uniform, we discuss a correspondence with paths of a beam of light bouncing between glass plates and give an explicit generating function.

We show that the subleading collinear sector of Yang-Mills (YM) amplitudes is controlled by ordinary Einstein-Yang-Mills (EYM) amplitudes and their higher-derivative corrections. The complete set of strict subleading collinear limits associated with an equal-helicity collinear pair can be extracted from open-closed string disk amplitudes. The latter generate $\frac12 (n-3)!$ BCJ-like relations with non-linear kinematic coefficients, reducing the $(n-3)!$ collinear data to a basis of dimension $\frac12 (n-3)!$. This reduced basis can be represented by gravitational amplitudes in EYM theories and by their higher-derivative open-string corrections. At multiplicity $n$ this gravitational basis consists of the $(n-4)!$ independent EYM subamplitudes together with $\frac12 (n-5)(n-4)!$ higher-order corrections involving one graviton and $n-2$ gluons. The resulting decomposition is governed by unsigned Stirling numbers of the first kind: the ordinary EYM amplitudes correspond to the sector $\left[{n-3\atop 1}\right]$, the higher-order BCJ-like relations to even sectors $\left[{n-3\atop 2j}\right]$, and the higher-derivative EYM corrections to odd sectors $\left[{n-3\atop 2j+1}\right]$ with $j\geq 1$.

The generating graph $\Gamma(G)$ of a group $G$ is the graph whose vertex set is $G$, where two distinct vertices are adjacent if and only if they generate $G$. In this paper, we systematically study the structure of generating graphs of finite abelian groups (non-cyclic) and determine the set of all generating pairs. Moreover, we give some structural characterizations, in particular, we determine conditions under which $\Gamma(G)$ is regular, characterize when the isolated vertices form a subgroup, and establish necessary and sufficient conditions for two non-isomorphic finite abelian groups $G$ and $H$ to satisfy $\Gamma(G)\cong \Gamma(H)$. Furthermore, we compute the spectra of the adjacency and Laplacian matrices of these graphs.

Using the Andrews–Askey integral, we derive a holomorphic extension formula for a Jackson $q$-integral. This formula allows identities established for terminating specializations to be continued to the nonterminating case. Our first application yields two companion binomial-type double-sum formulas. The second formula contains, as special cases, the nonterminating Sears–Carlitz transformation of Gasper and Rahman and Rahman's generating function for the Askey–Wilson polynomials. Applying the same method to the $q$-Chu–Vandermonde and Rogers' ${}_6\phi_5$ summations, we obtain two further integral representations for double sums of basic hypergeometric type. A balanced ${}_4\phi_3$ specialization of the latter identity is equivalent, via Sears' transformation, to the double-series transformation of Ismail, Rahman, and Suslov.

In this paper, we initiate the study of colored exponential random graph models (ERGMs), a class of exponential-family models for networks with multiple types of edge relations. Using the framework of probability graphons, we first derive a variational representation for the limiting free energy, whose maximizers determine the asymptotic structure of typical samples from the model. Then we identify several general families of colored ERGMs exhibiting replica symmetry, where the variational problem has constant maximizers and the model asymptotically concentrates on product colorings with independent edges. For general colored ERGMs, we derive Euler-Lagrange fixed-point equations for the variational maximizers, which in turn yield a general high-temperature uniqueness criterion. In the complementary zero-temperature regime, we establish a two-level selection principle: the leading energy term determines the ground states, while the lower-order energy terms, combined with entropy, act as a tie-breaker to determine the asymptotic zero-temperature structure of the model. We illustrate this principle through the induced wedge and rainbow triangle ERGMs. Both models have natural interpretations in multitype networks, and their zero-temperature limits exhibit interesting structures that connect to well-known results in extremal combinatorics. We further establish finite-temperature symmetry breaking for both these models and complement the rigorous results with numerical experiments.

We determine the exact dimensional range in which a normalized longest signed sum, which we call a Bang vector, always satisfies the real polarization inequality: this prescription is universally valid if and only if \(n\leq 14\). For every \(n\geq 15\) we construct \(n\) unit vectors whose all-positive sum is, up to global sign, the unique longest signed sum, while its normalized direction has polarization product smaller than \(n^{-n/2}\). The counterexamples are given by a single explicit family, and for the same configurations we exhibit nonmaximal signed sums whose normalized directions do satisfy the polarization bound.

We study the partition regular properties of topological groups, proving several extensions of Hindman theorem where monochromatic sets of finite sums are required to satisfy additional topological constraints. In particular, our results imply that for every nowhere dense set $C \subseteq \mathbb{R}^n$, there exists an open set $P \supseteq C$ such that for any finite coloring of $\mathbb{Q}^n \setminus P$, there is a family $\mathcal{A}$ of sequences in $\mathbb{Q}^n \setminus P$ which satisfies the following properties: (i) for each $A\in\mathcal A$, the set $\operatorname{FS}(A)$ of finite sums of $A$ is a closed discrete subset of $\mathbb R^n$; (ii) the set $\bigcup_{A\in\mathcal A}\operatorname{FS}(A)$ is monochromatic; and (iii) the set $\bigcup_{A\in\mathcal A}\operatorname{FS}(A)$ is dense in an open unbounded subset of $\mathbb R^n$.

For a row-finite weighted graph $(E,w)$, Preusser showed that the monoid $\mathcal{V}(L_k(E,w))$ of finitely generated projective modules over the weighted Leavitt path algebra $L_k(E,w)$ is isomorphic to a combinatorially defined weighted graph monoid $\mathcal{M}(E,w)$. We study two structural properties of $\mathcal{M}(E,w)$: confluence and cancellativity. We introduce a reduction system on the free commutative monoid presenting $\mathcal{M}(E,w)$, obtain sufficient conditions for non-confluence by constructing explicit non-confluent triples, and provide a complete confluence characterization for certain classes of weighted graphs. Turning to cancellativity, we work within Preusser's class of weighted graphs satisfying Condition (LPA), for which $L_k(E,w)$ is isomorphic to an unweighted Leavitt path algebra $L_k(F)$ via a two-step construction. We introduce an auxiliary graph associated to the intermediate step of this construction and use it to give a graph-theoretic characterization of when $\mathcal{M}(E,w)$ is cancellative. Finally, under Condition (LPA), we show that Preusser's construction upgrades to a graded isomorphism $L_k(E,w) \cong_{\operatorname{gr}} L_k(F)$ with respect to the standard $\mathbb{Z}^{\lambda(E,w)}$-grading of weighted Leavitt path algebras, yielding $\mathcal{V}^{\operatorname{gr}}(L_k(E,w)) \cong \mathcal{V}^{\operatorname{gr}}(L_k(F))$ as $\mathbb{Z}^{\lambda(E,w)}$-monoids.

We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight analysis of Anari and Rezaei gives a universal comparison between the permanent and the Bethe permanent within a factor $(\sqrt 2)^n$. The simple example of the unweighted $4$-cycle $C_4$ (or a union of disjoint $C_4$'s) shows that this bound is tight. We show that such $4$-cycle obstructions can be identified and exploited algorithmically. Given a Bethe optimizer, our algorithm identifies nearly isolated weighted $2\times2$ blocks and peels off a vertex-disjoint family of them. If the total weighted correction is large, we can improve the Bethe approximation; if it is small, we show that the Bethe permanent is within a factor of $(\sqrt2 - \varepsilon)^n$ of the truth. Combining these facts, we obtain a deterministic polynomial time $(\sqrt2-\varepsilon)^n$-approximation algorithm for the permanent of an arbitrary nonnegative $n\times n$ matrix, where $\varepsilon>0$ is some absolute constant.

For a connected and non-complete graph $G$ of order $n$, its toughness is defined as \[ \tau(G)=\min\bigl\{|S|/c(G-S):S\subseteq V(G),\ c(G-S)>1\bigr\}, \] where $c(G-S)$ denotes the number of components of $G-S$. Let $\alpha(G)$ denote the independence number of $G$. An elementary bound on toughness is $$\tau(G)\leq\frac{n-\alpha(G)}{\alpha(G)}.$$ Fix $p\in(0,1)$, and let $G(n,p)$ be the binomial random graph on vertex set $[n]$. Set $a=\alpha(G(n,p))$. In this paper, we mainly prove that \[ \tau(G(n,p))\in\left\{\frac{n-a}{a},\frac{n-a-1}{a}\right\} \] with high probability.