Papers

We give an algorithm counting the permutations that avoid a fixed pattern of the following form: the direct sum of an increasing pattern and 231. The first members of the family are 1342 and 12453. For each member the algorithm uses polynomially many operations and stored integers, with degrees that grow linearly in the length of the pattern. It comes from a recurrence that reads a permutation from left to right and records the constraints that the letters read so far impose on those still unread. This recurrence has exponentially many states, but part of each state is protected: later steps carry it along unchanged and do not depend on it, and factoring the protected part out leaves a dynamic program of polynomial size. For 12453 a translation symmetry sharpens the bounds to degree seven for the operations and degree four for the storage. We also compute the number of 12453-avoiding permutations of every length up to 150. The previously published series, due to Biers-Ariel (2019), reached length 38. We also give a sampler of uniformly random avoiders. A floating-point implementation of it, proved to be within total variation distance $3.5\cdot10^{-5}$ of uniform for ideal random bits, draws the one million 12453-avoiding permutations of length 300 shown in a heatmap. The literal and kernel recurrences for 1342 and 12453 are verified in the Lean 4 proof assistant.

For every $\alpha\ge3$ and all sufficiently large $n$, we identify a single graph that simultaneously maximizes the number of independent sets of every size among all $n$-vertex $2$-connected graphs with independence number $\alpha$. This graph is unique up to isomorphism and is a balanced cycle-linking of the disjoint union of $\alpha$ cliques whose orders differ by at most one. More precisely, for each $3\le\beta\le\alpha$, the graphs maximizing the number of independent $\beta$-sets are exactly the cycle-linkings whose clique-size cyclic words are $\lfloor\beta/2\rfloor$-balanced. These results extend the corresponding extremal result for connected graphs to the $2$-connected setting. The proof combines generalized Turán-type clique counting and the edge-extremal theory of $2$-connected graphs with a coefficientwise balancing-switch argument. The switch also shows that a shortest imbalance of length $r$ first affects the independent-set count in degree $2r$.

In this paper, we construct two extremal positive definite even unimodular lattices of rank $88$ using a Hermitian tensor product over $\mathbb{Q}(\sqrt{-23})$, thereby extending the known existence range for such lattices from rank $80$ to rank $88$.

We show that every planar graph with no $t \times t$ grid minor has treewidth at most $4t +4$. This improves on the previously best known bound of $\frac{9}{2}t - \frac{11}{2}$, due to Gu and Tamaki (2012), and is within a factor $2$ of optimal. A key step in the proof is showing the following result, which might be of independent interest: Every $2$-connected plane graph $G$ with radius $d$ and faces of size at most $k$ has a tree-decomposition of width at most $\max\{3d+ k+5, 2d+2k+1\}$ such that the vertex set of every face of $G$ is contained in some bag.

We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside $[-2\sqrt2,2\sqrt2]$. This disproves the Bilu–Linial signing conjecture for general regular graphs. The graph $F$ is not Ramanujan, and the conjecture restricted to Ramanujan base graphs remains open.

We study packings of annuli of a common width, allowing each ring to nest inside the hole of a larger one. The objectives of maximizing contact area and cardinality diverge: area is superadditive in the radius, cardinality is not. Under superincreasing radii, every descending greedy maximizes every positive, strictly increasing, superadditive objective. More strongly, any choice among feasible containers yields the lexicographically maximal feasible set, for containers of arbitrary shape in every dimension. This placement irrelevance holds unconditionally for at most three rings and fails at four in disks and squares; twin instances exclude every universal rule based only on the observable state. Write $\rho=\max_i(\sum_{j>i}r_j)/r_i$. The additive model has threshold exactly $1$. For disks we prove the exact global threshold $\tau=\varphi$, with no failure at $\rho\le\varphi$, for every finite inventory, even with independent hole radii. The key geometric theorem states that, under golden tail bounds, an entire disk list fits a circular container if and only if its three largest disks fit; this supplies the uniform exchange of parents that the threshold proof needs. The Tribonacci constant $T\approx1.83929$ remains the exact floor of a rigid subfamily. A dimension-reduction lemma transfers spherical sharpness results to all dimensions $d\ge2$, and a separate argument proves the golden threshold for at most five rings in those dimensions. For square pans, a Cartesian confinement criterion gives twins and a family proving $\tau_{\square}\le Y\approx1.6845$; its optimality is open. For independent holes, the exact universal area guarantee under $\rho\le\kappa<1$ is $\min(1,\kappa^{-2}-1)$, with threshold $1/\sqrt2$. The repository has 122 Lean theorems. Euclidean geometry, forest assembly and continuity remain written proofs; numerical checks do not substitute for them.

We study stylic monoids from the viewpoint of higher-dimensional rewriting. A coherent presentation records not only the defining relations of a monoid, but also the relations among them. Using the $N$-tableau model, we construct a finite coherent presentation for every stylic monoid of finite rank. We start from the known finite convergent row presentation. By adjoining one generating confluence for each critical branching, Squier's coherence theorem yields a finite coherent extension. We then simplify the resulted coherent presentation by two successive homotopical reductions adapted to the row combinatorics of $N$-tableaux. Finally, coherent Tietze transformations and a further homotopical reduction transfer the construction from the auxiliary row generators to the standard letter generators. This gives an effectively computable finite homotopy basis for the standard letter presentation. The construction is illustrated in detail in rank $2$.

The number of spanning trees is a classical graph invariant and an important measure of network reliability, as it counts the minimal connected spanning substructures that can maintain communication in a network. Let $\mathcal{B}(n,d)$ be the set of connected bipartite graphs of order $n$ and diameter $d$. Motivated by reliability design problems for bipartite network models with fixed order and diameter, this paper determines all graphs with the maximum number of spanning trees in $\mathcal{B}(n,d)$. The result gives an extremal characterization of bipartite network topologies with the largest number of connected spanning backbones under prescribed order and diameter constraints, and provides a structural reference for the design of reliable bipartite networks.

We investigate scaling and local limits of random trees biased according to their number of descents. A descent in a rooted labeled tree $t$ is a parent-child pair such that the label of the parent is greater than the label of the child, and the total number of descents is denoted by $\mathrm{des}(t)$. For $n \geq 1$ and $q_n \geq 0$, we consider the probability measure on trees of size $n$ where each tree $t$ is chosen with a probability proportional to $q_n^{\mathrm{des}(t)}$. We study the resulting random tree $\mathcal{T}_n^{(q_n)}$ properly rescaled as $n \to \infty$, and focus on two regimes for the bias parameter $q_n$. When $q_n = q \in (0,1]$ is fixed, we prove that $\mathcal{T}_n^{(q)}$ converges in distribution to the Brownian Continuum Random Tree. When $q_n = a/n$ for some fixed $a > 0$, we prove that $\mathcal{T}_n^{(q_n)}$ converges in distribution to a random non-trivial dendron constructed from a Poisson-Dirichlet sequence. We complement these results with a description of the Benjamini-Schramm local limit of $\mathcal{T}_n^{(q_n)}$ in all regimes of parameters. Our proofs rely on analytic combinatorics to find the asymptotics of certain statistics of the tree, and on a probabilistic analysis of the structure of descent-biased random trees.

Let $G$ be a graph on $n$ vertices, and let $e_G(S,V(G)\setminus S)$ be the number of edges with exactly one endpoint in $S$. The Cheeger constant and the restricted Cheeger constant of $G$, where $k\ge1$ is real, are, respectively, \[ h(G)=\min_{\substack{\emptyset\ne S\subseteq V(G)\\|S|\le \frac{n}{2}}} \frac{e_G(S,V(G)\setminus S)}{|S|} \text{ and } h_k(G)=\min_{\substack{\emptyset\ne S\subseteq V(G) |S|\le\min\{k,\frac{n}{2}\}}} \frac{e_G(S,V(G)\setminus S)}{|S|}. \] The contraction clique number $\ccl(G)$ is the largest integer $r$ such that $G$ contains the complete graph $K_r$ as a minor. Krivelevich and Nenadov [Complete minors in graphs without sparse cuts, Int. Math. Res. Not. IMRN 12 (2021) 8996–9015] proved that, for every fixed $\eps>0$ and all sufficiently large $n$ and $d$, if $G$ is a graph on $n$ vertices with maximum degree at most $d$, then $h(G)\ge\eps d$ and $h_{\eps n}(G)\ge(\frac{1}{2}+\eps)d$ imply $\ccl(G)=\Omega_\eps(\sqrt{\frac{nd}{\log d}})$. They asked to determine if one can guarantee the same lower bound on $\ccl(G)$ without the additional condition on $h_{\eps n}(G)$. They showed that this is the case when $d$ is a constant. We answer this question affirmatively. For every $\eps>0$, there are constants $\beta=\beta(\eps)>0$ and $n_0=n_0(\eps)$ such that, whenever $d\ge 3$ is an integer, for every graph $G$ with $n\ge n_0$ vertices and maximum degree at most $d$, if $h(G)\ge\eps d$, then $\ccl(G)\ge\beta\sqrt{\frac{nd}{\log d}}$. The dependence of this lower bound on $n$ and $d$ is best possible up to a constant factor. As a corollary, a lower bound is derived for the contraction clique number of $d$-regular graphs for which the second largest eigenvalue is bounded away from $d$, compared to earlier $\frac{d}{2}$. The proof combines spectral properties of graphs with an analysis of lazy random walks.

For integers $k\ge 1$ and $n\ge k+2$, let $g_k(n)$ be the maximum number of edges in an $n$-vertex graph containing no cycle with a vertex incident with at least $k$ chords. Erdős conjectured that $g_k(n)=(k+1)(n-k-1)$ for $n\ge 2k+2$. Lewin found a counterexample. Bollobás later conjectured that there exists a function $n(k)$ such that $g_k(n)=(k+1)(n-k-1)$ for all $n\ge n(k)$. Jiang confirmed this by proving the formula for all $n\ge3k+3$ when $k\ge1$. In this paper, we determine $g_k(n)$ completely. For all $k\ge1$ and $n\ge k+2$, we prove $g_k(n)=\big\{\lfloor\frac{(k+1)n}{2}\rfloor,\max\{a(n-a)+\lfloor\frac{a(k+1-a)}{2}\rfloor : a\in\mathbb Z,\; \lfloor {(k+1)}/{2}\rfloor+1\le a\le k+1\}\big\}$. For $k\ge2$, we prove $g_k(n)=(k+1)(n-k-1)$ when $n\ge \lceil(5k+1)/2\rceil$, and this threshold is sharp. Our proof builds on the method developed by Ma and the second author in [Ma and Ning, 2020].

We prove a structural theorem for point sets in $\mathbb R^2$ which determine few pinned angles. More precisely, we prove the existence of an absolute constant $c>0$ such that if $n$ is sufficiently large and $P$ is a set of $n$ points then there exists a point $q \in P$ which determines at least $n^{1+c}$ distinct angles to other pairs of points of $P$, provided that $P$ is not of one of the following exceptional forms: all but at most one of the points of $P$ lie on a line; all but two points of $P$ lie on a line, and the two exceptional points are symmetric with respect to the line; all the points of $P$ lie on a circle; all but one of the points of $P$ lie on a circle, and the exceptional point is the centre of the circle. As a consequence, we answer a question of Corrádi, Erdős and Hajnal by showing that if $n$ is sufficiently large and $P \subseteq \mathbb R^2$ has cardinality $n$ and is not contained on a single line, then $P$ determines at least $n-2$ angles. Moreover, we prove that the unique point set attaining this minimum is the regular $n$-gon.

We prove that the bound \[ \max \{ |16A|,|16f(A)| \} \gg_m |A|^{\frac{3}{2}+\frac{1}{162}} \] holds for any polynomial $f$ with degree $m \geq 2$ and any finite $A \subset \mathbb R$. This shows that the classical Jarník obstruction to growth beyond exponent $3/2$, which occurs for general strictly convex functions, cannot occur for polynomial functions.

Quasiparabolic sets extend parabolic coset spaces while retaining a length filtration and natural Hecke algebra deformations. Gelfand models built from induced linear characters ask when such spaces can account for every irreducible representation exactly once. We classify, up to equality of the individual induced characters, all quasiparabolic Gelfand models for finite irreducible Coxeter groups with inducing characters restricted from their ambient parabolic subgroups, including the additional models of type \(D_{4r+2}\) and \(B_3\). We derive the associated finite Gelfand-pair and commutant consequences, construct canonical Hecke structures for the additional classical models.

Let $H$ be a fixed $d$-regular graph with $d\ge2$, and let $t(H,\cdot)$ denote its homomorphism density. We study the upper-tail event $t(H,G(n,p))\ge r^{|E(H)|}$ for fixed $0<p<r<1$ in a dense Erdős–Rényi random graph $G(n,p)$. Near the Lubetzky–Zhao replica-symmetric phase boundary and away from the exceptional target density $(d-1)/d$, we prove that the optimizer of the Chatterjee–Varadhan variational problem on the symmetry-breaking side is bipodal (two-block) and unique up to relabeling. Its block parameters depend analytically on $(p,r)$. To treat the exceptional boundary point, where the nonexceptional theory degenerates, we construct an analytic curve approaching that point from the symmetry-breaking side along which the unique optimizers are nonconstant rank-one bipodal graphons. In both settings, we derive asymptotic expansions of the edge-density deficit and the rate function that governs the exponential decay of the upper-tail probability. Moreover, the conditioned random graph converges in cut distance to the corresponding bipodal optimizer as $n\to\infty$. As $(p,r)$ approaches the phase boundary from the symmetry-breaking side, the optimizers converge to their constant limits through two distinct mechanisms. For each fixed nonexceptional target density, one block shrinks to zero measure, giving convergence in $L^1$ but not in $L^\infty$. Along the exceptional curve, both blocks remain macroscopic: their sizes tend to $1/2$ and all three block densities tend to $(d-1)/d$, yielding convergence in $L^\infty$.

Beck and Pixton expressed the Ehrhart polynomial of the Birkhoff polytope as a weighted sum of constant terms of several multivariate rational functions. Xin and Zhang studied a class of constant terms $h_n(t)$, which can be regarded as a variation of the Morris constant term. They proved that $h_n(t)$ is a polynomial of degree $(n-1)^2$ and obtained many nice properties involving the Morris constant term identity. Let $h_n^*(y)=(1-y)^{(n-1)^2+1}\sum_{t\geq0}h_n(t)y^t$. For fixed $n\geq 3$, we obtain the following results for $h_n^*(y)$: (i): $h_n^*(y)$ is a polynomial with positive integer coefficients. (ii): $h_n^*(y)$ is real-rooted. In particular, all its roots are non-positive real numbers. (iii): $h_n^*(y)$ is Gamma-positive. Furthermore, $h_n^*(y)$ is palindromic, unimodal, and ultra log-concave. This confirms Xin and Zhang's conjecture regarding $h_n^*(y)$. In order to resolve this conjecture, we also developed an operator on the space of symmetric polynomials that preserves real stability. As a byproduct, we prove that every root of a Gamma polynomial associated with $h_n^*(y)$ is a negative real number.

Motivated by the Morse–Seelinger conjecture on type C $k$-Schur functions, we develop a permutation model for type C strong marked tableaux. Using type C transpositions, we give an explicit correspondence with the symmetric-core model that preserves the marking data. We also describe the induced affine Weyl group action on bounded partitions.

The palindromic length $PL(u)$ of a nonempty finite word $u$ is the least number of nonempty palindromes whose concatenation is $u$. For an infinite word $w$, let $P_w(n)$ be the number of nonempty palindromic prefixes of $w[1,n]$, and let $T_w(n)$ consist of those prefixes $w[1,j]$, $1\leq j\leq n$, whose palindromic length equals the maximum attained among the nonempty prefixes of $w[1,j]$. We prove the finite inequality $|T_w(n)|\geq P_w(n)$ for every $n\geq1$. In particular, if $w$ has infinitely many palindromic prefixes, then \[ \liminf_{n\to\infty}\frac{|T_w(n)|}{P_w(n)}\geq1. \] The coefficient $1$ is optimal, already for a nonconstant periodic word. The proof uses chains of occurrences connected by palindromic factors, together with trimming and reflection arguments that preserve lower bounds on palindromic length.

We prove the conjecture of Xu, Li, Hua, and Pan that the resistance diameter does not increase under the line-graph operation. For every finite connected simple graph $G$ with at least one edge, we establish $D_r(L(G))\le D_r(G)$, with equality if and only if $G$ is a cycle or $K_4$. The proof combines an exact electrical representation of $L(G)$ by stars with a sharp budget inequality for the branch core. This inequality controls the combined error terms arising from the comparison of degree-two paths and is central to both the diameter bound and the equality analysis.

In this paper, we derive thresholds and fluctuations for arithmetic progressions with prescribed color patterns in sparse random colorings of $[n]:=\{1, 2, \ldots, n\}$, where each element of $[n]$ is colored independently according to a given probability vector. For any admissible ordered palette of colors, we determine the full multi-parameter threshold region for the appearance of a colorful arithmetic progression. The threshold is governed by two competing mechanisms: a global first-moment condition and a local color-availability condition, resulting in a polyhedral satisfiability region, with a piecewise-polyhedral threshold surface. In the satisfiability region we establish asymptotic normality for the number of colorful arithmetic progressions of a given length, with an explicit rate of convergence in Wasserstein distance. On the threshold surface, we identify three distinct asymptotic regimes: Poisson, compound Poisson with mixed Poisson jumps, and compound Poisson with uniform jumps, after an appropriate normalization. These results provide a complete description of the threshold and fluctuation behavior of general colored arithmetic progressions under sparse random colorings, in a unified framework that interpolates between classical uncolored/monochromatic progressions in binomial random subsets and multicolored, including rainbow, arithmetic progressions.

The arithmetic graph $B_n$ joins distinct $a,b\in\N$ when $\max(a,b)/\gcd(a,b)\le n$. We prove $\chi(B_{205})=206$, disproving the conjecture that $\chi(B_n)=n$ for every $n$, equivalently the Rainbow Cascades Conjecture. The proof reduces an arbitrary tiling by the arithmetic exponent tile to a periodic tiling, then to two families of finite quotients, which are excluded using exact computations. We also construct a $208$-coloring using $\Z_{104}\times\Z_2$ and prove $212\le\chi(B_{211})\le213$. The lower bound at $211$ follows from prime-cardinality tiling rigidity and the published nonexistence of a cyclic logarithm of length $211$; we give a direct proof of the required rigidity statement. Finally, we record the equivalence with the List Cascade Coloring Conjecture and the conjecture on ironic decorations, and deduce finite graph counterexamples to both. The least $n$ with $\chi(B_n)>n$ is either $195$ or $205$; determining which remains open.

The Komlós conjecture is a classic problem in discrepancy theory; it asks whether an absolute constant $K$ exists such that given any $n$ vectors $a_1,\ldots,a_n$ inside the $m$-dimensional Euclidean ball, regardless of how large $m,n$ are, there is always a selection of signs $\varepsilon_1,\ldots,\varepsilon_n$ guaranteeing $$\|\varepsilon_1a_1+\ldots+\varepsilon_na_n\|_\infty \leq K.$$ We show that if the $\varepsilon_i$'s are allowed to take not just the values of $\pm 1$ but any unit modulus complex number, which we refer to as complex discrepancy, then the above inequality holds for a finite, explicit constant $K_{\mathbb{C}}$. Here, the $\ell^\infty$ norm of the resulting vector in $\mathbb{C}^m$ is the largest modulus of its entries, and thus the complex discrepancy of real vectors is equivalent to their rank-$2$ vector discrepancy. This quantity provides an upper bound (modulo uniform constant prefactor) on Gaussian discrepancy – a discrepancy measure introduced by Chewi, Gerber, Rigollet and Turner. Thus, we also resolve the Komlós conjecture for Gaussian discrepancy. Our paper builds upon the recent work of Bansal and Jiang on the Beck-Fiala and Komlós conjectures, which we approach from the formalism of Burkholder and the Bellman function method from probability and harmonic analysis. Our work was in part motivated by the realization that the complex discrepancy of the columns of any unitary matrix is equal to 1, a fact that follows from a straightforward calculation based on Idel and Wolf's generalization of the Sinkhorn normal form for unitary matrices.

We determine the exact time exponent of space-optimal reversible pebbling on chains as $1.331742379256310\ldots$. The growth rate of space-optimal reach exists as a limit and admits a variational formula. The same exponent governs complete computations at minimal space, uniformly in the chain length.

We prove that, for every integer $t\geq 1$, the unit two-sphere admits a spherical $t$-design consisting of exactly $54t^2$ points. More generally, such a design exists with exactly $6q^2$ points for every integer $q\geq 3t$. The proof builds on the topological degree method of Bondarenko, Radchenko and Viazovska, using an explicit equal-area partition of the sphere based on the map of Roşca and Plonka. By choosing the cell centers to minimize the average squared geodesic distance and deriving sharper sampling estimates, we obtain the stated quadratic bound on the size of spherical $t$-designs on $\Sph$.

The Borel distinguishing number $D_B(\mathcal{G})$ of a Borel graph $\mathcal{G}$, recently introduced by Bilge and Kaya, is the minimum number of colors required to break the symmetry of $\mathcal{G}$ in a Borel way. In this paper, we investigate the Borel distinguishing number of Schreier graphs induced by the free part of the shift action $\Gamma \curvearrowright n^\Gamma$. We prove that $D_B(\mathcal{G})\le n+1$ for $\Gamma=\mathbb{Z}^d$ equipped with the standard generators. Moreover, we show that $D_B(\mathcal{G})\ge n+1$ if $ \Gamma$ is amenable and $ \{\gamma \in \mathrm{Aut}(\mathrm{Cay}(\Gamma,S)) \mid \gamma(e) = e \}$ is non-trivial. We also show that $D_B(\mathcal{G})$ is finite if $\Gamma$ is finitely generated, and give some applications of our results. These results answer some questions raised by Bilge and Kaya.

Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$–sparse binary vectors in $\{0,1\}^n$. This is a random analogue of the online Beck–Fiala problem. We show that uniformly for $2\le d\le n/2$ and $T = \Theta(n)$, the optimal online prefix discrepancy $\max\limits_{t\leq T}\left\|\sum_{i=1}^t\sigma_i X_i\right\|_\infty$ is of order \[ \Theta\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le(\log\log n)^2$, the optimal discrepancy is $\Theta(\log\log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $\Theta(\sqrt d)$, matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck–Fiala model.

Consider a simple undirected graph $G$ on $N$ vertices, with each vertex holding an opinion from one of two options. Starting from the initial opinions on day 1, we run majority dynamics: on each subsequent day, all vertices simultaneously adopt the majority opinion among their neighbors, retaining their current opinion in case of a tie. A well-studied conjecture of Benjamini, Chan, O'Donnell, Tamuz, and Tan states that if $G$ is drawn from the random binomial model $\mathbb{G}(N,p)$, and if the starting opinions are chosen uniformly at random, then as long as $pN \to \infty$ the network will converge to 99% consensus with high probability. We confirm this conjecture as long as $pN \ge N^{\varepsilon}$ for any fixed $\varepsilon > 0$, showing that full unanimity is reached with high probability in $O(1/\varepsilon)$ days. This result improves on a line of results by Fountoulakis, Kang, and Makai, who achieve $\varepsilon = 1/2$; Chakraborti, Kim, Lee, and Tran, who achieve $\varepsilon = 2/5$; and Jaffe, who achieves $\varepsilon = 1/3$. The proof technique involves iteratively revealing the "opinion histories" for each vertex through time, keeping track of the degrees between every vertex and each of $2^k$ opinion history classes on day $k$. Our analysis of this process requires intricate estimates for degree-constrained random graph models using graph enumeration tools from the work of McKay and Wormald as well as Canfield, Greenhill, and McKay, and their extensions by Liebenau and Wormald. In doing so, we connect the discrete dynamics to a deterministic idealized process, whose leading-order behavior is described by conditional Gaussian probabilities and expectations.

In this paper, we classify the Conway symbols of the Euclidean symmetry groups of frieze patterns of Dynkin types $A_n$, $B_n$, $C_n$, $D_n$, $F_4$ and $G_2$. First, we show that the Conway symbol of a Conway–Coxeter frieze is determined by the bilateral and the central symmetry of the underlying triangulation. Secondly, we show that a frieze pattern of non-simply-laced type has the symbol ${*}\infty\infty$ or $\infty\infty$ according as its first interior row is palindromic or not, with the single exception of type $C_3$, which realises four symbols. Thirdly, we show that the same dichotomy holds for type $D_n$ with $n \ge 5$, the symbol being read off the tagged triangulation of the once-punctured polygon attached to the frieze together with the value on its puncture edges, and that type $D_4$ realises five symbols.

Long-range expansion is a combinatorial graph property introduced to construct metric spaces with strong quantitative obstructions to low-distortion embeddings. Such extremal constructions are motivated by fundamental questions in metric geometry and nonlinear functional analysis. However, the only known constructions of long-range expander sequences are random regular graphs; the problem of constructing explicit sequences, especially with logarithmic girth, remains open. We resolve this question in strong form by proving that the Ramanujan condition implies long-range expansion. In particular, classical Ramanujan constructions (such as LPS graphs) give explicit long-range expander sequences with logarithmic girth. We also clarify that long-range expansion implies spectral expansion, and both implications are strict. While long-range expansion, the Ramanujan property, and spectral expansion are strictly separated, it is a priori not clear how robust these gaps are. We next compare them from a dynamics perspective: how do the different notions of expansion affect the mixing rate of random walks? Our second main result is that, from a dynamics perspective, LRE and the Ramanujan property are equivalent. We show that the random walk on any LRE sequence has the same cutoff location and Gaussian limit profile as on a Ramanujan graph. This incidentally offers intermediate progress between cutoff for Ramanujan graphs—proven by Lubetzky and Peres—and the long-standing conjecture of cutoff for transitive spectral expanders.

We prove that the integer-threshold decision problem for weak partition connectivity in hedgegraphs is NP-complete, answering an open question about its computational complexity. Hardness holds even for connected unweighted hedgegraphs in which every hedge consists of exactly two nonempty, vertex-disjoint hyperedges whose union is the entire vertex set. On the same class of instances, hedge connectivity has a simple exact formula. Using a binary matrix representation, we express fractional weak partition connectivity as $m-\rho(A)$, where $\rho(A)$ maximizes the ratio of the number of selected rows to one less than the number of distinct projected columns. This formula yields both the hardness reduction and deterministic algorithms: exact computation when some reference column gives row supports satisfying a linear intersection condition, including the case of minimum row-support number $s(A)\le2$, and a partition-output polynomial-time approximation scheme (PTAS) for both the integer and fractional objectives on all full-support split systems. Unless $\mathrm{P}=\mathrm{NP}$, neither objective admits a fully polynomial-time approximation scheme (FPTAS) on this class.