Papers

In 1992, Pukhlikov and Khovanskii provided a description of the cohomology ring of toric variety as a quotient of the ring of differential operators on spaces of virtual polytopes. Later Kaveh generalized this construction to the case of cohomology rings for full flag varieties. In this paper we extend Pukhlikov-Khovanskii type presentation to the case of K-theory of toric and flag varieties. First, we study the Frobenius algebras obtained as quotients of the group algebra of free abelian group (possibly of infinite rank). Then we apply this construction to define a K-ring associated to a linear family of (virtual) polytopes. We study in detail two examples of such families: the family of integer (virtual) polytopes with a fixed normal fan and the family of (virtual) Gelfand-Zetlin polytopes. We show that the K-theory of toric and flag varieties can be realized as K-rings of the above families and use this to get natural set of relations in the above K-rings. Further, we describe the classes of structure sheaves of toric orbit closures and Schubert varieties in type A flag varieties. Finally, we show that our results also hold true in T-equivariant setting.

We improve the known upper bound for the extremal number of Berge-$C_4$-free $3$-uniform hypergraphs. More precisely, we prove that every $n$-vertex $3$-uniform hypergraph with no Berge cycle of length four has at most \[ \frac{n^{3/2}}{2+\sqrt2}+O(n) \] hyperedges. This improves the previous best-known leading constant $1/\sqrt{10}$ to $1/(2+\sqrt2)$.

This paper provides a (Laurent) polynomial reduction to $q$-holonomic sequences $F_k(q)$. We first characterize Laurent polynomials $\tilde{p}(x)$ such that the product $\tilde{p}(q^k)F_k(q)$ is summable. Then the reduction framework is given to decompose any given Laurent polynomial into a summable part and a remainder with lower degree. Finally, we introduce a power-partible reduction for $q$-holonomic sequences of which the recurrence relation satisfies a certain symmetry condition. The advantage is that it can not only simultaneously eliminate the highest-degree and lowest-degree terms of a Laurent polynomial satisfying a symmetry condition, but also guarantee the symmetry of the remainder. As applications, we apply the reduction to $q$-central-Delannoy numbers to derive new $q$-identities and $q$-congruences.

The present work develops the results of the series of papers by Buchstaber and Terzić on the standard actions of the compact torus $T^n = (S^1)^n$ on the complex Grassmann manifolds $G_{n,2}$. In those works, a hyperplane arrangement in $\mathbb{R}^n$ was introduced that determines the chamber decomposition of the hypersimplex $\Delta_{n,2}$ for the $T^n$-action on $G_{n,2}$. We introduce a notion of admissible graph for the standard action of the torus $T^n$ on the complex Grassmannian $G_{n,2}$. In terms of admissible graphs, we give a complete inductive description (with respect to $n \ge 4$) of the admissible polytopes in $\Delta_{n,2}$, as well as of the toric varieties arising as closures of $(\mathbb{C}^*)^n$-orbits on $G_{n,2}$ under the standard $(\mathbb{C}^*)^n$-action. We consider the $T^n$-equivariant Plücker embedding $G_{n,2} \hookrightarrow \mathbb{C}P^{N_2}$, where $N_2 = \binom{n}{2}-1$. Using admissible graphs, for the considered $T^n$-actions, we describe hyperplane arrangements in $\mathbb{R}^n$ that determine the chambers in $\Delta_{n,2}$ for the $T^n$-actions on $G_{n,2}$ and $\mathbb{C}P^{N_2}$. Gel'fand, Kapranov, and Zelevinsky introduced the notions of secondary polytopes and secondary fans in connection with the problem of describing triangulations of a given convex polytope, which is closely related to the Newton polytopes of discriminants and resultants. For the $T^n$-action on $\mathbb{C}P^{N_2}$, we show that the cones in $\mathbb{R}^n$ with vertex at the origin spanned by the chambers form the secondary fan of the cone spanned by the vertices of $\Delta_{n,2}$.

Nikiforov conjectured that, for every fixed $k\ge2$ and all sufficiently large $n$, the unique $n$-vertex $C_{2k+2}$-free graph with maximum adjacency spectral radius is $S^+_{n,k}$, where $S_{n,k}=K_k\vee\overline K_{n-k}$ and $S^+_{n,k}$ is obtained from $S_{n,k}$ by adding one edge inside the independent part. Cioabă, Desai and Tait proved this conjecture for $n\ge k^{O(k)}$. Later, Li and Ning raised the problem of determining the optimal exponent $\gamma=\gamma(k)$ such that the same conclusion holds for $n\ge \Omega(k^{\gamma(k)})$. We prove a stronger uniform theorem for Nikiforov's matrices $A_\alpha(G)=\alpha D(G)+(1-\alpha)A(G)$. More precisely, for every $\epsilon>0$ there are constants $C_\epsilon$ and $k_\epsilon$ such that for all $0\le\alpha\le1-\epsilon$, $k\ge k_\epsilon$ and $n\ge C_\epsilon k$, every $n$-vertex $C_{2k+2}$-free graph $G$ satisfies $\rho_\alpha(G)\le\rho_\alpha(S^+_{n,k})$, with equality if and only if $G\cong S^+_{n,k}$. In particular, the case $\alpha=0$ answers the problem of Li and Ning, and the $A_\alpha$-spectral even-cycle threshold is linear in $k$, uniformly for all $\alpha$ bounded away from $1$. Our proof introduces a weighted rooted Erdős–Gallai type path lemma, which may be of independent interest in Perron-vector methods for spectral extremal graph problems. The same method also yields asymptotically tight $A_\alpha$-spectral bounds for two local forbidden-subgraph families, namely $(K_1\vee P_\ell)$-free graphs and $F_s$-free graphs, where $F_s$ denotes the friendship graph.

We disprove the visibility conjecture in the plane and prove the sharp upper bound for the almost-sure dimension of visible parts. Precisely, let $K \subset \mathbb{R}^{2}$ be a compact set. For $\sigma \in S^{1}$, let $\mathrm{Vis}_{\sigma}(K) \subset K$ be the visible part of $K$ in direction $\sigma$. We prove that $\operatorname{dim}_{\mathrm{H}} \mathrm{Vis}_{\sigma}(K) \leq \tfrac{3}{2}$ for $\mathcal{H}^{1}$ almost every $\sigma \in S^{1}$. This is sharp: we construct a compact set $K \subset \mathbb{R}^{2}$ such that $\operatorname{dim}_{\mathrm{H}} \mathrm{Vis}_{\sigma}(K)\geq \tfrac{3}{2}$ for all $\sigma \in S^1$.

Zhou et al. (2025) proposed a distance Laplacian analog of Brouwer's conjecture on partial sums of Laplacian eigenvalues, asserting that for any connected graph $G$, $\sum_{i=1}^r \partial_i^L(G)\le W(G)+\binom{r+2}{3},$ where $\partial_i^L(G)$ are the eigenvalues of the distance Laplacian matrix and $W(G)$ is the Wiener index. We prove this inequality for three broad classes of graphs, thereby improving and extending existing results. First, we prove that all connected graphs of diameter at most $D$ satisfy the inequality once the order $n$ satisfies $n\ge\lceil\frac49(D+1)^3\rceil$. Second, we show that the inequality holds for every diameter-$2$ graph with the only exceptions being $K_{1,3}$ at $r=2$ and $K_{1,4}$ at $r=3$. Third, we prove that if the maximum degree is $\Delta(G)=n-k$, then the inequality holds for all $n\ge N(k)$, where $N(2)=10$ and $N(k)=\lceil 5(k-1)^{3/2}\rceil$ for $k\ge 3$. Our proofs rely on decomposing the distance Laplacian matrix into Laplacian matrices of auxiliary graphs whose edges are vertex pairs at distance at least a prescribed value, together with classical eigenvalue inequalities.

Let $d_r(n)$ be the maximum, over all binary phylogenetic trees with $n$ leaves, of the minimum number of $r$-state characters required to define the tree. Semple and Steel proved that $d_r(n)\geq\lceil(n-3)/(r-1)\rceil$, and Bordewich and Semple proved that equality holds for each fixed $r$ and all sufficiently large $n$. We study the corresponding threshold $n_r$, the least $N$ for which equality holds for every $n\geq N$. The Bordewich–Semple construction yields an explicit polynomial upper bound of order $O(r^5)$ for this threshold. We prove the near-linear estimate \[ 3r+1\leq n_r\leq \ceil{64(r-1)\log_2(r+1)}+3\qquad(r\geq4). \] The proof constructs, for every binary phylogenetic tree with $m=n-3$ internal edges, a linked quartet certificate whose conflict graph has maximum degree at most $16\lceil\log_2(m+2)\rceil+4$. Equitable coloring then packs the certificate into exactly $\lceil m/(r-1)\rceil$ $r$-state characters once $m\geq\lceil64(r-1)\log_2(r+1)\rceil$. We also include the lower bound $n_r\geq3r+1$, obtained from the snowflake obstruction, and state the natural conjecture that this lower bound is the exact threshold for all $r\geq4$. The conjectural endpoint is consistent with the known small-state thresholds: $n_4=13$ and $n_5=16$, while the cases $r=2,3$ are also explicitly classified.

We define and study the rectangular finite free heat flow, a dynamical system on polynomials that plays the role of the heat equation in the setting of rectangular finite free probability. We show several equivalent characterizations of the evolution (including PDE and gradient flow formulations), establish basic properties of the dynamics, and determine the asymptotic distributions of the polynomial roots in the long-time and high-degree limits. We also discuss connections with Calogero-Moser systems and Dunkl processes, and we show that the rectangular finite free heat flow describes the mean curvature expansion of a family of compact Lie group orbits.

Let $M$ be a simple connected binary matroid, and let $e$ and $f$ be distinct elements of $M$. It is well known that, when the only circuits containing $e$ are spanning, $M$ is a circuit with at least three elements. This paper proves that if every circuit containing $\{e,f\}$ is spanning, then the canonical tree decomposition of $M$ is a path in which each vertex is labeled by a circuit, a copy of $U_{1,3}$, or a binary spike having one non-tip element deleted.

Motivated by the B-coloring defined by Gyárfás and Sárközy, we introduce a new edge coloring called D-coloring. For a graph $G$, a D-coloring of $G$ is a proper edge coloring such that every diamond subgraph is rainbow. The D-chromatic index of $G$, denoted by $\chi'_D(G)$, is the minimum number of colors needed for a D-coloring of $G$. Denote by $\Delta$ the maximum degree of $G$. We prove that $\chi'_D(G)\le \frac{9}{16}\Delta^2+\frac{1}{2}\Delta$, conjecture that $\chi'_D(G)\le \frac{1}{2}\Delta^2+\frac{1}{2}\Delta$, and verify this conjecture for $\Delta\le 5$.

For a graph G = (V, E) embedded in the Klein bottle, let F(G) denote the set of faces of G. A C_4-face-magic Klein bottle labeling on G is a bijection f: V(G) to {1, 2,..., |V(G)|} such that for any F in F(G) with F isomorphic C_4, the sum of all the vertex labelings along C_4 is a constant. We say that a C_4-face-magic labeling X={x_{i,j} : 0< i,j< 5} on the 4x4 Klein bottle grid graph is horizontally (or vertically) pairwise balanced if x_{2i-1,j} + x_{2i,j}=17 for 0< i <3 and 0< j \le <5 (or x_{i,2j-1} + x_{i2,j}=17 for 0< i <5 and 0< j <3). We show that the 4x4 Klein bottle grid graph has 192 C_4-face-magic labelings up to symmetries on a Klein bottle. We classify these labelings into two categories depending on whether a C_4-face-magic label preserving permutation of the labeling is either horizontally pairwise balanced or vertically pairwise balanced. These results extend known results on C_4-face-magic labelings on an mxn Klein bottle grid graph.

Let $K_{KR}$ be the least constant governing uniform approximation of approximately additive real-valued set functions by finitely additive signed measures. We prove that $$K_{KR}\le\frac{374167}{20000}=18.70835.$$ Starting from a norming functional for best uniform approximation, we form two families of almost extremal sets with complementary point frequencies. Intersections and biregular expanders then give two recombination schemes. The sharper estimate comes from using the schemes on different ranges and from cancelling the positive and negative errors with unequal weights. This improves the previously published bound $38.8$.

We study whether a labeled tree can be recovered from the numbers of larger labeled trees that contract to it. We first characterize containment using the edge splits induced on the surviving vertices after contraction and derive an exact formula for containing trees with one marked display. We then study several displays in the same containing tree simultaneously. After contracting every edge invisible to all \(k\) displays of an \(n\)-vertex target, the remaining collision core has at most \(k(n-1)+1\) vertices. Once the coincidences and relative positions of the surviving labels are recorded, these bounded cores give a finite exact expansion of each collision count. As applications, we prove that almost every sufficiently large labeled tree contains any fixed target, with an exponentially small exceptional proportion. We also obtain an exact avoidance formula and generating function for stars whose center is represented by the largest host label, together with fixed-star asymptotics and a coarse threshold.

Given $R$ a finite commutative ring with identity and $k \in \mathbb{N}$, we consider the $k$-th unitary Cayley graph $G_R(k)=Cay(R,U_{R,k})$ with $U_{R,k} = \{ x^k: x \in R^*\}$, and its symmetrized version $\mathcal{G}_R(k) = Cay(R,T_{R,k})$, with $T_{R,k}=U_{R,k} \cup (-U_{R,k})$. If $R$ is a local ring with maximal ideal $\frak m$, we give the blow-up decompositions for the graphs: namely, we have $G_R(k)= (G_{R/\frak m}(k))^{(|\frak m|)}$ and $\mathcal{G}_R(k)= (\mathcal{G}_{R/\frak m}(k))^{(|\frak m|)}$ for any $k$ such that $(k,|R|)=1$. If the ring $R$ has Artin decomposition $R=R_1 \times \cdots \times R_s$ in local rings $R_i$, we give the Kronecker product decompositions $G_R(k) = G_{R_1}(k) \otimes \cdots \otimes G_{R_s}(k)$ and $\mathcal{G}_R(k) = \mathcal{G}_{R_1}(k) \otimes \cdots \otimes \mathcal{G}_{R_s}(k)$. In further $(k,|R|)=1$, these decompositions can be given in terms of generalized Paley (GP) graphs over finite fields, that is $G_{R_i}(k) = \Gamma(k_i,q_i)$ and similarly for $\mathcal{G}_{R_i}(k)$, for $i=1,\ldots,s$. Also, the reduced graphs correspond to the graphs of the reduced rings, i.e.\@ $\big(G_{R}(k)\big)_{red}\simeq G_{R_{red}}(k)$ and $\big(\mathcal{G}_{R}(k)\big)_{red} \simeq \mathcal{G}_{R_{red}}(k)$. By using these decompositions in terms of GP-graphs, we study some basic structural properties of the graphs such as directedness, bipartiteness and connectedness.

In this paper, the first of a two-part series, we explore 2-cell embeddings of cubic graphs, particularly those with small genus. Using local rotations, we introduce a new way of describing the space of 2-cell embeddings and their mutual relationship for any fixed (cubic) graph. We introduce the unstable dual of an embedding of a cubic graph, a subgraph of the dual graph, and describe how the genus of the corresponding embedding can be recovered from properties of the unstable dual. Finally, we characterize the unstable duals of embeddings with genus at most 2 of cubic cyclically 5-edge connected planar graphs and use these to generate those of genus 3 that have connectivity at most 2.

Gao and Wang proved a strong clopen marker theorem for finite generating sets of $\mathbb Z^n$ under the assumption that each generator has support of size either $1$ or $n$. We show that this support assumption can be removed. The proof is a short conjugacy argument: after a unimodular change of coordinates, any finite set of nonzero lattice vectors can be put in full-support position, allowing one to apply the theorem of Gao and Wang and conjugate the resulting marker set back.

We generalize the Ahlswede–Daykin inequality (1978) to a Schur positive ADS inequality, which also contains the Lam–Postnikov–Pylyavskyy inequality (2007) as a special case. We then present a number of further generalizations and applications. Notably, we resolve Mihalcea's conjecture on log-supermodularity of stable Grothendieck polynomials.

Let $G$ be a compact abelian group whose dual group $\Gamma=\widehat{G}$ has bounded torsion. In 1967, Malliavin-Brameret and Malliavin proved that every Sidon set in $\Gamma$ is a finite union of quasi-independent sets when $\Gamma$ has prime exponent. This was later extended to squarefree exponents in work of Varopoulos and Bourgain. We prove the remaining bounded-torsion case. Consequently, if $\widehat{G}$ has bounded torsion, then a subset $\Lambda\subset \widehat{G}\setminus{0}$ is Sidon if and only if it is a finite union of quasi-independent sets.

This work considers combinatorial and statistical aspects of {\em{shifts of finite type}}, which are families of words over a finite alphabet which avoid a fixed class of {forbidden} sub-words. The overarching question we are interested in is: how do local statistics of a uniformly random element of the shift space depend on combinatorial features of the forbidden set? We focus on the binary alphabet $\{0,1\}$, the class of shift spaces where a single pattern is forbidden, and the average frequency of $1$s (equivalently, the probability of observing $1$ at a given position). In this case, the relevant combinatorial information is encoded by a two-variable auto-correlation polynomial associated to the forbidden word, which we call the {\em{border polynomial}}. We present several results and examples characterizing the ordering of all words by their letter frequencies: for example, we describe the set of patterns which, when forbidden, cause the frequency of $1$s to increase, decrease, or stay exactly $1/2$. Our methodologies include novel explicit local injections and bijections, generating function analysis, and a connection with a probabilistic notion of letter frequency.

We introduce two new relations involving the pentagon and the quadrilateral for the evaluation of the Penrose polynomial at $n=4$ that is proven using a new type of ribbon graph polynomial. Additionally, we extend several relations for the evaluation of the Penrose polynomial at $n=3$ to all $n$.

We explicitly compute the perverse Leray filtration on the top cohomology of the Hilbert scheme of points on $\Sigma\times\mathbb{C}$, for any connected smooth projective curve $\Sigma$. The computation is carried out in the natural basis given by the $\mathbb{C}^*$-upward-flow cycles. The result is described by a simple symmetric-function dictionary: upward-flow classes correspond to products of complete homogeneous symmetric functions, while the perverse-homogeneous basis corresponds to products of power-sum symmetric functions. This gives an explicit triangular change-of-basis between the two bases.

We study maximum matching problems in temporal graphs whose underlying graph is a tree. We consider two temporal models. In a $\Delta$-matching, selected time edges sharing an endpoint must have time ticks differing by at least $\Delta$. In a $\gamma$-matching, the selected objects are blocks of $\gamma$ consecutive appearances of the same underlying edge. We also consider the related ordered static problem of $d$-distance matchings. We show that maximum $\Delta$-matching remains NP-hard on temporal trees for every $\Delta\geq 2$, even in the sparse case where each edge appears at most twice. Using a reduction between the temporal models, we obtain the analogous result for maximum $\gamma$-matching on temporal trees, even when each edge admits at most two $\gamma$-edges. We also show, via a reduction from $d$-distance matching, that maximum $\gamma$-matching is APX-hard even when the underlying graph is bipartite. Complementing these hardness results, we identify several tractable cases. We prove that maximum $\Delta$-matching is polynomial-time solvable on temporal trees in which every edge appears exactly once, and that maximum $\gamma$-matching is polynomial-time solvable when each edge admits at most one $\gamma$-edge. We also give dynamic-programming algorithms under bounded local-use and local-sparsity assumptions, and derive polynomial-time solvability of maximum $d$-distance matching when the input bipartite graph is a tree. Finally, we prove that both maximum $\Delta$-matching and maximum $\gamma$-matching admit polynomial-time approximation schemes on temporal trees.

We construct a periodic weighted graph whose discrete Laplacian has a spectrum with precisely $n$ gaps. Moreover, we show that by an appropriate choice of the weights, the endpoints of these gaps, as well as the upper edge of the spectrum, attain the prescribed values. The underlying graph has a brush-like geometry: it consists of an infinite chain of vertices, each of which is connected to $n$ additional pendant vertices by extra edges. Semi-explicit formulae for the weight coefficients are provided: some of the coefficients are determined explicitly, while others are given as roots of an explicitly determined polynomial.

Order theory is increasingly relevant in applications where data is naturally structured as a partially ordered set (poset), often requiring meaningful notions of distance over posets. In this paper, we introduce a new family of extended metrics on path-connected and fence-connected posets that do not require additional structure. Unlike many existing distances, these metrics are not induced by valuations, but instead arise as a type of shortest-path distance determined by both path length and the number of alternations. For discrete posets, we show that these metrics converge to a type of shortest-fence metric. Our main result establishes that these metrics characterize most discrete path-connected posets up to isomorphism, and up to duality for modular posets. Finally, we prove that this family defines interleaving distances when posets are viewed as thin categories.

We construct an explicit equivariant quantum Satake map for Grassmannians, which enables us to express their torus-equivariant quantum cohomology in terms of that of projective space. We then consider the exterior algebra of the latter, which admits a canonical identification with a Clifford algebra. We describe the resulting action in several complementary ways: first, from a geometric perspective via push-pull maps, and second, in terms of the shuffle product, which also arises in the simplest cohomological Hall algebra associated with the $A_1$-quiver. Exploiting the Clifford algebra structure, we derive new recurrence relations among equivariant Gromov-Witten invariants, yielding a new method for their computation in terms of Wick's Theorem. As an application, we provide combinatorial proofs of Graham positivity for both equivariant quantum Pieri rules, and in one case extend these results to quantum triple Schubert calculus.

A cactus is a graph in which every edge lies on at most one cycle. In 2024, Zhang and Huang generalized this concept to the $k$-cactus, defined as a graph in which every edge lies on at most $k$ cycles. It is known that any cactus on $n$ vertices has at most $\lfloor\frac{3}{2}(n-1)\rfloor$ edges. However, the upper bound on the size of $k$-cacti was known only for $k\le 4$. In this note we consider general $k$. We prove that every $n$-vertex $k$-cactus has $O\!\left(\frac{\log k}{\sqrt{\log\log k}}\,n\right)$ edges for all sufficiently large $k$, and a construction shows this is optimal up to a factor of $\sqrt{\log\log k}$.

In this paper we present a sharp mixed inequality relating successive minima and quotient covering radii of origin-symmetric convex bodies with respect to lattices. The inequality interpolates between the (classical) covering-density lower bound and the lower bound in Minkowski's second theorem.

In 1989, Erdős and Hajnal conjectured that for any graph $H$, there is a constant $c=c(H)>0$ such that every $n$-vertex graph $G$ with no induced copies of $H$ contains a clique or an independent set of size at least $n^{c}$. This conjecture, known as the Erdős-Hajnal conjecture, is a central open problem in combinatorics and listed as one of the top 10 Erdős problems by Bloom on the Erdős problem website https://www.erdosproblems.com/. In a recent breakthrough, Nguyen, Scott and Seymour proved that Erdős-Hajnal conjecture holds for the case when $H$ is the five-vertex path, which, combined with known results, implies that Erdős-Hajnal conjecture holds for every five-vertex graph. In this paper, we extend the iterative sparsification framework recently developed by Nguyen, Scott and Seymour. We introduce a generalized niceness condition relaxing their nice condition, a novel intermediate property concerning combs and a general structural lemma (which may be of independent interest) that is sufficient to deduce the Erdős-Hajnal conjecture. This framework simultaneously recovers the recent result on the five-vertex path (PLMS 2026) and the classical result on the bull graph by Chudnovsky and Safra (JCTB 2008) as special cases, thereby unifying these two previously independent strands, and further proves the conjecture for two new cases: the E-graph (which contains the five-vertex path) and the Bird graph (which contains both the five-vertex path and the bull). These are the first two six-vertex graphs whose validity does not follow from the known operations (see Alon-Pach-Solymosi, Combinatorica 2001, and Nguyen-Scott-Seymour, TAMS 2026) that preserve the Erdős-Hajnal property.

Let $d$ be the smallest positive integer, not divisible by $3$, for which there exists an algebraic number over $\mathbb{Q}$ of degree $d$ whose some three algebraic conjugates sum to zero. Employing the classification of vertex-transitive graphs on 16 vertices of degree 6, we prove that $d\neq 16$. This, combined with results obtained by Dubickas, Smyth and Stong \cite{DubickasSmyth2006}, Dubickas and Jankauskas \cite{DubickasJankauskas2015} and Virbalas \cite{Virbalas2025a}, implies that $d=20$.