Papers

The complementary prism $G\overline{G}$ of a graph $G$ is obtained from the disjoint union of $G$ and its complement $\overline{G}$ by adding an edge between each vertex $a$ in $G$ and its copy $a'$ in $\overline{G}.$ This paper explores a general framework for studying fractional revival with respect to real symmetric matrices with a block structure. The framework is then used to show that, for a fixed state $\mathbf{u}$ in $G$ orthogonal to the all-one vector, the complementary prism $G\overline{G}$ exhibits fractional revival from the state $[\mathbf{u},\mathbf{0}]^T$ with respect to the adjacency, Laplacian, and signless Laplacian matrices. We further characterize perfect pair state transfer in the complementary prism of a complete graph and establish the existence of perfect pair and plus state transfer in the complementary prism of a complete bipartite graph.

The celebrated result of Johansson, Kahn and Vu determined the threshold order for clique factors in random graphs, and subsequent work identified the sharp threshold and the corresponding hitting-time phenomenon. In this paper we study the probability that there is no $K_r$-factor above the threshold and, more generally, the probability that the largest $K_r$-matching covers less than $n-s$ vertices of $G(n,p)$. For every fixed $r\ge3$, throughout the range $$n^{-2/r}(\log n)^{1/\binom r2}\ll p\ll n^{-2/(r+1)},\qquad n-s\in r\mathbb Z,\qquad s=o(n),$$ we prove $$\mathbb P\bigl(\phi_r^s(G(n,p))=0\bigr)=\exp\left(-\Theta_r\!\left((s+1)\frac{\mu_r(n,p)}n\right)\right),$$ where $\phi_r^s(G)$ is the number of $K_r$-matchings covering exactly $n-s$ vertices and $\mu_r(n,p):=\binom nrp^{\binom r2}$. The lower bound is given by $s+1$ vertices which lie in no copy of $K_r$. For the upper bound we develop an iterable one-root version of the Johansson–Kahn–Vu method. As a structural consequence, we show that the remainder of $G(n,p)$ outside every maximal $K_r$-matching has an almost-perfect $K_{r-1}$-matching throughout the sparse clique window. Independently, we prove a central limit theorem for the maximum $K_r$-matching number. Combining these inputs and a structural theorem for $r=2$ from our earlier work, we prove a central limit theorem for the chromatic number of very dense random graphs: for every $r\ge2$ and $n^{-2/r}(\log n)^{1/\binom r2}\ll p\ll n^{-2/(r+1)},$ $$\frac{\chi(G(n,1-p))-\mathbb E\chi(G(n,1-p))}{\sqrt{\mu_{r+1}(n,p)}/r}\xrightarrow{\mathrm d}\mathcal N(0,1),\qquad\operatorname{Var}\bigl(\chi(G(n,1-p))\bigr) \sim\frac{\mu_{r+1}(n,p)}{r^2}.$$ This settles the Surya–Warnke conjecture throughout the interior of every clique window with $r\ge2$, strengthening its concentration prediction to a Gaussian limit with asymptotically exact variance.

Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the sum of the largest Laplacian eigenvalues of graphs, Discrete Appl. Math., 170:95–103, (2014)], Rocha and Trevisan showed that the conjecture holds true for $1 \leq k \leq \lfloor g/5 \rfloor$, where $g$ denotes the girth of $G$. This bound on $k$ was later improved by Chen in [Improved results on Brouwers conjecture for sum of the Laplacian eigenvalues of a graph, Linear Algebra Appl., 557:327–338, (2018)], who established that the conjecture holds for $1 \leq k \leq \lfloor g/4 \rfloor$. In this article, we further strengthen these results by proving that the Brouwers conjecture holds for $1\leq k\leq\left\lfloor \frac{m(G)}{2}\right\rfloor,$ where $m(G)$ denotes the matching number of $G$. Since $m(G)\geq \lfloor g/2\rfloor$, the case constitutes a genuine improvement over the aforementioned results. As an application, we show that if $G$ is a graph of order $n$ and with a perfect matching, then the Brouwers conjecture holds for $1\leq k\leq \left\lfloor \frac{n}{4}\right\rfloor$. Finally, we provide a new perspective on verifying Brouwers conjecture by proving that $G$ satisfies the Brouwers conjecture if and only if for a fixed positive integer $h$, $\mathcal{S}_h(\overline{G})\leq e(\overline{G})+\binom{h+1}{2}$ holds whenever $\mathcal{S}_h(G)\leq e(G)+\binom{h+1}{2}$, where $\overline{G}$ denotes the complement of $G$.

Finding large lattice subgraphs in sparse Erdős–Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed $\delta\in (0,1)$, there exists $C_\delta>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-\delta)n$ in $G(n,p)$ with high probability whenever $p\ge C_\delta\sqrt{\ln k/n}$. Thus, for $k^2=\Theta(n)$, a density of order $\sqrt{\log n/n}$ is sufficient, a factor of order $\sqrt{\log n}$ above the corresponding $n^{-1/2}$ emergence scale.

Each of the 12 known conjecturally optimal kissing configurations in dimensions 5, 6, and 7 carries a contact-graph polytope: a polytope whose vertices are the configuration points and whose edges are exactly its contacts. Eight of these polytopes are non-convex and distinct from their convex hulls, which include longer edges. Each polytope is radial about the sphere's center: its boundary meets every ray from the center exactly once. It is the unique radial polytope with those vertices and edges. Seven of the nine non-lattice configurations carry polytopes constructed from the lattice contact polytope in the same dimension by splitting some facets and reassembling the pieces. This split-and-reassemble construction describes the configurations by facets rather than by layers. The fold angles of the reassembled facets explain the inner products $1/(10-n)$, giving $1/5$, $1/4$, and $1/3$ in dimensions 5, 6, and 7, respectively. The contact graphs of all 12 configurations are infinitesimally rigid. We also prove that $Q_5$ and $R_5$ are infinitesimally jammed, extending the 10 previously established cases to all 12 configurations. All mathematical computations use exact arithmetic.

A graph is $K_{r+1}$-saturated if it is $K_{r+1}$-free and adding any missing edge creates a copy of $K_{r+1}$. Kim, Kim, Kostochka, and O conjectured that $K_{r-1}\vee(n-r+1)K_1$ minimizes the spectral radius among all $n$-vertex $K_{r+1}$-saturated graphs. They proved the case $r=2$, and the cases $r=3$ and $r\in\{4,5\}$ were subsequently established by Kim, Kostochka, O, Shi, and Wang, and by Wang and Hou, respectively. We settle the conjecture for all $r\ge3$: if $n\ge r+1$ and $G$ is an $n$-vertex $K_{r+1}$-saturated graph, then \[ \rho(G)\ge \frac{r-2+\sqrt{(r-2)^2+4(r-1)(n-r+1)}}{2}, \] with equality if and only if $G\cong K_{r-1}\vee(n-r+1)K_1$. We also prove O's local two-walk conjecture for every $r\ge2$: \[ \sum_{w\in N_G(v)}d_G(w) \ge (r-2)d_G(v)+(r-1)(n-r+1) \qquad(v\in V(G)). \] If $G$ has no universal vertex, the inequality holds with the additional term $(r-1)(r-2)$ on the right-hand side. This constant is best possible uniformly in $n$ for every fixed $r$, and gives a strict improvement when $r\ge3$. A corresponding spectral bound follows.

We prove that the multiplicities of every symmetric $Q$-polynomial association scheme form a log-concave sequence. This resolves the 1984 unimodality conjecture of Bannai and Ito and establishes both related inequalities conjectured by Stanton. Our proof is a novel application of strong subadditivity and weak monotonicity inequalities for quantum entropy.

We introduce and study the rotating-memory Fibonacci numbers, a periodic variable-order analogue of the Fibonacci sequence in which the number of preceding terms used in the recurrence changes cyclically with the index. Despite this varying memory, the resulting sequences exhibit a remarkably rigid structure. We derive closed forms, rational generating functions, arithmetic properties, and exact growth behavior, and show that the sequence decomposes naturally into geometric subsequences. We also develop combinatorial interpretations in terms of periodically constrained tilings, and restricted compositions, including bijective explanations for the multiplicative structure of the sequence. In addition, the first two nonclassical periods admit natural geometry-driven realizations: the period-2 sequence arises from monomer–dimer tilings of a triangular chain, while the period-3 sequence is related to tilings of a double hexagon strip by single and double hexagons. These connections provide geometric interpretations of the rotating recurrence in which the periodic behavior is induced by the underlying structures themselves, and suggest a broader problem of constructing analogous models for higher periods.

A weighted dynamical version $\mathbf{Z}_f$ of the classical Ihara zeta function is presented on connected finite regular graphs, expressed in terms of weighted periodic orbit data. We establish its meromorphic continuation, with poles given by the resonances of the associated non-backtracking transfer operator acting on a suitable Banach space, and compute its residues. At simple spectral parameters, the residue of $\mathbf{Z}_f$ is identified with the invariant Ruelle distribution on the graph phase space. Combining this result with a relation obtained by Arends-Palmirotta, we further derive Patterson-Sullivan and Wigner residue formulae. This provides a finite-graph analogue of residue formulae for weighted dynamical zeta functions for geodesic flow on rank one locally symmetric spaces, in the spirit of Schütte-Barkhofen-Weich.

For a finite abelian group $\Gamma$, a map $f\colon V(G)\to\Gamma$ is a $\Gamma$-magic map if the sum of its values over the neighbors of a vertex is independent of the vertex. It is affinely generating if its pairwise differences generate $\Gamma$. When $|\Gamma|=|V(G)|$, a bijective $\Gamma$-magic map is a $\Gamma$-distance magic labeling. For a regular graph $G$ with adjacency matrix $A$, write $\mathbf1$ for the all-ones vector indexed by $V(G)$, and let $\overline A$ denote the endomorphism induced by $A$ on $\Lambda_{\mathbf1}=\mathbb Z^{V(G)}/\mathbb Z\mathbf1$. When $\overline A$ is nonsingular over $\mathbb Q$, define the reduced Smith group by $\mathsf S_{\mathrm{red}}(G)=\operatorname{coker}\overline A$. In previous work, we established that for every regular graph $G$ of positive degree with $\overline A$ nonsingular over $\mathbb Q$, one has \[ G\text{ admits an affinely generating }\Gamma\text{-magic map} \quad\Longleftrightarrow\quad \Gamma\hookrightarrow\mathsf S_{\mathrm{red}}(G). \] We determine this group explicitly for Kneser graphs. If $r\ge1$, $n\ge2r$, and $m_j=\binom nj-\binom n{j-1}$, then \[ \mathsf S_{\mathrm{red}}(K(n,r))\cong \bigoplus_{j=1}^{r} \left(\mathbb Z/\binom{n-r-j}{r-j}\mathbb Z\right)^{m_j}. \] When the labeling group and the Kneser graph have the same order, the resulting embedding criterion leaves only one case in which an affinely generating map exists. More precisely, if $\Gamma$ is an abelian group of order $\binom nr$, then $K(n,r)$ admits an affinely generating $\Gamma$-magic map if and only if $(n,r)=(9,2)$ and $\Gamma\cong\mathbb Z/6\mathbb Z\oplus\mathbb Z/6\mathbb Z$. A weak-Sidon-set bound shows that the affinely generating maps in the exceptional case cannot be bijective. Hence $K(n,r)$ admits no $\Gamma$-distance magic labeling throughout the range $r\ge1$ and $n\ge2r$.

In this work, we prove that any Boolean function of degree $d$ on $\mathbb{Z}_{q}^n$, $q\geq 3$, has at most $m_qq^d$ relevant variables, where $m_q=\frac{2q(q^2+4q+1)}{(q-1)^4}$. For $q\in \{3,4,5,6,7\}$, we improve this bound to $2.854\cdot 3^d$, $1.749\cdot 4^d$, $1.263\cdot 5^d$, $0.994\cdot 6^d$, and $0.814\cdot 7^d$, respectively.

A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let $q_B(G)$ be the minimum number of colors in such a coloring. Every graph of maximum degree $\Delta$ is $K_{2,\Delta+1}$-free; hence the known $2\Delta$ bound for planar graphs with $\Delta\ge38$ (Kong et al., 2026) motivates our study of $K_{2,t}$-free planar graphs, where $t\ge2$ is an integer. We prove $q_B(G)=\Delta(G)$ when $t=2$ and $\Delta(G)\ge7$, or when $t\ge3$ and $\Delta(G)\ge14(t-1)$. For $t\ge35$, the bound $q_B(G)\le\Delta(G)+t-1$ holds regardless of $\Delta(G)$; for every $t\ge2$, it also holds when $\Delta(G)>428$. Finally, for every integer $k\ge1$, every $k$-degenerate $K_{2,t}$-free graph satisfies $q_B(G)\le\Delta(G)+(k-1)\min\{t-1,\Delta(G)\}$, with equality for $K_{k,t-1}$ when $k\ge2$ and $t-1\ge k$.

We prove the Bárány–Kalai–Tverberg conjecture extending the affine version of Tverberg's theorem to simplicial balls and polytopes other than the simplex: For any affine map $\phi : P\to \mathbb R^d$ from a convex polytope $P$ of dimension $N=(d+1)(r-1)$ with $r\geq 2$, there exist $r$ pairwise disjoint faces $F_1,\ldots,F_r\subset\partial P$ such that $\phi(F_1)\cap\dots\cap\phi(F_r)\neq\varnothing$. A similar statement holds for a simplicial ball $P$ with $\phi$ assumed affine on all of its faces.

For a positive integer $h$, a subset $A = \{a_1, \dots, a_k\}$ of an additive abelian group $G$ is called an $S_h$-set of size $k$ if all sums of $h$ distinct elements in $S$ are distinct. For fixed positive integers $h$ and $k$, let $v_h(k)$ denote the order of the smallest abelian group containing an $S_h$-set of size $k$. A lower bound for $v_2(k)$ is known. In this paper, we establish a lower bound for $v_3(k)$. Using our argument for $h=2$, we recover the known bound for $v_2(k)$.

We prove that the Bohnenblust–Hille constants for Walsh polynomials on the Hamming cube grow at most polynomially in the degree. More precisely, there is an absolute constant $K$ such that every $f :\{-1,1\}^{n} \to \mathbb{C}$ of degree at most $m$ satisfies $$ \left(\sum_{|S|\le m}|\widehat f(S)|^{2m/(m+1)}\right)^{(m+1)/(2m)} \le Km^{27}\|f\|_\infty. $$ The estimate is uniform in the dimension. The exponent $27$ is not optimized.

Every cluster variety admits an action of its cluster dilation group. We prove that, in the case of braid varieties for simple Lie groups, this action always extends to a regular action on each of the brick compactifications. We explore two applications of this result. First, we show that any closed Richardson variety admits a faithful action of a torus of rank the Kazhdan-Lusztig $d$-invariant, answering affirmatively a recent question of E. Gorsky–S. Kim–M. Sherman-Bennett. The same result holds for projected Richardson varieties. Second, we show that the braid variety is a torus if and only if for each of its brick compactifications, the polar dual of the moment polytope for this action realizes the corresponding subword complex. The braid words satisfying this property turn out to be precisely the double root free words of V. Pilaud and C. Stump. This provides a novel approach to the longstanding open question of the polytopality of spherical subword complexes asked by A. Knutson and E. Miller, and in particular gives infinite families of subword complexes admitting polytopal realizations in dimension higher than the rank of the corresponding Coxeter group. As a common consequence of these two applications, we classify all Bruhat intervals in finite crystallographic Coxeter groups which are isomorphic to face lattices of convex polytopes via certain double root free words.

Han, Jouhet and Zeng established $q$-analogues of the $\gamma$-expansion formulas for Eulerian polynomials of types $A$ and $B$. Combinatorial interpretations of the corresponding coefficients$a_{n,k}(q)$ and $b_{n,k}(q)$, however, remained open. In this paper, we provide combinatorial interpretations for thesecoefficients by using the model of increasing binary trees, thereby resolving a problem posed by Han, Jouhet and Zeng. Our combinatorial approach consists of three main steps: 1. construct a Carlitz-type insertion bijection for increasing binary trees and derive a new combinatorial interpretation ofCarlitz's $q$-Eulerian polynomials of type $A$ in terms of such trees; 2. introduce a generalized Foata–Strehl action on increasing binary trees to interpret the coefficients $a_{n,k}(q)$;3. derive a new combinatorial interpretation for the $q$-Eulerianpolynomials of type $B$ introduced by Chow and Gessel in terms of increasing binary trees of type $B$, and develop a generalizedFoata–Strehl action on these trees to interpret the coefficients $b_{n,k}(q)$. We further give combinatorial interpretations for the quotients ${a_{n,k}(q)/(-q;q)_{k-1}}$ and ${b_{n,k}(q)/(1+q)^k(-q;q^2)_k}$ in terms of André trees and a certain class of increasing binary trees of type $B$, respectively. As an application of the latter interpretation, we obtain a combinatorial interpretation for a $q$-analogue of the secant number and prove the positivity conjecture of Han, Jouhet and Zeng.

The study of $t$-intersecting families in symmetric groups received lots of attention in the last two decades. In this paper, we study two different kinds of stability results for $t$-intersecting families in symmetric groups. Let $\Sigma_n$ denote the symmetric group on $\{1,2,\ldots,n\}$. The $t$-diversity $\gamma_t(\mathcal{F})$ of $\mathcal{F}\subseteq\Sigma_n$ is defined as the minimum number of members of $\mathcal{F}$ whose deletion results in a family with transversal number $t$. The star $t$-diversity $\gamma_t^{\star}(\mathcal{F})$ is defined as the minimum number of members of $\mathcal{F}$ whose deletion results in a $t$-star. For $n$ relatively large with respect to $t$, we determine the best possible bounds for both $\gamma_t(\mathcal{F})$ and $\gamma_t^{\star}(\mathcal{F})$ over all $t$-intersecting families $\mathcal{F}\subseteq\Sigma_n$. The equality holding conditions are characterized. For $\gamma_t(\mathcal{F})$, the extremal case is generated by all $2t$-subsets of a $3t$-partial permutation or, when $t=2$, the family complements of the lines of the Fano plane. For $\gamma_t^{\star}(\mathcal{F})$, the extremal family is generated by all $(t+1)$-subsets of a $(t+2)$-partial permutation.

A multipartite tournament is an orientation of a complete multipartite graph. We prove that every $r$-regular $c$-partite tournament with common partite-set cardinality $\alpha$ is $4$-arc-pancyclic whenever $c\ge93$; that is, every arc belongs to a cycle of each length from $4$ to $c\alpha$. This confirms the conjecture of Zhou and Zhang for all sufficiently large $c$ and provides a multipartite analog of Alspach's arc-pancyclicity theorem. Moreover, we also give a construction to show that 4-arc-pancyclic is the best possible. Next, we prove that every arc belongs to at least $c\alpha-\alpha-1$ cycles of pairwise distinct lengths when $c\ge7$ and $\alpha\ge2$. For regular $3$-partite tournaments with common partite-set cardinality $\alpha\ge2$, we obtain the sharp lower bound $\alpha$, settling the remaining case of a conjecture of Xia, Cai, Guo, and Wang.

Fix one colour class in the checkerboard colouring of an $n\times n$ integer grid, and let $M_4(n,\varepsilon)$ be the largest subset having at most two points in every row, column, and diagonal of slopes $\pm1$. We prove the near-saturation bound $M_4(n,\varepsilon)\leq2n-4$ for $n\geq6$. The proof uses first and second moments of the four line families: a hypothetical set of size $2n-3$ produces row, column, and diagonal deficits whose exact moment identities contradict Cauchy–Schwarz. A finite argument handles $n=6$. The same identity extends to arbitrary deficit multisets. It gives $M_4(n,\varepsilon)\leq2n-d$ whenever $d\geq4$ is an integer and $n\geq3d-4$, and an entirely discrete asymptotic estimate \[ M_4(n,\varepsilon)\leq(\sqrt{21}-3)n+8. \] We also prove a general continuum-to-discrete theorem for the associated four-direction fractional packing problem. Applying it to the exact continuum dual certificate constructed in earlier work yields, for both colours, \[ L_{\mathrm{mono}}(n,\varepsilon)\leq\alpha n+O(1), \qquad \alpha\approx1.5768233968738, \] and hence the same upper bound for $M_4$ and for checkerboard no-three-in-line sets.

Given integers $c\geq 2$ and $s\geq 0$, let $\mathsf{M}_3(c,s)$ denote the least integer such that every set of at least $\mathsf{M}_3(c,s)$ points in the plane, no three on a line, colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. Further, let $\lambda_3(c)$ be the least integer such that $\mathsf{M}_3(c,\lambda_3(c))<\infty$. \citet{colorempty} proved that, for every $c\geq 2$, $$\left\lfloor\frac{c-1}{2}\right\rfloor \leq \lambda_3(c)\leq c-2.$$ Later, \citet{cravioto2019almost} improved the upper bound to $c-3$, for $c\geq 4$. In this paper, we refine their argument to obtain the following asymptotic improvement: $$\lambda_3(c) \leq c-\sqrt{c\log c}+o (\sqrt{c\log c} ),$$ for all sufficiently large $c$. We also show that every $c$-coloring of a sufficiently large Horton set contains a monochromatic triangle with at most $\lfloor \frac{c-1}{2} \rfloor$ interior points. This shows that the aforementioned lower bound on $\lambda_3(c)$ is sharp within the class of Horton sets. We conclude with a conjecture on the large-color asymptotics of $\lambda_3(c)$.

Let $G=\Cay(\mathbb{Z}_n,S)$ be a $3$-valent circulant digraph with connection set $S=\{0,s,t\}$, where $s,t\in\mathbb{Z}_n^*$ and $t\neq\pm s$. Determining the automorphism group of its endomorphism monoid reduces to determining the subgroup $U_S(\mathbb{Z}_n)\leq\mathbb{Z}_n^*$ that normalizes $\End(G)$. In this paper, we first establish necessary and sufficient conditions for a unit circulant digraph without $2$-cycles to admit an endomorphism whose image induces a directed cycle. Using this characterization, we explicitly determine $U_S(\mathbb{Z}_n)$ for the previously unresolved $0$-unit $3$-valent family.

We prove Jensen's inequality on each coordinatewise parity class of a jump $M$-convex function on $\mathbb{Z}^n$, without assuming strong base orderability or a finite effective domain. If a finite convex combination of domain points has its barycenter in the same parity class, then the barycenter belongs to the domain and satisfies Jensen's inequality. We also prove that every domain point admits an affine support on its entire parity class. The set of support vectors is characterized by at most $3^n-1$ local inequalities, which yield optimality certificates, attained duality, and an exact formula for linear growth and stability under linear perturbations. The same conclusions hold for distributions with finite first moment supported on domain points of a single parity class, provided their mean lies in that class. We characterize equality by contact sets and give a quantitative bound on the Jensen gap. The proof combines induction on dimension with the known closure under infimal convolution: convolution with an even-box indicator gives finite-domain supports, a quadratic kernel proves barycenter feasibility, and a fixed local kernel yields global supports. A two-dimensional example shows that total parity alone does not suffice.

Let $G(n,r,s)$ be a graph $(V,E)$ such that $V = \binom{[n]}{r}$ and $E = \{(u, v)| |u \cap v| = s\}. $In this paper we study the probability threshold for the exact stability of the independence number of $G(n, r, s)$ where $r > 2s+2$. We improve the previous result of Pyaderkin that implied asymptotic stability of the independence number.

We study the overhand shuffle with a fixed cut probability $p\in(0,1)$. In the packet-reversal convention, each gap is cut independently with probability $p$, and each resulting packet is reversed in place. We prove total-variation cutoff at \[ \frac{p^2}{2(1-p)\pi^2}\,n^2\log n. \] The lower bound uses an exact finite-deck cosine eigenfunction and a uniform conditional-variance estimate. For the upper bound, a coalescing coupling reduces a transposition discrepancy to a symmetric killed two-card chain. Its principal decay rate is $(1-p)\pi^2/(p^2n^2)+o(n^{-2})$. A boundary-flux identity bounds the sum of adjacent discrepancy probabilities without a factor equal to the deck size. The remaining ingredient is a two-sided $L^1$ inequality on permutations, with constant at most $\sqrt n\exp\{O(\sqrt{\log n\log\log(n+2)})\}$. Its proof decomposes a fixed block-table fiber into assignment words and independent smaller permutations, and closes a recursion using a multivariate hypergeometric inequality and an explicit routing comparison. We also prove relative-entropy cutoff with an $O_p(n^2)$ window about the intrinsic entropy transition time. Its leading coefficient lies between the total-variation coefficient and twice that value; a sharp entropy location is not obtained. The proof states the normalization and hypotheses of its established functional-inequality inputs. An appendix proves the intermediate static bounds and explains the change from one-scale averaging to recursive fibers.

Let $R_N(m)$ count unordered partitions of $m$ into reduced positive fractions whose numerators and denominators are at most $N$, excluding integer parts. Uniformly for $\rho$ in compact positive intervals, $\log R_N(\lfloor\rho N\rfloor)=\sqrt{2\rho}\,N^{3/2}-\kappa(\rho)N^{3/2}/\log N+o(N^{3/2}/\log N)$. The positive, continuously differentiable function $\kappa$ is an explicit sum of lattice-distance integrals, with $\kappa(1)\approx 0.00264713$. For a uniform partition of $n$, all but $o_{\mathbb{P}}(n/\log n)$ prime-denominator blocks in $(n/2,n]$ have total 2 or 3, according to whether $p/n$ lies below or above an explicit threshold near 0.7522. For fixed $N$, we give the Ehrhart numerator and determine how its poles control quasipolynomial coefficients. Its residue distribution is asymmetric for $N\ge 4$, but agrees with an independent model in every moment below order $\lceil N/2\rceil$. We identify the first discrepancy and prove a Gaussian limit. We also obtain joint denominator and size laws under two sampling rules.

This paper proves Conjecture 5.10 of Gajdzica, Visser, and Zakarczemny on restricted partitions of a rectangle. For every fixed positive integer k, the generating function for feasible multisets of bars of lengths at most k tiling a 2 x n rectangle has denominator dividing the product of (1 - x^j) for j = 1,...,k. Its coefficients are eventually quasipolynomial of degree k - 1 and period dividing the least common multiple of 1,...,k. The key observation is that appending a two-bar slab makes feasibility upward closed within each parity class of multiplicities. Dickson's lemma and finite inclusion-exclusion then give the precise denominator.

We introduce two new graph classes, the bicoloured-interval graphs and the interval-sandwich graphs, arising from the study of the robust line fitting problem in computer vision. In a bicoloured-interval graph, each vertex is assigned a real interval and one of two colours. Vertices of different colours are adjacent precisely when their intervals intersect, and vertices of the same colour precisely when the centre of one interval lies in the other. Discarding the colouring yields the interval-sandwich graphs, sandwiched between the $50\%$-tolerance graph and the intersection graph of a family of intervals. We prove structural results for both classes, determining which holes, antiholes, trees, and complete bipartite graphs each contains. Consequently, neither class is characterised by finitely many forbidden induced subgraphs. We place both classes strictly between the unit tolerance graphs and the co-comparability graphs in the tolerance hierarchy, separating them from the neighbouring classes. In particular, we construct an infinite family of proper tolerance graphs, each of which is a minimal forbidden induced subgraph for the bicoloured-interval graphs. Finally, we consider the recognition problems for both classes. We show that every graph in either class has a polynomial-size integer representation, and hence that both problems lie in~$\textsf{NP}$.

Let $\Gamma$ be the Cayley graph of Thompson's group $F$ with its standard generators. Belk and Brown constructed finite marked-forest subgraphs of limiting density $7/2$, and Guba showed that deleting certain low-degree vertices gives density greater than $3.5004$. We refine this approach in two directions. First, a deterministic interval-deletion rule followed by root-sensitive triple and pair deletions yields finite induced subgraphs with \[ \operatorname{dens}(\Gamma)>3.50074529. \] The interval rule is evaluated by a nine-state recurrence, while the simultaneous deletion conditions created by split and merge operations are computed exactly by a common-suffix first-passage argument. Second, we determine the joint distribution of the categories of a tree and its two children and reduce optimization over every fixed category-window retention rule to a weighted densest-subgraph problem. An explicit edge-allocation certificate shows that, for every fixed $a\ge0$, the optimal limiting density of a rule depending on the window $[-a,1]$ is exactly $7/2$. Thus arbitrary finite left context together with one right-hand category does not improve the Belk–Brown limit, whereas the root-sensitive whole-segment construction does. All constants are explicit elements of $\mathbb Q(\sqrt3,\sqrt{2\sqrt3-1})$.

We study a deformation of the central heat trace on $\mathrm U(N)$ obtained by deforming Schur polynomials to Jack polynomials, and prove that it admits an asymptotic expansion to arbitrary order. Its coefficients are governed by elliptic $b$-Hurwitz numbers, which are genus-one counterparts of the $b$-Hurwitz theory of Chapuy and Dołęga \cite{ChapuyDolega22}. We construct the associated elliptic $b$-Hurwitz theory by means of generalized coverings on a torus and identify it with the genus-one closure of the genus-zero simple $b$-Hurwitz theory. At $b=0$ the construction recovers ordinary elliptic Hurwitz theory, while at $b=1$ it gives an automorphism-weighted geometric interpretation of the connected and disconnected twisted elliptic Hurwitz numbers of Hahn–Markwig \cite{HahnMarkwig26}. Our results extend the topological expansion obtained in the classical case in \cite{LemMai25,LM2} and take the form of a coupling between chiral and antichiral elliptic $b$-Hurwitz generating functions.