Papers

We show that the logarithmic Sobolev inequality of the Boolean cube is stable under random monotone censoring. More precisely, if $A_n\subseteq \{0,1\}^n$ is chosen uniformly among all monotone subsets, then the logarithmic Sobolev constant of the censored walk on $A_n$ is of order $n$ with high probability. As a consequence, several analytic and probabilistic properties of the Boolean cube persist for a typical monotone subset: the censored semigroup is hypercontractive, the uniform measure on $A_n$ satisfies Gaussian concentration for Lipschitz observables, and the associated walk mixes in time $O(n\log n)$. The latter proves a conjectured mixing bound of Ding and Mossel for almost all monotone sets. The result is genuinely typical rather than universal. We construct monotone sets of density bounded away from zero whose logarithmic Sobolev constant is of order $n^2$. To prove the result, we establish a sharp logarithmic Sobolev inequality for Hamming caps and combine it with a harmonic extension argument transferring this inequality to monotone sets lying between nearby caps, together with a structural theorem of Korshunov on random monotone sets.

The interest in studying the size of the intersection of multiple $q$-ary Hamming balls has grown due to the recent advances in DNA-based data storage systems. We present an exact formula for the cardinality of the intersection of $s$ Hamming balls of varying radii over a $q$-ary alphabet. It is known that the distances between the center points of the Hamming balls are not enough, in general, to determine the size of the intersection. Based on our formula, we are able to find more refined structural properties of the center points for determining the exact size of the intersection. Moreover, we also analyze the size of the intersection for sufficiently large $n$. When $s=3$, we give the necessary and sufficient conditions (for all $q\ge 2$, $q\neq 6$ and sufficiently large $n$) to obtain the maximum size of the intersection when the center points of the Hamming balls have a given minimum distance and demonstrate how to compute it using our general formula.

A bicoloration of a graph $G=(V,E)$ is a map $\beta:V\to\{-1,1\}$. A local inversion at a vertex $v$ complements the subgraph induced by the neighbors of $v$ and simultaneously reverses the colors of all neighbors of $v$. Sabidussi (Discrete Mathematics, 1987) showed that every bicolored graph on $n$ vertices without isolated vertices admits a color reversal using at most $6n+3$ local inversions, and that any two bicolorings of such a graph can be transformed into each other using at most $9n$ local inversions. Recently, Porte, Sandeep, and Santra (CALDAM 2026) improved these bounds to $4n-3$ and $\lfloor(11n-3)/2\rfloor$, respectively. We prove the tight bound $3n$ by showing that, for every graph on $n$ vertices without isolated vertices, any bicoloring can be transformed into any other bicoloring using at most $3n$ local inversions. We also show that this bound is best possible: for complete graphs and stars on $n$ vertices, at least $3n$ local inversions are required to reverse the colors of all vertices. Moreover, the proof of the upper bound is constructive: given two bicolorings, it produces, in polynomial time, a sequence of at most $3n$ local inversions transforming one into the other.

A function $f \colon X^k \to X$ on a finite set embeds into a polynomial of total degree $d$ over a commutative ring $R$ if there is an injection $j \colon X \to R$ and a polynomial $g$ of total degree at most $d$ with $j \circ f = g \circ j^k$, where $j^k$ applies $j$ in each coordinate. These are the transition functions of $k$-neighbour cellular automata, and the injection $j$ is an enlargement of the alphabet that preserves the transitions. We prove three results, all verified in Lean~4 with Mathlib~\cite{bacik2026finbin}. Every unary function $f \colon X \to X$ embeds into a polynomial of total degree $1$. Every binary Kronecker delta embeds into a polynomial of total degree $4$. For every $d$ there is a binary function that does not embed into any polynomial of total degree $d$.

We classify and count binary necklaces [w] for which the representative-independent minimum nontrivial rotational Hamming distance minDist(w) equals 2, the first positive layer after the periodic case. With a fixed priority convention, the set of nonzero shifts attaining distance 2 determines a classification into half-turn (HT), single-pair (SP), and subgroup-pattern (SUB) classes, while the residual multi-pair (MP) class is empty. We give closed formulas for the HT, SP, and SUB counts and an explicit Mobius-totient divisor-sum formula for |D_2(n)|. We also describe the larger subgroup-shaped branch, which contains the SUB cases together with boundary cases assigned by priority to HT and SP, by a quotient-background normal form and its boundary counts. For odd prime lengths p, every distance-2 necklace is rotation-equivalent to an arithmetic interval on the prime cycle, and |D_2(p)| = (p^2 - 4p + 7)/2.

Talagrand's correlation inequality provides a quantitative strengthening of the Harris–Kleitman inequality for increasing Boolean functions. Motivated by a Fourier-analytic conjecture of Friedgut, Kahn, Kalai, and Keller, we prove that $$ \mathrm{Cov}(f,g)\ge 2\sum_{S\neq\emptyset}|S|\hat f(S)^2\hat g(S)^2 $$ holds for all increasing Boolean functions $f,g:\{0,1\}^n\to\{0,1\}$. The proof combines the reverse Bonami–Beckner inequality with Young's convolution inequality. We also establish a sharp pointwise inequality: for every $n\ge1$, every $0\le\rho\le1$, and every $f,g:\{0,1\}^n\to[0,1]$, the optimal constant $c_{\rho,n}$ for which $$ \left\langle f,T_\rho g \right\rangle\ge c_{\rho,n}\|f*g\|_2^2 $$ holds for all such $f,g$ is $1$ for $0\le\rho\le1/2$, $(2(1-\rho))^n$ for $1/2<\rho<1$, and $0$ for $\rho=1$. Integrating this pointwise inequality yields, for $n\ge1$, the slightly improved bound $$ \mathrm{Cov}(f,g)\ge 4\cdot\frac{n+1}{2n}\sum_{S\neq\emptyset}|S|\hat f(S)^2\hat g(S)^2. $$

Guiduli asked in 1996 the following problem concerning the maximum spectral radius of a graph under hereditary density constraints. If an $n$-vertex graph $G$ satisfies $e(H)\le c|V(H)|^2$ for every subgraph $H$ of $G$, must one have $\lambda(G)\le 2cn$? More generally, what remains true when the exponent $2$ is replaced by a constant less than $2$? We study the natural power-law version of this question for all $1<p\le2$. For $1<p\le 2$, define \[ d_p(G)=\max_{\varnothing\ne S\subseteq V(G)}\frac{e(G[S])}{|S|^p}. \] We determine the sharp asymptotic upper bound for $\lambda(G)$ in terms of $d_p(G)$ and $n$. More precisely, every $n$-vertex graph $G$ with at least one edge satisfies \[ \lambda(G)\le \begin{cases} \left(\left(\max_{t\in\mathbb N_{\ge1}}\dfrac{t}{(t+1)^p}\right)^{-1}+o(1)\right)d_p(G)\sqrt n,&1<p<3/2,\\[0.4em] \left(\dfrac{3\sqrt3}{4}+o(1)\right)d_p(G)\sqrt{n\log n},&p=3/2,\\[0.4em] (\mathfrak C_p+o(1))d_p(G)n^{p-1},&3/2<p<2, \end{cases} \] and each constant here is best possible. Here $\mathfrak C_p$ is characterized by an exact variational problem over finite kernels. We apply a sparse graphon operator estimate to convert hereditary $p$-density bounds into sharp spectral bounds, and this estimate also explains the transition at the critical exponent $p=3/2$. For the endpoint $p=2$, Wilf's theorem gives the exact finite-$n$ bound $\lambda(G)\le 2d_2(G)n$, with equality for $K_n$. Thus Guiduli's power-law problem is resolved in its sharp asymptotic form for every $1<p\leq2$, including exact leading constants.

Recently there has been some progress in understanding the density of a subset of $[N]^2$ that avoids polynomial patterns. Kravitz, Kuca, and Leng showed that if $P\in\mathbb{Z}[z]$ satisfies certain conditions, then any set $A\subseteq[N]^2$ does not contain $(x,y),(x+P(z),y),(x,y+P(z))$, we must have \[ |A|\ll_P\frac{N^2}{(\log\log\log N)^c} \] for some small constant $c$. In this article, we show a similar result in $(\mathbb{F}_p)^2$ where we get a better bound on the density of a set $A\subseteq (\mathbb{F}_p)^2$ not containing $(x,y),(x+P(z),y),(x,y+P(z))$ with some conditions on $P\in \mathbb{F}_p[z]$.

We study Dyck paths refined simultaneously by proper area and water capacity, where water capacity is measured above the path and below its lattice-path upper hull. The finite-height ingredients used in the enumeration are classical bounded-height area-polynomial and continued-fraction objects. The upper-hull decomposition produces a coupled area–capacity substitution, which gives an exact four-variable height expansion with denominator branches indexed by the height levels. The full generating function is asymmetric in the two weights, while the height summands admit a symmetric unreduced denominator representation under interchange of the area and capacity weights. In the open square $0<p,q<1$, we prove that the length radius of $G(x,1,p,q)$ is the minimum of the positive real denominator branches. The proof combines uniform normal convergence of the height expansion below this first branch with a Perron-root representation of the branch locations and an interval log-submodularity theorem for spectral radii of weighted paths. On the diagonal $p=q=s$, the classical Chebyshev specialisation gives explicit branch crossings and a $(1-s)^{2/3}$ branch-envelope accumulation law at the Dyck critical point.

Let $p>3$ be a prime and let $$f_{\lambda_1,\lambda_2}(x)=x^{p^2-p+1}+\lambda_1x^{p^2}+\lambda_2x^{2p-1}\in\mathbb F_{p^2}[x].$$ We determine all pairs $(\lambda_1,\lambda_2)\in(\mathbb F_{p^2})^2$ for which $f_{\lambda_1,\lambda_2}$ is a permutation polynomial of $\mathbb F_{p^2}$. The final classification consists of three explicit families. The first one is the binomial case $\lambda_1=0$. The other two are obtained from the condition $\lambda_2=c\lambda_1^3$, with $c\in \mathbb F_{p}^{*}$, and are defined by two simple equations involving the norm $\lambda_1^{p+1}$. The proof is based on the AGW criterion and on the study of a quartic curve naturally associated with the rational function induced on the unit circle $\mu_{p+1}$.

The meet of two points in $\mathbb{Z}^d$ is their coordinatewise minimum. We show that every finite antichain $A$ in $\mathbb{Z}^d$ has at least $c_d |A|^{d/(d-1)}$ distinct pairwise meets, where $c_d > 0$ depends only on $d$, and that the exponent $d/(d-1)$ is best possible. As a corollary we obtain an isoperimetric inequality for downsets: every finite downset $D$ in $\mathbb{Z}^d_{\geq 0}$ satisfies $|D| \geq c_d |\max(D)|^{d/(d-1)}$, where $\max(D)$ is its set of maximal elements. By prime factorization the meet bound also yields a lower bound on greatest common divisors: a primitive set of $N$ integers supported on at most $d$ primes has at least $c_d N^{d/(d-1)}$ distinct pairwise gcds.

We study the maximal number $m_{k,\ell,n}$ of empty convex $k$-gons ($k$-holes) determined by an $n$-point set in the plane in general position that contains no empty convex $\ell~$-gon, focusing on the first nontrivial case $\ell=k+1$. Our main result determines the exact value in the small-excess regime: for $n=k+a$ with $a\le k/2-1$, we prove $m_{k,k+1,k+a}=2^a.$ We also describe the extremal configurations attaining equality. Beyond this exact range, we provide upper and lower bounds in the proportional regime $n=\alpha k$ and in the regime where $k$ is fixed and $n$ goes to infinity. In the last mentioned regime we prove that $m_{k,k+1,n}=\Omega_k(n^{\lfloor\frac{k}{3}\rfloor})$ and $m_{k,k+1,n}=O_k(n^{\lfloor k/2\rfloor+1})$.

This paper uses theoretical results previously established in the literature to design search algorithms to find new linear codes over $\mathbb{Z}_4$ from cyclic and negacyclic codes of even length. As a result of these searches, we have found 2500 new cyclic codes and 730 negacyclic codes. These new codes exhibit improved parameters compared to previously known codes. Additionally, we have obtained binary quantum codes with good parameters from such $\mathbb{Z}_4$ codes.

We consider some extremal combinatorial questions for bipartite graphs definable in stable one-based (and related) structures. We show that they satisfy both strong Erdős-Hajnal property and linear Zarankiewicz. We also show that the same is true for both collapsed and uncollapsed Hrushovski's “ab initio” constructions, and discuss some connections to Zilber's trichotomy principle. For strong Erdős-Hajnal, we show that in fact it holds in a more general class of $1$-semi-equational theories.

We show that if $L$ is an extremal Type II lattice of rank $72$, then $L$ is generated by its vectors of norm $10$. The proof determines the full inner product distribution between the shells of norms $8$ and $10$ using the spherical $11$-design property of the norm-$10$ shell.

We study degree-$2$ Siegel theta series of extremal even unimodular lattices from the genus-$2$ viewpoint initiated by Ozeki. Using Igusa's structure theorem, we define a depth filtration on genus-$2$ cusp forms, measured by the total degree in $\chi_{10}$ and $\chi_{12}$, and relate it to the vanishing of low Fourier–Jacobi coefficients forced by extremality. In ranks $48$, $72$, and $96$, this interaction closes exactly and yields a direct genus-$2$ proof that the degree-$2$ theta series is uniquely determined by extremality (conditional on existence in rank $96$). In rank $120$ (again conditional on existence), the same argument leaves a one-dimensional residual line spanned by $\chi_{10}^6$: with $\chi_{10}$ in the standard integral normalization, any two such degree-$2$ theta series differ by an integer multiple of $\chi_{10}^6$.

Recently the poset of ranked cactuses $(\mathfrak{P}(X),\preceq)$ was introduced. For a finite set $X$, this poset consists of a set $\mathfrak{P}(X)$ of certain collections of ordered pairs of subsets of $X$ together with an ordering $\preceq$ that is similar to the refinement ordering of partitions of a finite set. In addition, the maximal chains in this poset correspond to binary ranked cactuses, a fact which can be used to construct the so-called space of equidistant cactuses. In this paper, we show that the poset of ranked cactuses is EL-shellable. As a consequence we also show that the proper part of the link of the origin of the space of equidistant cactuses has the homotopy type of a wedge of spheres.

Let \(V\) be an \(n\)-dimensional vector space over the finite field \(\Fq\), and let \(\Gr{V}{k}\) denote the family of all \(k\)-dimensional subspaces of \(V\). A family \(\cF\subseteq\Gr{V}{k}\) is called intersecting if \(\dim(F\cap F')\ge1\) for all \(F,F'\in\cF\). For a point \(P\le V\), let \(d_P(\cF)\) denote the number of members of \(\cF\) that contain \(P\), and order the point-degrees as \(d_1(\cF)\ge d_2(\cF)\ge\cdots\ge d_{\points{n}}(\cF)\), where \(\points{m}=(q^m-1)/(q-1)\) is the number of points in an \(m\)-dimensional subspace. Recent work of Frankl and Wang~\cite{FW2025} and of Huang and Rao~\cite{HR2026} established that for \(k\)-uniform intersecting families \(\cF\subseteq\binom{[n]}{k}\) with \(n\ge2k+1\), the bound \(\binom{n-2}{k-2}\) governs the order statistic \(d_{2k+1}(\cF)\). We prove that every intersecting family \(\cF\subseteq\Gr{V}{k}\) with \(n\ge2k+1\) satisfies \(d_{\points{k}^{2}}(\cF)\le\qbinom{n-2}{k-2}\). The naive \(q\)-analog of the Huang–Rao \((k+2)\)-th degree theorem fails, as a vector-space Hilton–Milner construction has \(\points{k+1}\) points of degree larger than \(\qbinom{n-2}{k-2}\); we prove the corrected bound \(d_{1+\points{k+1}}(\cF)\le\qbinom{n-2}{k-2}\) for fixed \(q\), sufficiently large \(k\), and \(n>3k\), using a structural theorem of Ihringer and Kupavskii~\cite{IK2026}. For larger degree indices \(i\), a saturated Frankl–Hilton–Milner family of Ihringer and Kupavskii identifies the conjectural sharp bound on \(d_{\points{i+1}}(\cF)\), and we prove two necessary conditions that any strict counterexample to this conjecture must satisfy.

We give a short analytic proof of Raposo's signed refinement of Pohst's inequality.

In this paper, we establish two families of $q$-supercongruences modulo the third and fourth powers of a cyclotomic polynomial by employing Watson's ${}_{8}\phi_7$ transformation, the creative microscoping method introduced by Guo and Zudilin, and the Chinese remainder theorem for coprime polynomials.

We prove that level-$\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate the Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\leq \ell \leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior works, we apply it to an appropriate collection of blocks of Johnson eigenspaces. Our analysis relies on a new, simple band-locality property for arbitrary Kikuchi graphs. As an application, we prove that the natural degree-$2\ell$ sum-of-squares relaxation for the Max $2r$-XOR problem is “integral” when the input is a planted noisy $2r$-XOR instance on a random hypergraph with $\gtrsim n \cdot (n/\ell)^{r-1} \log n$ hyperedges.

We study the $t$-uniform hypergraphicality problem under a compressed representation of the degree sequence. Instead of listing all vertex degrees explicitly, the input consists of pairs $$ (\delta_1,n_1),\dots,(\delta_k,n_k), $$ meaning that exactly $n_i$ vertices have degree $\delta_i$. Thus the parameter $k$ denotes the number of distinct degrees. Although deciding $t$-hypergraphicality is NP-complete for every fixed $t>2$, we prove that the problem is fixed-parameter tractable parameterized by $(k,t)$. Our result shows that tractability extends substantially beyond previously known bounded-range regimes: even degree sequences with large overall degree spread can be handled efficiently when the number of distinct degrees is bounded. Our approach decomposes hyperedges according to their types with respect to the degree classes, yielding a bounded-dimension spectrum representation. Using balancing hinge-flips, we show that every feasible spectrum can be transformed into a realization of the prescribed degree sequence. This leads to an integer programming feasibility formulation with $$ \binom{t+k-1}{k-1} $$ variables. Applying Lenstra's theorem yields an FPT algorithm running in time $$ f(k,t)\cdot \mathrm{poly}(L), $$ where $L$ denotes the encoding length of the compressed input.

Let $f(n,k)$ be the minimum size of a collection of bicliques such that (i) every edge of the complete graph $K_n$ is covered by at least one and at most $k$ bicliques in the collection, and (ii) for each edge $\{u,v\}$, the number of bicliques in which $u$ appears in the first class and $v$ in the second class differs by at most one from the number of bicliques in which $u$ appears in the second class and $v$ in the first class. For $k=1$, $f(n,k)$ reduces to the biclique partition number of $K_n$, and the Graham-Pollak theorem gives $f(n,1)=n-1$. For $k=2$, $f(n,k)$ is the ordered biclique partition number of $K_n$, for which it is known that $c_1 n^{1/2} \le f(n,2) \le c_2 n^{1/2+o(1)}$ for some positive constants $c_1$ and $c_2$. In this note, we give almost tight bounds for $f(n,k)$ for fixed $k \ge 2$: \[ (1+o(1))c_1(k)\cdot n^{\frac{1}{\lceil k/2\rceil+1}} \le f(n,k) \le (1+o(1))c_2(k)\cdot n^{\frac{1}{\lfloor k/2\rfloor+1}+o(1)}, \] where $c_1(k)$ and $c_2(k)$ are positive constants.

Let $G$ be a graph. The size and the signless Laplacian spectral radius of $G$ are denoted by $e(G)$ and $q(G)$, respectively. A spanning subgraph $F$ of $G$ is called an $H_b$-factor of $G$ if $d_F(v)\in\{1,3,5,\ldots,b-1,b\}$ for every $v\in V(G)$, where $b\geq2$ is an even integer. Lu and Wang obtained a sufficient condition according to the number of odd components in $G-S$ for a connected graph $G$ of even order to have an $H_b$-factor, where $S$ is a subset of $V(G)$ [H. Lu, D. Wang, On Cui-Kano's characterization problem on graph factors, J. Graph Theory 74 (2013) 335–343]. In this paper, motivated by Lu and Wang's above result, we establish a lower bound for the size in an $n$-vertex connected graph $G$ with given minimum degree to guarantee that $G$ has an $H_b$-factor. Further, we show a lower bound for the signless Laplacian spectral radius in an $n$-vertex 2-connected graph $G$ with given minimum degree to ensure that $G$ has an $H_b$-factor.

This paper investigates the nonexistence of solutions to semilinear parabolic and hyperbolic inequalities with positive potentials on metric graphs, including both nonnegative solutions and sign-changing solutions. The Laplacian under consideration is of a nonstandard type, incorporating contributions from both the vertices and edges of the metric graph. We construct a new pseudo-metric and introduce suitable space-time test functions of either coupled or separated type. Under suitable weighted space-time volume growth conditions on the potential, we establish nonexistence results for very weak solutions. More precisely, we show that all such solutions to the inequality must be identically zero.

Let $L_\mu(G)=A(G)-\mu D(G)$ be the generalized $\mu$-adjacency matrix of a finite graph $G$. Fan, Xing, Zhang, and Wang constructed pairs of non-degree-similar trees for which the Smith normal forms of the matrices $tI-L_\mu(G)$ over $\mathbb{Q}(\mu)[t]$ coincide, and conjectured that their construction remains valid when the attached rooted path is replaced by an arbitrary rooted tree. We prove this conjecture as a consequence of a more general coalescence theorem: if a finite graph $H$ has two vertices $u$ and $v$ that are cospectral for $L_\mu(H)$, then, for every finite rooted graph $R$ with root $r$, the matrices \[ tI-L_\mu(R(r)\odot H(u)) \quad\text{and}\quad tI-L_\mu(R(r)\odot H(v)) \] have the same Smith normal form over $\mathbb{Q}(\mu)[t]$, where $\odot$ denotes coalescence of rooted graphs. The proof uses an orthogonal intertwiner over a real closed extension field.

Let $s$ denote West's stack-sorting map. In 2020, Defant characterized and enumerated the set $s^{n-m}(S_n)$ for $n \geq 2m-3$. While $|s^{n-m}(S_n)| = B_m$ when $n \geq 2m-2$, where $B_m$ denotes the $m$th Bell number, there are additional permutations when $n = 2m-3$. In this paper, we explore the more complex $n = 2m-4$ case, with several forms of additional permutations. We characterize $s^{m-4}(S_{2m-4})$ and find that its size is \[B_m + \frac{m^2 + 7m - 28}{2}\] for $m \geq 5$. This answers Defant's question about the $2m-4$ case. Furthermore, we find some differences in the behavior of the $2m-5$ case compared to the $2m-3$ and $2m-4$ cases.

For a digraph $D$, let $\alpha_2(D)$ be the largest size of a vertex set no two of whose vertices lie in a common directed $2$-cycle. Let $f_2(a)$ be the least integer $K$ such that every $K$-connected digraph $D$ with $\alpha_2(D)\le a$ has a Hamilton cycle. Jackson proved in 1987 that $f_2(a)\le2^a(a+2)!$, whereas a conjecture of Jackson and Ordaz predicts $f_2(a)\le a+1$. We prove the quadratic bound $f_2(a)\le12000a^2$. We also prove that $\kappa(H)\ge6000(\alpha(H)+r)$ guarantees vertex-disjoint paths joining any prescribed $r$ pairs of distinct vertices and covering $V(H)$.

We develop an explicit PBW normal ordering theory for the $26$ double extension regular algebras of type $(14641)$ in the Zhang-Zhang classification. With respect to the order $x_1\prec x_2\prec y_1\prec y_2$, we obtain closed two-letter formulas for the internal relations and recursive coefficient systems for mixed words, products of PBW monomials, powers of normal blocks, and noncommutative multinomial expressions. The internal coefficients are mostly quantum or skew-commutative, while the Jordan families produce Lah-Whitney, hence Stirling-type, triangular arrays. The symbolic reductions are supported by a SageMath implementation included as an ancillary file.

We prove several conjectures recorded in the On-Line Encyclopedia of Integer Sequences. The conjectures considered here concern determinants and permanents of special matrices, such as Toeplitz matrices, cross matrices, Kronecker powers of matrices, and matrices whose entries are defined by powers of differences. As tools we use row and column operations, block determinant formulas, Cauchy determinants, Sylvester's determinant theorem, and $LU$-factorizations. We also obtain closed-form formulas for several related integer sequences for which no such formulas were conjectured.