Papers

The discrete-time treatment number of a graph $H$, denoted by $\tau(H)$, was introduced in arXiv:2408.0531(3) and arises from a deterministic process in which each vertex is assigned a color at each time-step. The pathwidth upper bound $\tau(H)\leq \lceil\frac{1+pw(H)}{2}\rceil$, is shown in arXiv:2408.0531(3), where $pw(H)$ denotes the pathwidth of graph $H$. Equality holds when $H$ is the complete binary tree of depth $d$ (denoted by $BT(d)$) and $1 \le d \le 6$. In this paper, we characterize the sizes of all subsets of vertices of $BT(d)$ whose boundary has $3$ or fewer vertices and use this result to prove that $\tau(BT(d))= 3$ for $8\leq d\leq 10$; in these cases, equality also holds in the pathwidth upper bound. By the hereditary property of the treatment number, all larger complete binary trees have treatment number at least $3$. In contrast, we provide an explicit construction to show that $\tau(BT(7))=2$, while the pathwidth upper bound only shows $\tau(BT(7))\le 3.$ We construct an infinite family of graphs, each with a cut-vertex, whose treatment number depends on the number of components when the cut-vertex is removed. We use a combination of pathwidth and vertex cuts to prove another upper bound on the treatment number and use this to construct an infinite family of graphs whose boundary size is limited, but whose treatment number is unlimited.

Let $F$ be a family of $n$ unit disks in $\mathbb{R}^2$ with $n$ being odd. We use $\mbox{OA}(F)$ to denote the area of the set of points that is covered by an odd number of disks. The purpose of this note is to disprove the conjecture $\mbox{OA}(F) \geq \pi$ which was suggested in the literature and to present some examples.

We show that every probability-measure-preserving equivalence relation generated by a locally-finite Borel graph with planar connected components is sofic in the sense of Elek–Lippner. In particular, every unimodular random planar graph is sofic. This removes the additional assumptions in the works of Angel–Hutchcroft–Nachmias–Ray and Timár on the soficity of unimodular random planar maps and graphs. To prove this, we investigate Borel simplicial complexes with planar components and approximate them by treeable covering spaces. To construct these coverings, we use a canonical family of tracks on planar simplicial complexes introduced by Dunwoody.

The 1970 spectral extension of Mantel's theorem, proved by Nosal, states that every graph with $m$ edges and spectral radius $\rho_1>\sqrt{m}$ contains at least one triangle. Its quantitative refinement by Ning and Zhai later established that any graph $G$ with $m$ edges and spectral radius $\rho_1\geq\sqrt{m}$ contains at least $\lfloor\frac{\sqrt{m}-1}{2}\rfloor$ triangles, unless $G$ is a complete bipartite graph. In this paper, we further investigate the minimum number of triangles guaranteed under the strengthened spectral condition $\rho_1\geq\sqrt{m}+c$, where $c$ is a positive constant. We prove that for any constant $c\in (0,\frac{1}{2}]$ and all sufficiently large $m$, if $s=s(m)$ is a real-valued function satisfying $\lim_{m\to\infty} \frac{s}{m}=c$, then every $m$-edge graph $G$ with spectral radius $\rho_1$ satisfying $\rho_1^2\geq m-1+\frac{2s}{\rho_1-1}$ contains at least $s$ triangles. Moreover, we characterize the extremal graph achieving the minimal number of triangles. In particular, when $s=\frac{m-1}2$, our result settles a conjecture proposed by Li, Feng, and Peng.

In this paper, we introduce and investigate the $\textbf{k}$-neighborhood ideal of a graph, a natural generalization of the closed neighborhood ideal. Let $G$ be a simple graph on the vertex set $[n]$, and let $S=K[x_1,\dots,x_n]$ be the polynomial ring over a field $K$. For a vector $\textbf{k}=(k_1,\ldots,k_n)\in \mathbb{N}^n$ satisfying $1\leq k_i\leq \textrm{deg}_G(i)+1$ for all $i$, the $\textbf{k}$-neighborhood ideal of $G$ is defined as the squarefree monomial ideal $$\textrm{NI}_{\textbf{k}}(G)=\sum_{i=1}^n\, (\textbf{x}_W:\, W\subseteq N_G[i],\, |W|=k_i)$$ of $S$, where $\textbf{x}_W=\prod_{i\in W} x_i$. We study homological invariants and properties of $\textrm{NI}_{\textbf{k}}(G)$ focusing on its Castelnuovo-Mumford regularity, projective dimension and Cohen-Macaulayness. Special attention is devoted to the case where the vector ${\textbf{k}}$ is the degree-vector of the graph, i.e., $k_i=\textrm{deg}_G(i)$ for all vertices $i$, and to the case where $\textrm{NI}_{\textbf{k}}(G)$ coincides with the edge ideal of a graph. In these settings, we provide combinatorial characterizations and bounds for the regularity and projective dimension of $\textrm{NI}_{\textbf{k}}(G)$ for several classes of graphs, and further investigate the Cohen-Macaulay property of these ideals.

Let ${\bf x} = (a_i)_{i \geq 0}$ be an infinite word over a finite alphabet $\Sigma$. Let $\rho (n)$ be the factor complexity function for $\bf x$ and ${\rm Pal}(n)$ be the palindrome complexity function for $\bf x$. We give a new relationship between these two quantities; namely, if $\bf x$ is not ultimately periodic, then $$ \lim_{n \rightarrow \infty} {{ {\rm Pal} (n) \log ({\rm Pal} (n) + 1)} \over {\rho (n)}} = 0. $$ Furthermore, we prove that the numerator in this result is essentially optimal.

In this paper, we study the nested Hilbert scheme $(\mathbb{A}^2)^{[n,n+1]}=\mathrm{Hilb}^{n,n+1}(\mathbb{A}^2)$ from a combination of deformation theory, torus actions, and Young diagram combinatorics. We first recall the scheme theory and functor basics needed to define Hilbert schemes. We then use a classic result on first-order deformations to identify $T_I(\mathbb{A}^2)^{[n]}\cong \mathrm{Hom}_{\mathbb{C}[x,y]}(I,\mathbb{C}[x,y]/I)$. For a nested pair $I\subset J$, with $\dim_{\mathbb{C}}\mathbb{C}[x,y]/I=n+1$ and $\dim_{\mathbb{C}}\mathbb{C}[x,y]/J=n$, the tangent space becomes a compatibility kernel $T_{(I,J)}(\mathbb{A}^2)^{[n,n+1]}\cong \ker(\mathrm{Hom}(I,R/I)\oplus \mathrm{Hom}(J,R/J)\to \mathrm{Hom}(I,R/J))$. The torus-fixed points are indexed by a partition $\lambda\vdash n+1$ together with a removable corner $c$ of its Young diagram. This corner is not only combinatorial, but also the monomial form of a one dimensional socle direction in $R/I_\lambda$. The blow-up map to $(\mathbb{A}^2)^{[n]}\times \mathbb{A}^2$ has fibres given by projective spaces of one-dimensional quotients of $J/\mathfrak m_pJ$, whose torus-fixed points are addable boxes of the smaller diagram. These two local fibres explain how the universal family, the blow-up geometry, and Young diagram combinatorics come together in the study of the local geometry of the nested Hilbert scheme of points. Finally, we derive the tangent weight formula at a fixed point $(I_\lambda,I_{\lambda\setminus c})$ in the torus convention used in the paper. Using the standard arrow basis, we show in the proof how the arm-leg weights are modified by the compatibility kernel through a shortening rule determined by $c$. A Macaulay2 verification computes the compatibility kernel from monomial syzygies and checks the weight formula for all partitions of size at most $16$.

We study the second largest spectral gap from $1$ of the normalized Laplacian of a graph, a quantity that appears in the literature in connection with random walks, expander graphs, and Ramanujan graphs. We relate it to the classical Cheeger and dual Cheeger constants, and we introduce a new Cheeger-type constant admitting a probabilistic interpretation in terms of two-step random walks. For this constant, we establish sharp inequalities analogous to the classical Cheeger inequalities.

Building upon the algebraic framework of trace monoids introduced by Giscard and Rochet, we establish a new determinant formula for the Ihara zeta functions of certain digraphs. We present our results through two main theorems. First, at the algebraic level, we show a general determinant formula expressed by a Cayley determinant over the hike monoid ring, which provides a unifying perspective on several known determinant expressions. Second, by evaluating the lengths of hikes through a natural ring homomorphism, we prove that the reciprocal of the Ihara zeta function can be explicitly expressed as a determinant whose dimension is equal to the number of simple cycles of the line digraph without backtrack.

In 2011, Csikvári [Electron. J. Combin. 18 (2011), $\#$P182] proved that among all graphs with a prescribed number of edges, the largest matching root is attained by a threshold graph, and conjectured that the extremal graph should be `as star-like as possible.' In this paper, we give a complete and affirmative answer to this problem and extend it to the setting of uniform hypergraphs. We prove that for every $k$-graph $\mathcal{H}$ with $m$ edges, its largest matching root satisfies $$\lambda(\mathcal{H})\le m^{1/k},$$ with equality if and only if $\mathcal{H}$ is intersecting. For $k=2$, after deleting all isolated vertices, the resulting graph must be the star $K_{1,m}$ or a triangle, thereby confirming Csikvári's conjecture. Moreover, if the matching number $\nu(\mathcal{H})\ge 2$, then \[ \lambda(\mathcal{H})\le \left(\frac{m+\sqrt{m^2-4(\nu(\mathcal{H})-1)}}{2}\right)^{1/k}, \] with equality if and only if $\nu(\mathcal{H})=2$ and $\mathcal{H}$ has exactly one $2$-matching.

Hypercube graphs are fundamental model spaces of positive curvature in discrete comparison geometry. Let $G$ be a finite, connected, simple, unweighted graph with Bakry–Émery curvature bounded below by $K$. We call $G$ Lichnerowicz-sharp if its first non-zero non-normalized Laplacian eigenvalue $\lambda_1=K$. We prove that all regular Lichnerowicz-sharp graphs are hypercube bundles with constant Bakry-Émery curvature $2$. A hypercube bundle is a graph bundle whose fiber graphs are hypercubes. As applications, we show that any $d$-regular Lichnerowicz-sharp graph with the multiplicity $m_K(G)$ of $\lambda_1=K$ at least $d/2$ can split off a hypercube of certain dimension. Moreover, we characterize all $d$-regular Lichnerowicz-sharp graphs with $m_{K}(G)\geq d-3$. Interestingly, our result leads to the following spectral rigidity theorem of hypercubes. For a graph $G$ with maximum degree $\Delta$, if the multiplicity $m_K(G)\geq \Delta-1$, then $G$ is a $\Delta$-dimensional hypercube. This improves, in the unweighted setting, the multiplicity condition $m_K(G)\geq \Delta$ appearing in the hypercube rigidity theorem of Liu, Münch, and Peyerimhoff. This improvement is optimal.

We investigate the joint distribution of the trivariate statistics (des, maj, inv) on classical permutations, Andre permutations of the first and second kinds, and Simsun permutations. By decomposing permutations according to the position of the smallest element, we obtain explicit recurrence relations for the generating functions of these statistics. In the classical permutation setting, our recurrence relation yields the generating function for the trivariate statistics (des, maj, inv) due to Gessel, which is typically proved using MacMahon's technique.

For $m \in \mathbb{N}$, let $q_m := \frac{\log(2m+1)}{2\log(m+1)}$. The max-convolution inequality \begin{align*} \sum_{k=0}^{2m}\left(\max_{i+j=k} x_i y_j \right)^{q_m} &\ge \left(\sum_{i=0}^{m} x_i\right)^{q_m} \left(\sum_{j=0}^{m} y_j\right)^{q_m} \end{align*}for arbitrary sequences $x_0 \ge x_1 \ge ... \ge x_m \ge 0, y_0 \ge y_1 \ge ... \ge y_m \ge 0$ implies an affirmative answer to a question of Bourgain, Dilworth, Ford, Konyagin, and Kutzarova \cite{BDFKK} on the sizes of sumsets in product sets. This inequality was proven for $m = 2$ by Becker, Ivanisvili, Krachun, and Madrid \cite{BIKM} by reducing the general case to the geometric block case via a max-tie analysis. We prove the geometric block case $x = (1, t, ..., t^{r}, 0, ..., 0)$ and $y = (1, t, ..., t^s, 0, ..., 0)$, $t \in [0, 1]$, for all $m \in \mathbb{N}$ via a comparison of Stolarsky means. Some perturbations are also verified. Finally, we prove the above inequality when one sequence has only two non-zero terms.

Green asked the following question concerning structures in sumsets: Suppose that $\mathbb{F}_2^n$ is partitioned into sets $A_1, \dots, A_K$. Does $A_i+A_i$ contain a coset of codimension $O_K(1)$ for some $i$? An answer is not known even in the case of $K = 3$. We resolve this question in the affirmative in two special cases: (1) when $A_1, A_2$ are Hamming balls of radius $r < n/2 - 7$ relative to different bases, and (2) when $A_1$ is a Hamming ball of sufficiently small constant density.

We introduce two infinite families of 3-regular planar graphs. Both families are conceptual adversaries to the Pohl-Warnsdorf algorithm for finding Hamiltonians. We provide a closed form calculation of the number of Hamiltonians.

Order types are an equivalence relation between point configurations that capture their combinatorial and convexity properties. Let $P$ be a $\kappa$-colored sequence of $n \ge d+1$ points in general position in $\mathbb{R}^d$. Let $\rho$ be a $\kappa$-colored order type on $k \le d+1$ points that has positive density on $P$; that is, for some constant $\delta >0$, there are $\delta \cdot \binom{n}{k}$ $k$-point subsequences of $P$ that have the same order type as $\rho$ and the same color pattern. In this paper we show that there exists a constant $c >0$ (depending only on $d, \delta$, $k$ and $\kappa$) and disjoint subsets $X_1,\dots,X_k$ of $P$, each with at least $c \cdot n$ points, such that for every choice of $k$ points $x_i \in X_i$, $(x_1,\dots,x_k)$ has the same order type and color pattern as $\rho$.

In this note, we introduce the partial order decomposition number of a digraph $D$, denoted $pod(D)$, defined as the minimum integer $k$ such that $A(D)=A(P_1)\cup\cdots\cup A(P_k)$, where $P_1,\ldots,P_k$ are partial orders on $V(D)$. We prove that $\dic(D)\le \diomega(D)^{pod(D)}$ for every digraph $D$. In particular, every class of digraphs with bounded $pod$ is polynomially $\dic$-bounded. We apply this to tournaments, showing that if $\mathcal C$ is a class of tournaments with bounded dichromatic number, then the closure of $\mathcal C$ under substitution is polynomially $\dic$-bounded, thereby making progress on a question of Aubian, Charbit, Lopes, and the first author. As further applications of $pod$, we prove that poset tournaments of bounded dimension are $\dic$-bounded, derive polynomial lower bounds on the directed clique number of an explicit family of tournaments, thereby answering a conjecture of Gutowski and Rams, and show that tournaments with bounded $pod$ have bounded domination number.

Springer fibers are subvarieties of the flag variety parameterized by nilpotent matrices. They are central objects of study in geometry representation theory. This paper focuses on two-row Springer fibers, those corresponding to nilpotent matrices with two Jordan blocks. Irreducible components of two-row Springer fibers are in bijection with two-row standard Young tableaux and also with noncrossing matchings. Inspired by the combinatorial commutative algebra of matrix Schubert varieties, we define a polynomial ideal for each noncrossing matching and prove that these ideals define the corresponding components of the Springer fiber. Our proofs leverage geometric descriptions of Springer fibers established by Fung, Stroppel–Webster, Fresse, and Goldwasser–Nadeem–Sun–Tymoczko. Using these ideals to compute examples, we give two conjectural formulas for the cohomology class of each component of a two-row Springer fiber. We apply commutative algebra techniques to prove these conjectures for a specific family of two-row tableaux.

We compare two cluster algebras related to a positive element $\mathtt{b}$ in the braid group of finite $ADE$ type. One is the localized bosonic extension ${\widetilde{\mathbb{A}}}_\mathbb{C}(\mathtt{b})$ equipped with an initial seed arising from an admissible chain $\mathfrak{C}$ of $i$-boxes, which is deeply connected to monoidal categorification. The other is the coordinate ring $\mathbb{C}[X({\underline{\Delta}} {\boldsymbol{i}})]$ of the braid variety $X({\underline{\Delta}} {\boldsymbol{i}})$ equipped with an initial seed arising from a Demazure weave $\mathfrak{W}$, where ${\boldsymbol{i}}$ and ${\underline{\Delta}}$ are expression sequences of $\mathtt{b}$ and the half twist $\Delta$, respectively. We explicitly construct a Demazure weave $\mathfrak{W}_{{\underline{\Delta}}}(\mathfrak{C})$ for each admissible chain $\mathfrak{C}$ associated with ${\boldsymbol{i}}$, and prove that there exists an algebra isomorphism $\varphi_{{\boldsymbol{i}}}\colon {\widetilde{\mathbb{A}}}_\mathbb{C}(\mathtt{b})\to\mathfrak{C}[X({\underline{\Delta}} {\boldsymbol{i}})]$ which is compatible with the two seeds arising from $\mathfrak{C}$ and $\mathfrak{W}_{{\underline{\Delta}}}(\mathfrak{C})$. Moreover, the isomorphism $\varphi_{{\boldsymbol{i}}}$ sends the PBW vectors ${\overline{\mathsf{p}}}_{{\boldsymbol{i}},k} \in {\widetilde{\mathbb{A}}}_\mathbb{C}(\mathtt{b})$ to the coordinates $z_k \in \mathfrak{C}[X({\underline{\Delta}} {\boldsymbol{i}})]$ indexed by the letters of ${\boldsymbol{i}}$. As applications, we investigate a connection between Demazure weaves and signed words via the $i$-boxes and interpret the isomorphism $\varphi_{{\boldsymbol{i}}}$ from the viewpoint of monoidal categorification using Hernandez–Leclerc categories.

The singular cohomology ring of a matroid is an algebraic invariant which generalizes the Chow ring of a matroid. We study combinatorial and Lefschetz properties of the singular cohomology ring of a uniform matroid. Combinatorially, we construct an explicit basis for the singular cohomology ring in terms of Koszul homology. From this basis we derive multiple formulas for the Hodge numbers of the cohomology ring that recover and extend known formulas for the Chow polynomial of a uniform matroid. We also use this basis to show that the singular cohomology ring of a uniform matroid satisfies the "quasi-projective strong Lefschetz property" – a slight weakening of the Hard Lefschetz property found in the Chow ring of a matroid.

For a finite group $G$, let $\beta(G)$ denote the minimum cardinality $|P|$ among finite posets $P$ whose automorphism group $\Aut(P)$ is isomorphic to $G$. While every finite group is realizable as the automorphism group of some finite poset, exact values of $\beta(G)$ are known only in special cases, most notably for cyclic groups. In this paper we prove that $\beta(\mathbb{Z}_2 \times \mathbb{Z}_4) = 14$; in particular, the product bound $\beta(G \times H) \le \beta(G) + \beta(H)$ is sharp in this case. The upper bound is realized by an explicit $14$-element poset $P_{14}$, whose automorphism group is computed by a height-function argument together with a rigidity analysis of its covering relations. The lower bound, which constitutes the substantive part of the proof, is established by a case analysis of the orbit decompositions of a hypothetical poset on at most $13$ points under a faithful $G$-action, organized according to the largest orbit size; in each case we construct an order-automorphism outside the given copy of $G$, contradicting $\Aut(P) \cong G$. Among non-cyclic groups, to our knowledge this is the first exact determination of $\beta(G)$ whose lower bound requires a structural analysis of this kind: for the other non-cyclic abelian groups of order at most $8$, namely $\mathbb{Z}_2 \times \mathbb{Z}_2$ and $\mathbb{Z}_2^3$, the value of $\beta$ is elementary. The arguments are closely adapted to the subgroup lattice of $\mathbb{Z}_2 \times \mathbb{Z}_4$.

We show that, for every $\varepsilon>0$ and all sufficiently large $k$, any spanning subgraph of the $k$th power of a cycle with minimum degree at least $(1+\varepsilon)k$ contains a Hamilton cycle. This asymptotically settles a conjecture of Espuny Díaz, Lichev, and Wesolek.

A b-coloring of a graph $G$ is a proper vertex coloring where each color class contains at least one vertex (a b-vertex) adjacent to a vertex in every other color class. The maximum number of colors in such a coloring is the b-chromatic number, ${\rm b}(G)$. A ${\rm b}^{\ast}$-coloring is a variation in which a b-vertex is adjacent to a b-vertex in every other color class. We employ the ${\rm b}^{\ast}$-coloring to prove that any $n$-vertex graph $G$ with independence number at most $t$ satisfies ${\rm b}(G) \leq [(t-1)n+t\chi(G)]/(2t-1)$. This bound extends the bounds of Kouider and Zaker (2006) and Alkhateeb and Kohl (2011) and improves the bound in terms of the clique partition number. We show that this bound is sharp for all $t\geq 2$ and $\chi(G)\geq 3$. Furthermore, we provide a refined bound based on the maximum number of vertex-disjoint independent sets of size $t$. Finally, we prove ${\rm b}^{\ast}(G) \leq [(t-2)n+(t-1)\chi(G)]/(2t-3)$ for all $K_{1,t}$-free graphs $G$, a significant improvement over the analogous bound for ${\rm b}(G)$.

Spielman-Srivastava spectral sparsification preserves Laplacian quadratic forms to within (1 +/- epsilon), but does not directly control the adjacency spectral radius lambda_1, which governs the NIMFA epidemic threshold and arises in spectral clustering. We prove |lambda_1(A_H) - lambda_1(A_G)| <= epsilon(2 Delta - lambda_1) deterministically, with a sharp epsilon*lambda_1 bound for reweighting sparsifiers via Perron-Frobenius monotonicity. Under effective-resistance sampling, Matrix Bernstein gives O(epsilon Delta / sqrt(c)) with high probability. Combining eigenvector delocalization with resolvent perturbation theory, we establish that for graphs with delocalized Perron eigenvectors and spectral gap = Omega(Delta), the distortion is O(epsilon Delta sqrt(log n) / sqrt(n)) + O(epsilon^2 Delta^2 / delta_gap), with corollaries for Erdos-Renyi graphs, regular expanders, and stochastic block models. Lower bounds establish tightness for regular graphs.

With $\rho = \frac{13-\sqrt{69}}{10} \approx 0.47$, it was recently established that there exist multiplicative Sidon sets (sets without any non-trivial solutions to $ab = cd$) in $\{1, 2, \ldots, n\}$ with maximal gap size $\ll_{\varepsilon} n^{\rho + \varepsilon}$. Here we improve upon this result and show that one can take $\rho = \frac{10}{33} \approx 0.303$ instead.

We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let $\textsf{C}$ be a family of $n$-qubit states such that: $(i)$ $\textsf{C}$ is succinctly representable and $(ii)$ there is a weak agnostic learner of $\textsf{C}$. We give a tomography protocol for an unknown state $|\psi\rangle$ that is promised to admit a decomposition of the form $|\psi\rangle = \sum_i c_i |\phi_i\rangle$, where $|\phi_i\rangle \in \textsf{C}$ with bounded $\ell_1$-norm of the coefficients (which we call extent). Our main contribution is to show that a weak agnostic learner for $\textsf{C}$ can be boosted into a tomography algorithm for states with bounded extent with respect to $\textsf{C}$. Our reduction is black-box and applies broadly across model classes. As an application, when $\textsf{C}$ is the class of stabilizer states, we obtain tomography algorithms for states with stabilizer extent $\xi$ up to trace distance $\varepsilon$, in time $\textsf{poly}(n,(\xi/\varepsilon)^{\log(\xi/\varepsilon)})$, which is improvable to $ \textsf{poly}(n,\xi,1/\varepsilon)$ assuming the algorithmic polynomial Freiman-Ruzsa conjecture in the high-doubling regime. When the unknown state $|\psi\rangle$ is arbitrary, we give an algorithmic decomposition result in the spirit of a weak regularity lemma for quantum states with respect to $\textsf{C}$ and show that the structure in $|\psi\rangle$ that is explainable by $\textsf{C}$ can be efficiently learned. Our main conceptual message is that agnostic learning of a structured base class automatically yields learnability of its low-complexity linear span.

Let $H$ be a fixed 3-chromatic graph, and let $g \geq 2$ be the smallest integer such that there is no homomorphism $H \rightarrow C_{2 g+1}$. For every $\varepsilon>0$, we prove that there exists a constant $\rho>0$ such that every $H$-free $n$-vertex graph $G$ with $\delta(G) \geq(2 /(2 g+1)+\varepsilon) n$ can be made bipartite by deleting $O\left(n^{2-\rho}\right)$ edges. Thus the sharp qualitative minimum-degree stability theorem for 3-chromatic graphs admits a polynomial strengthening. In particular, this gives an affirmative answer to a question of Illingworth [\textit{Minimum degree stability of $H$-free graphs}, Combinatorica, 43(1):129-147, 2023.] on blow-ups of odd cycles.

We study growth rates of infinite and finite sumset patterns in sets of positive density. In the infinite setting, we show that no such rate exists, answering a question of Kra, Moreira, Ritcher, and Robertson. Namely, for any proposed growth rate $\mathcal{H}: \mathbb{N} \to \mathbb{N}$ tending to infinity, we construct a set $A$ of lower density $1$ such that whenever $B,C \subseteq \mathbb{N}$ are infinite and $B+C \subseteq A$ we have the minimum of $|B\cap [N]|$ and $|C \cap [N]|$ is less than $\mathcal{H}(N)$ for infinitely many $N$. In the finitary setting, we prove that for all $\delta \in (0,1)$, for all sufficiently large $N$, for all subsets $A$ of $\{1,\dots,N\}$ of proportion $\delta$, one can always find sumset patterns $B+C\subseteq A$ with $|B|$ and $|C|$ of order $\log N$, partially resolving a conjecture of Kra, Moreira, Richter, and Robertson. Moreover, we generalize our second result to the case of the $k$-fold sum $B_1 + B_2 + \ldots + B_k \subseteq A$.

The study of set families with restricted Hamming distances is a classical topic of extremal combinatorics and coding theory. Let \(H=\{A\subseteq[n]: |A|\text{ is even}\}\) be the even subcube. Let \(\ell_1,\dots,\ell_t\) be distinct positive integers and set \(\mathcal L=\{2\ell_1,\dots,2\ell_t\}\). We prove that, for all sufficiently large \(n\), every family \(\mathcal F\subseteq H\) satisfying \( |A\triangle B|\in\mathcal L \) for all \(A\ne B\in\mathcal F\) has \[ |\mathcal F|\le \sum_{i=0}^{t}\binom{n-1}{i}. \] This is best possible as a universal bound, with equality attained at the distance set \(\mathcal L=\{2,4,\dots,2t\}\). Our proof uses a Fourier-inertia argument based on a universal low/high boundary-layer sign pattern for the Fourier transform of the distance-polynomial kernel on the even subcube: the prescribed distances enter only through lower-order Fourier terms, while the leading boundary-layer signs depend solely on \(t\). This even-subcube result immediately yields an odd-subcube analogue and, through parity reductions, provides bounds for arbitrary distance sets. In particular, this approach recovers the classical interval bounds of Kleitman and the corresponding interval bounds of Huang–Klurman–Pohoata, while offering a direct spectral proof of the maximality of \(\{2,4,\dots,2t\}\) among all fixed \(t\)-distance sets.

Let \(B_n\) denote the book graph consisting of \(n\) triangles sharing a common edge. Rousseau and Sheehan (1978) proved, using Paley graphs, that \(R(B_n,B_n)=4n+2\) whenever \(4n+1\) is a prime power. Since then, only a few additional exact values of \(R(B_n,B_n)\) have been obtained. In this paper, we obtain \(R(B_n,B_n)=4n+1\) for infinitely many \(n\) by constructing graphs from pseudo-cyclic strongly regular graphs (PC-graphs). To the best of our knowledge, this is the first new infinite family of exact diagonal book Ramsey numbers since 1978. We also prove that \(R(B_{n-2},B_n)\le 4n-3\) for every \(n\ge 3\) with \(n\ne 6\), removing the original condition \(n\equiv 2\pmod 3\) imposed by Rousseau and Sheehan. Moreover, equality \(R(B_{n-2},B_n)=4n-3\) holds if there exists a symmetric Hadamard matrix of order \(2n-2\) with all diagonal entries equal to \(1\). In particular, this equality holds for every \(n=2^{2\ell-1}+1\) with \(\ell\ge 1\).