Papers

The Fibonacci, Lucas, and Pell sequences satisfy certain families of “polynomial” identities. While a few members of these families are well-known, we are not able to find a general statement of these identities in the mathematical literature. We show that such polynomial identities exist for many generalized Fibonacci sequences, and we classify sequences that have these identities obtained by two distinct approaches. One approach uses the Girard-Waring formula, while the other relies on Binet's formula and linear algebra.

A central problem in zero-sum theory is to determine the Davenport constant of a finite abelian group. For a finite abelian group $G\cong C_{n_1}\oplus\cdots\oplus C_{n_r}$, with $1<n_1\mid\cdots\mid n_r$, let $\mathsf D(G)$ be the least integer $t$ such that every sequence of $t$ elements of $G$ contains a nonempty zero-sum subsequence, and denote $\mathsf D^*(G):= 1+\sum_{i=1}^r(n_i-1)$. The standard construction shows that $\mathsf D(G)\ge\mathsf D^*(G)$. Equality holds for several important classes of groups but fails in general, and even the question whether $\mathsf D(G)/\mathsf D^*(G)$ is bounded by an absolute constant remains open. In this paper, we prove the upper bound \[ \mathsf D(G)<4.86\,\exp(G)\frac{\log|G|}{\log\exp(G)} \] for every finite abelian group. When $|G|$ is large compared with $\exp(G)$, it improves the previous classical upper bound by a factor of order $\log\exp(G)$. We also prove that, for almost all finite abelian groups (counting isomorphism classes by order), \[ \mathsf D(G)\sim\exp(G)\frac{\log|G|}{\log\exp(G)}\sim\mathsf D^*(G). \] We also study the difference $\mathsf D(G)-\mathsf D^*(G)$: for every function $L$ with $L(x)\to\infty$, almost all groups satisfy $\mathsf D(G)-\mathsf D^*(G)\le L(\mathsf D^*(G))$. However, for every fixed $C\ge0$, the groups with $\mathsf D(G)-\mathsf D^*(G)>C$ have positive lower density.

Let $K>1$ be a real number and let $A\subsetneq \mathbb Z$ be a finite and nonempty subset. Suppose $|A+A|<K|A|$. A fundamental open problem is to characterize the size of higher iterated sumsets $nA = A+\cdots+A$ ($n$-fold sumset). In 2004, Terry Tao formally posed the problem of determining the optimal growth function governing iterated sumsets of small-doubling sets. In this manuscript, we give a solution to this long-standing open problem for large enough $n$.

The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$ except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed–Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.

A bisection of a graph is a partition of its vertex set into two parts whose sizes differ by at most one. We prove that every graph with $m$ edges and maximum degree at most $k$ has a bisection of size at least $\frac{k+1}{2k}m$ when $k$ is odd, and at least $\frac{k+2}{2(k+1)}m$ when $k$ is even. Both bounds are sharp, with equality for complete graphs. This establishes the unweighted case of the bisection conjecture of Gerke, Gutin, Yeo and Zhou (arXiv 2024), removes the additive error from the corresponding bounds of Lee, Loh and Sudakov (JCTB 2013), and extends the odd-degree regular case proved by Bollobás and Scott (JGT 2004) to arbitrary graphs of bounded maximum degree. The proof combines the matching-and-pairing method with the Gallai–Edmonds decomposition. Hall's theorem controls the number of uncovered factor-critical components whose internal degrees are all even. A boundary-edge count bounds this obstruction by the total degree deficiency, while the remaining uncovered components supply the required pairing gain.

Richardson varieties provide geometric representatives for products of Schubert classes, with stratifications indexed by the subintervals of Bruhat intervals. We construct analogous geometric models for tilted Bruhat intervals for all split connected reductive groups. Our construction uses Richardson varieties in affine flag varieties and yields abstract tilted Richardson varieties whose isomorphism classes, together with their labeled stratifications, are independent of the choices involved. We obtain an explicit formula for the point-counting polynomials of their open parts in terms of increasing minimal weight paths, extending Dyer's formula for Kazhdan–Lusztig $R$-polynomials. Over the real numbers, their totally nonnegative parts are regular CW complexes homeomorphic to closed balls, which gives a natural geometric realization of the posets of tilted Bruhat subintervals in all Lie types. Over the complex numbers, we prove that their fundamental classes push forward under a continuous loop evaluation map to the Poincaré duals of the minimal-degree coefficients of quantum Schubert products.

Let $E$ be the exterior algebra of an $n$-dimensional vector space over a field, let $F$ be a graded free $E$-module with $r$ generators of degrees $d_1 \le \dots \le d_r$, and let $M$ range over the monomial submodules of Amata and Crupi. The Hilbert function of $F/M$ is a shifted sum of $f$-vectors of simplicial complexes; the companion paper determines the convex hull of such sums, and here we count them. For $r = 1$ the count is Linusson's (1999); we show that no new recursion is needed for general $r$. Using two statistics of an $f$-vector – its top nonvanishing degree and the initial degree of the corresponding ideal – we prove that the number of achievable Hilbert functions is a product of $r-1$ transfer matrices, one per generator-degree gap, with entries differences of Linusson's refined counts $E^p(n,k)$. The rank enters only as the length of a matrix product. The same holds for the proper variant. Consequences: a linear recurrence in $r$ for constant gaps, with exact exponential asymptotics $K \lambda^r$ when the gap is positive; polynomiality in $r$ when all gaps vanish; a threshold beyond which the count is a plain power; and polynomiality in the number of vertices.

Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).

Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde G$ with those of the trivial cover, consisting of $M$ disjoint copies of $G$, after prescribing how many vertices are selected above each vertex of $G$. A conjecture from 2011, motivated by the Bethe approximation, asserts that the trivial cover maximizes every such count. We prove this for every feasible occupation profile whose active graph has treewidth at most two or is chordal bipartite. Equality holds exactly when the restricted cover is flat, meaning that fibre relabelings make it trivial. For $M\ge2$ and positive feasible occupations, a nonflat cover of a connected bipartite graph of treewidth at most two has a deficit of at least twice the coefficient of $p_G^{M-2}$ with every occupation reduced by one. A holonomy-dependent bound improves the factor to three for odd-order holonomy; both uniform constants are sharp. Comparison and rigidity survive finite compositions along an edge or a vertex, and quantitative bounds from one piece propagate to the whole graph, giving results beyond the two original classes. On any bipartite base, the first nonzero homogeneous defect is determined by the shortest cycles with nontrivial holonomy. At singleton occupations, our counts are numbers of DP-colorings of full covers. The dual DP color function on these classes and their finite seam compositions equals the chromatic polynomial, with equality attained precisely by canonical labelings. Dong's chromatic-polynomial inequality then yields the Dual-DP Shameful inequality on the same graph class. The main theorems have been formalized in Lean 4.

We study a conjecture of Conlon, Fox, Gunby, He, Mubayi, Suk, Verstraëte, and Yu, which characterizes the $3$-graphs $H$ for which the off-diagonal Ramsey number $r(H,n)$ is polynomial. We prove the conjecture for $3$-graphs with at most five tight components. Additionally, we show that the full conjecture is equivalent to its specialization to linear $3$-graphs. We prove quasipolynomial upper bounds for a class of `forward-doubleable' $3$-graphs, which includes the Fano plane. Finally, we give an exponential lower bound for `non-forward-laminar' $3$-graphs and use this to completely classify the Ramsey growth of a natural family of 3-graphs called chains.

We characterize the generic consistency of vertical systems in terms of the iterated circuits of the column matroid of the coefficient matrix. More precisely, we prove that such a system is generically consistent if and only if there exists an iterated circuit such that the dimension of the Minkowski sum of the associated Newton polytopes is equal to the rank of the coefficient matrix. We also give an equivalent characterization in terms of $G$-spanning flags of the dual matroid. With this, we derive a combinatorial formula for the codimension of the locus of parameter values for which the system has a solution, extending known results on dual defects of toric varieties. When this locus has codimension one, its defining equation yields a generalization of the sparse resultant to vertical systems, which applies also to $\mathcal{A}$-discriminants. Finally, we characterize when the solution set is contained, for generic parameter values, in a finite union of hyperplanes parallel to a coordinate hyperplane.

Let $u_k^{(r)}(H,p)$ be the maximum, over all $k$-vertex $r$-uniform hypergraphs $F$, of the absolute difference between the number of induced copies of $F$ in $H$ and its expectation in the binomial random $r$-graph with the same number of vertices as $H$ and edge probability $p$. Let $u_k^{(r)}(n,p)$ be the minimum of $u_k^{(r)}(H,p)$ over all $n$-vertex $r$-uniform hypergraphs, and let $D_r(n,p)$ be the distance from $p\binom nr$ to the nearest integer. For fixed $r\ge3$, $k\ge2r$ and $\varepsilon>0$, the quantity $u_k^{(r)}(n,p)$ has order $\max\!\left\{D_r(n,p),p(1-p)\right\}n^{k-r}$ whenever $p(1-p)n^{\lfloor r/2\rfloor/(\binom{2r-2}{r}-1)}\ge\varepsilon$. Using local moment estimates and switchings in a sparse reservoir, we construct one hypergraph with the nearest-integer edge count that controls all induced orders simultaneously.

In this paper we study pairwise compatibility graphs whose witness tree is required to be an unweighted caterpillar. This is a natural restriction of PCGs, in the same line of research as the study of star witnesses, which led to the class of double-threshold graphs. In the caterpillar case, we show that this restriction is equivalent to a one-dimensional difference-labelling problem: a graph admits such a representation if and only if its vertices can be assigned integer labels so that adjacency is determined exactly by whether the absolute difference of two labels belongs to a given interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star $S_{2,2,2,2,2}$, the cube graph $Q_3$, the wheel $W_6$, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.

The reflection complexity of a sequence, introduced recently by Allouche, Campbell, Li, Shallit, and Stipulanti, counts the factors of a given length up to reversal. We generalize this notion considering a group $G$ generated by antimorphisms over a given alphabet $\mathcal A$. The $G$-complexity of a sequence over $\mathcal A$ counts the factors of a given length up to the action of $G$. For $G$ generated by the reflection alone, the $G$-complexity coincides with the reflection complexity. We characterize eventual periodicity in terms of the $G$-complexity. Then we focus on the binary alphabet and the group $H$ generated by reflection and the antimorphism exchanging letters. We provide a simple formula for the $H$-complexity in the case of $H$-rich sequences and determine the precise values for complementary symmetric Rote sequences and generalized binary Thue-Morse sequences. Finally, we describe the aperiodic recurrent sequences having the minimum $H$-complexity – they are exactly the complementary symmetric Rote sequences, while the binary sequences with the minimum reflection complexity correspond to the Sturmian sequences.

We establish sharp projection inequalities for $k$-antichains under orders defined by open convex cones. For integers $n\geq2$ and $k\ge 1$, let $C\subsetneq\mathbb R^n$ be a nonempty open convex cone. A set $A\subseteq\mathbb R^n$ is a $k$-antichain with respect to the order $x\prec_C y\iff y-x\in C$ if it contains no chain $x^1\prec_C\cdots\prec_C x^{k+1}$. For every such set $A$ and every $v\in C$, we prove \[ \mathcal H^{n-1}(A) \leq k\frac{\|v\|}{\alpha_C(v)} \mathcal H^{n-1}(P_v(A)), \] where $P_v$ is the orthogonal projection onto $v^\perp$, $\mathcal H^{n-1}$ denotes normalized Hausdorff outer measure, and $\alpha_C(v)$ is the minimum of $\langle\xi,v\rangle$ over unit vectors in the dual cone $C^*$. In particular, every weak antichain $A\subseteq\mathbb R^n$ satisfies $\mathcal H^{n-1}(A)\leq\mathcal H^{n-1}(\Delta_i(A))$ for each $i$, where $\Delta_i(x)=(x_j-x_i)_{j\ne i}$. This proves the skewed projection conjecture of Engel, Mitsis, Pelekis and Reiher. As an application, we recover the bound $\mathcal H^{n-1}(A)\leq kn$ for $k$-antichains in the unit cube under the coordinatewise order.

We prove that every finite simple triangle-free graph $G$ on $n\geq1$ vertices satisfies $q_{\min}(G)\leq7n/50$, where $q_{\min}(G)$ is the least eigenvalue of its signless Laplacian matrix $Q_G=D_G+A_G$, with $D_G$ the diagonal matrix of vertex degrees and $A_G$ the adjacency matrix. The constant is sharp, since the Higman–Sims graph and its balanced blow-ups attain equality, as shown by de Lima, Nikiforov and Oliveira (2016). This proves the bound conjectured by Balogh, Clemen, Lidický, Norin and Volec (2023). The proof uses five test column vectors associated with an ordered edge to obtain a matrix Rayleigh inequality. Our use of local Rayleigh inequalities together with flag-algebra semidefinite programming is inspired by Zhou (2026). We use semidefinite programming and rational approximation to find the required positive semidefinite matrices, and complete the proof by exact correction and verification.

We define a $d$-cube in a graph $G$ to be monophobic in $G$ if, whenever it supports a $d$-face of a discrete singular $d+1$-cube, it must also support another face. In many cases, the presence of such cubes implies the nontriviality of discrete cubical homology and homotopy groups associated with $G$. We describe several large classes of examples and characterize the property completely when $d=2$.

For a subset $A$ of a finite abelian group $G$, let $\Sigma_k(A)$ denote the set of sums of $k$ distinct elements of $A$, and let $\Sigma(A)=\bigcup_{k\ge1}\Sigma_k(A)$. The problem of determining when $\Sigma(A)=G$ goes back to Erdős and Heilbronn. Nguyen and Vu later formulated the corresponding fixed-length question: for a prescribed $k$, when does $\Sigma_k(A)=G$? For groups of odd order, we prove the sharp large-order threshold $|A|>|G|/3+1$, which forces $\Sigma_k(A)=G$ throughout the entire middle range $4\le k\le |A|-4$. This determines the limiting thresholds posed by Girard, Griffiths and Hamidoune. If $p$ is the least prime divisor of $|G|$, then, for fixed odd $p$ and sufficiently large $|G|$, the exact threshold $|A|\ge |G|/p+p-1$ forces covering throughout the middle range beginning at $2p-2$. Thus, throughout this range, prescribing the number of summands does not change the sharp covering threshold. For $3\le k\le2p-3$, the restricted and ordinary $k$-fold covering problems have the same asymptotic threshold. As an application to MDS elliptic codes on an elliptic curve $E/\F_q$, we sharpen the half-scale conjecture of Li, Wan and Zhang, obtaining the sharp $1/3$-scale bound when $|E(\F_q)|$ is odd and, more generally, the exact bound determined by the least prime divisor of $|E(\F_q)|$.

An edge labeling of a connected graph $G=(V, E)$ is called a local antimagic labeling if it is a bijection $f: E\rightarrow \{1, 2, \cdots, \left | E \right | \}$ such that for any pair of adjacent vertices $u$ and $v$, $f^{+}(u)\neq f^{+}(v)$ where $f^{+}(x)=\sum f(e)$, with $e$ ranging over all the edges incident to $x$. The local antimagic chromatic number of $G$, denoted $\chi_{la}(G)$, is the minimum number of distinct induced vertex labels across all possible local antimagic labelings of $G$. This paper investigates two families of graphs $G(m^{[n]})$ (a graph class constructed by augmenting a bipartite structure $B(m^{[n]})$ with cyclic edges) and $K_{1,s}\times C_n$ (the direct product of a star $K_{1,s}$ and a cycle $C_n$). Under the conditions odd integer $m\ge 1$ and even integer $n\ge 4$, we establish the exact values of $\chi_{la}(G(m^{[n]}))$ and $\chi_{la}(K_{1,s}\times C_n)$ for various $s$. Furthermore, we characterize several graph families achieving $\chi_{la}(G)=2$ or $3$.

We consider spin-coupled Grover walks on hypercubes within the framework of quantum Bernoulli noises (QBN). We identify parity-dependent harmonic subspaces generated by the central Hamming layers: in even dimension they give a fixed-point subspace, whereas in odd dimension the walk reduces on the harmonic subspace to an explicit eight-dimensional reduced dynamics. Using symmetric-group representation theory, we characterize the corresponding isotypic structure and determine the reduced spectrum. The harmonic reduction also yields explicit long-time probability behavior and shows that the resulting states may occupy an asymptotically vanishing fraction of the hypercube while still spanning its full Hamming diameter.

Identities of spanning forest polynomials can come from determinantal identities such as the classical Dodgson identity. They can also be useful in quantum field theory calculations, particularly the quadratic ones. To better understand the structure of spanning forest polynomial identities, we look at when identities on a given graph are generic for all graphs, we ask about dimensions of spaces of spanning forest identities indexed by certain parameters, and we set up a framework that we hope will be helpful for further progress in these directions. As part of this framework, we identify a family of maps naturally given by the all-minors matrix-tree theorem, and we show that their ranks are counted by the Narayana numbers via explicit construction of bases.

Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree $\Delta \geq 3$, then it admits a proper $\Delta$-coloring. In this paper, we give a new proof of a much stronger result: every such graph admits exponentially many proper $\Delta$-colorings. Exponential lower bounds have been obtained previously by applying the Combinatorial Nullstellensatz. In contrast, our proof is via a surprisingly simple and constructive analysis of a textbook greedy coloring algorithm. The entire argument is accessible to non-specialists. We extend our techniques to provide quantitative lower bounds on the number of colorings in several more general settings, namely $\Delta$-length list coloring, degree-length list coloring (degree-choosability), and degenerate partitioning. In the latter setting, one is asked to partition the vertices such that each partite set induces a subgraph of bounded degeneracy. In contrast to the other coloring variants considered, no clean Brooks-type characterization is possible, since it is known that for some combinations of parameters determining the existence of even one valid partition is NP-hard. We give a new reduction which significantly extends the parameter regime for which determining the existence of a valid partition is NP-hard. Finally, we give a new proof of the classic degree-choosability theorem, generalizing the techniques behind a recent proof of Brooks' Theorem.

Let $G$ be a finite simple graph on the vertex set $[n]$, and let $\Gamma(G)$ be the Cayley graph of the symmetric group $S_n$ generated by the transpositions corresponding to the edges of $G$. We study the inverse spectral problem for the assignment $G\mapsto \Gamma(G)$ through the group-algebra operator $A_G=\sum_{\{i,j\}\in E(G)}(ij)$ and its regular spectral moments $M_k(G)=\operatorname{tr}(A_G^k)$. The moments admit two all-order forms: a universal support expansion in non-induced subgraph counts of $G$, and a representation-theoretic expansion over the irreducible representations of $S_n$. We compute the first nontrivial moments through order six. In particular, the fourth moment already contains the Coxeter triangle relation and determines the signed local invariant $6N_{K_3}(G)-N_{P_3}(G)$, rather than $N_{P_3}(G)$ alone. Consequently, for triangle-free graphs the spectrum determines the second moment of the degree sequence. We also give a simplified sixth-moment formula for triangle-free graphs, showing that in this class the spectrum determines $5N_{K_{1,3}}(G)+2N_{P_4}(G)+12N_{C_4}(G)$. Further structural consequences include bipartiteness and spectral symmetry of $\Gamma(G)$, a precise connectedness test, and the identification of the standard irreducible component with the shifted graph Laplacian $mI-L_G$.

Let $M$ be a binary matroid of rank $r$ with no $F_7$-minor, and let $B_M^\star$ denote the maximum of its basis-generating polynomial over nonnegative weights of total mass $r$. We prove the sharp inequality $B_M^\star\leq 2^r/(r+1)$, with equality holding if and only if the nonloop simplification of $M$ is $M(K_{r+1})$. Binary matroids with no $F_7$-minor also form the largest minor-closed class of matroids on which this inequality holds.

The cardinalities of Kiselman's semigroups $K_n$ are known to grow double exponentially in $n$: the sequence $2^{-n/2}\log_2|K_n|$ converges along the even and odd $n$ subsequences to positive limits $c_{\mathrm{even}}$ and $c_{\mathrm{odd}}$ that appear to coincide. In this paper we prove that they are indeed distinct. Since Kiselman's semigroups are $\mathcal{L}$-trivial, the suffix relation defines a partial order on $K_n$. We introduce the Kiselman transform $\mathsf{Kis}(P)$ of a poset $P$, a construction recovering the poset associated with $K_{n+1}$ from that associated with $K_n$. Counting strictly increasing chains in $P$ and $\mathsf{Kis}(P)$ yields a linear recurrence governed by a symmetric infinite matrix with explicit binomial entries. This can be used towards efficiently computing $|K_n|$, allowing the values listed in OEIS sequence A125625 to be extended beyond $n=14$. A generating functions analysis gives formulas for the above asymptotic limits, together with rigorous numerical bounds establishing that \[ c_{\mathrm{even}} - c_{\mathrm{odd}} = 1.9945066605\ldots\times10^{-6} \]

For a graph $G$, we investigate sufficient degree conditions under which either $G$ or its complement $\overline{G}$ is $k$-connected. Motivated by a theorem of Hellwig and Volkmann, we introduce the notion of complement connectivity admissible pairs and define the parameter $\mathcal{C}(k)$ as the minimum degree threshold guaranteeing that either $G$ or $\overline{G}$ is $k$-connected whenever $\delta(G)\ge\mathcal{C}(k)$ and $\Delta(G)\le |V(G)|-1-\mathcal{C}(k)$. We prove that $\mathcal{C}(k)=2k-2$ for every $k\ge2$, thereby determining the exact degree threshold. As an application, we derive a Nordhaus–Gaddum type product condition, showing that for $n\ge4k-5$, the condition $\delta(G)\delta(\overline{G}) \ge (2k-3)(n-2k+2)$ guarantees that either $G$ or $\overline{G}$ is $k$-connected. Finally, we show that no analogous product condition depending only on $k$ can exist.

Let $\Phi$ be an irreducible root system normalized so that long roots have length $\sqrt{2}$, and let $\mu\leq\lambda$ be dominant weights. We associate to $(\Phi,\mu,\lambda)$ the convex polytope $$P^{\Phi}_{\mu,\lambda} = (\mu+C)\cap(\lambda-C)\cap(\overline{D}-\rho),$$ where $C=\mathbb{R}_{\geq 0}\Phi^+$ and $\overline{D}$ is the closed dominant Weyl chamber. We prove that if $P^{\Phi}_{\mu,\lambda}$ and $P^{\Phi'}_{\mu',\lambda'}$ are isometric, then $$K^{\Phi}_{\lambda\mu}(q)=K^{\Phi'}_{\lambda'\mu'}(q),$$ where $K^{\Phi}_{\lambda\mu}(q)$ is Lusztig's $q$-analogue of the $\mu$-weight multiplicity in the irreducible highest-weight representation $V(\lambda)$, often called the generalized Kostka-Foulkes polynomial. Moreover, we construct the polynomial directly from the metric shape of the polytope, and we classify when two such polytopes are isometric. Such coincidences are abundant and can occur in different Dynkin types, and in different Dynkin families. By the Lusztig-Kato theorem, the main theorem gives a metric analogue, in the spherical setting, of the combinatorial invariance conjecture for Kazhdan-Lusztig polynomials.

Under the conditional framework breaking the longstanding O(n log n) integer multiplication barrier (originating from OpenAI Preprint #109), the asymptotic time complexity exponent T(n) = O(n (log n)^{1-\kappa}) is governed by bounding the second moment E[X^2] < 1 of recursive branching processes over trilinear tensor carrier graphs. In this work, we present a constructive combinatorial optimization over the alternating carrier bipartite matching graphs of the Schönhage trilinear tensor decomposition at dimensions h=23 and h=25. Through an alternating augmenting path search, we uncover a non-trivial cluster-unlocking cascade that eliminates 185 carrier roles (95 roles in h=23 and 90 roles in h=25), reducing the global physical wire width by 377,890 wires from the reviewed baseline W = 177,284,805 down to W = 176,906,915. Evaluated over the exact 10^{-14} rational grid, this wire reduction certifies an improved second-moment coefficient AB = 5,164,059 / 125,000,000,000 and establishes the sharpened conditional exponent \kappa = 826,215,307 / 20,000,000,000,000 \approx 4.131076535 \times 10^{-5}, strictly surpassing the preceding record on this architecture (\kappa \approx 4.123864 \times 10^{-5}). All 47 polynomial constraints and 7 rational security margins are audited in exact Q-arithmetic with zero floating-point error, and the fundamental wire reduction identity is formally verified in the Lean 4 interactive theorem prover without unproven axioms.

Self-assembled monolayers (SAMs), formed by the adsorption of a monomolecular layer of adsorbate onto a surface, have emerged as leading candidates for plat- forms for electrochemical biosensors. In order to characterize the working age of a SAM-based biosensor, it is necessary to understand the long-term degradation of the monolayer, with particular emphasis on the intermolecular forces present in the self-assembly process. In this work, discrete- and continuous-time proba- bilistic cellular automaton (PCA) models for the degradation of SAMs involving adsorbate-adsorbate interactions are proposed in which adsorbate molecules desorb at a rate dependent only on the number of adsorbed neighbors. Impor- tantly, we make no assumptions on the relationship between degradation rate and adsorbed neighbors. Using techniques from generating function theory and complex analysis, the expected degradation curve is solved for explicitly in one dimension and shown to be a sigmoid curve related to the Gompertz function.

By the Strong Perfect Graph Theorem, every graph whose chromatic number exceeds its clique number contains an odd hole or an odd antihole. We investigate the structure of odd antiholes in critical graphs with fixed maximum degree. We prove that if $G$ is a $k$-critical graph with maximum degree $\Delta$ then every odd antihole in $G$ has length at most $2(\Delta-k)+7$, and conjecture that, in the odd-hole-free setting, equality forces the graph itself to be the corresponding odd antihole. We verify this extremal characterization when $\Delta\geq 2k-5$, extending recent results for $\Delta=k$, and construct $k$-critical odd-hole-free graphs showing that the next possible odd antihole length $2(\Delta-k)+5$ below the extremal bound can occur. Our proofs use a list-coloring theorem for graphs on $2\ell-1$ vertices whose complements are hypomatchable. This motivates the conjecture that every odd antihole $\overline{C_{2\ell-1}}$ is strongly $\ell$-chromatic-choosable; we show that this conjecture would imply the full extremal characterization. We also obtain degree and attachment restrictions for odd antiholes in critical graphs.