Papers

Eternal domination is a process in which a set of guards occupying a dominating set on a graph protects against an infinite sequence of attacks. After a vertex is attacked, one guard must move along an edge to the attacked vertex and each of the remaining guards may move along an edge so that the guards again occupy a dominating set on the graph and can defend the next attack. The minimum number of guards needed in a graph $\Gamma$ is the eternal domination number, denoted by $\gamma_{\mathrm{all}}^\infty(\Gamma)$. In this paper, we show that the eternal domination number of a vertex-transitive graph with an efficient dominating set is equal to its domination number. We show that a Cayley graph on a generalized dihedral group whose connection set contains few or many reflections is efficiently dominated. Then, we provide an infinite family of connected Cayley graphs for which $\gamma_{\mathrm{all}}^{\infty}(\Gamma) = \gamma(\Gamma)+1$, generalizing a result of [Braga et al., J. Combin. Math. Combin. Comput. 96 (2016), 13–22]. Finally, we build an infinite family of connected Cayley graphs with $\gamma_{\mathrm{all}}^\infty(\Gamma) \geq \gamma(\Gamma)+2$.

In the binary trust-gossip dynamics, $n$ agents each hold a directed binary opinion, trust or distrust, of every other agent, and a gossip step lets one agent copy another agent's opinion of a third whenever the copier trusts the source. We prove that under any fair schedule of such steps, every trajectory reaches an absorbing state in finitely many steps, one in which no gossip step changes any opinion; in particular, there are no limit cycles. The proof is constructive and rests on a single descent measure: the number of ordered pairs of distinct agents linked by a chain of trust. Trust-adding gossip leaves this count unchanged and trust-removing gossip can only lower it, so it never rises, and it is zero only at the all-distrust state. From any non-absorbing state we exhibit a finite run of steps that reaches an absorbing state or strictly lowers the count; since the count is a non-negative integer at most $n(n-1)$, the process halts at an absorbing state.

Ample sets of hypercubes, introduced by A. Dress in 1995, constitute a combinatorial structure with rich properties and important examples. Ample sets can be characterized in a multitude of combinatorial, graph-theoretical, recursive, and geometrical ways, and they are equivalent to lopsided sets introduced by J. Lawrence in 1983. In this paper, we define and investigate ample sets of Cartesian products $U=U_1\times\cdots\times U_m$. This is done using minor-subproducts of $U$, which correspond to products of partitions of factors: each minor-subproduct is obtained by partitioning each $U_i$ into blocks and contracting blocks into singletons. For a minor-subproduct $M$ and a set $S$, we define the notions of shattering of $M$ by $S$, of copy of $M$ in $S$, of projection $S_M$ of $S$ on $M$, and of strong-projection $S^M$ of $S$ on $M$. We call a set $S$ ample if for any minor-subproduct $M$ that is shattered by $S$, there exists a copy of $M$ included in $S$. We prove that several characterizations of ample sets can be extended to ample sets of Cartesian products. In particular, we show that ampleness of $S$ is equivalent to the ampleness of the complement $S^*$, to superisometricity (isometricity of $S^M$ for any minor-subproduct $M$), and commutativity $(S^M)_{M'}=(S_{M'})^M$ for all minor-subproducts $M,M'$ with disjoint supports. We also provide more efficient characterizations of ampleness, in particular, by showing that $S$ is ample iff S is isometric and both $S_e$ and $S^e$ are ample for some elementary minor-subproduct, iff the intersection of S with any interval [u,v] with u,v in S is ample in the classical sense. We characterize ampleness by push downs and provide a decomposition theorem, allowing us to prove that their prism complexes are contractible. We provide new examples of ample sets arising from payoff games, prism-like polyhedra, and quasi-median graphs.

Russell recently introduced a family of three-colored partitions in analogy with earlier work by Alladi and Gordon. He showed that their enumerations are surprisingly connected to the classic Rogers-Ramanujan identities. Using the method of linked partition ideals, we elaborate on Russell's results by further counting each part color. Unlike Russell's proofs, our arguments do not require any use of computer algebra systems. With these multivariate generating function relations, we are led to confirm a conjecture of Russell. Furthermore, our results offer a combinatorial understanding of a new triple Rogers-Ramanujan type identity.

We derive the equality between one-dimensional sums associated with tensor products of Kirillov-Reshetikhin column crystals of classical affine types and Lusztig q-analogues of weight multiplicities. The matching of the corresponding root systems is suggested by Howe duality. Our main tool is the dual Cauchy formula for Koornwinder polynomials due to Mimachi, which we combine with specializations in these polynomials. The mentioned dualities are proved for one-dimensional sums of all (twisted and untwisted) classical affine types except types B_n^(1) and D_n^(1). On another hand, all the Lusztig q-analogues of classical type are covered by our dualities, but they may have different parameters depending on the length of the roots in the underlying root system.

We study skew double-shifted plane partitions with three-element profiles using MacMahon's partition analysis. We present new generating function formulas for these partitions, incorporating an extra bound on the number of non-zero diagonal elements. These objects are closely related to the Göllnitz-Gordon and little Göllnitz identities. Moreover, we investigate some infinite hierarchies of $q$-series identities that stem from our formulas. We also observe certain palindromic properties within these generating functions. Finally, we examine these same objects from the perspective of linear partitions, which leads to interesting new $q$-series identities.

We develop a finite-field stratification for characteristic polynomials of deletion subarrangements of the full $m$-Catalan arrangement. It reduces the count to cyclic placements of rigid blocks and yields falling-factorial expansions for deletions indexed by graphs, digraphs, and gain-labeled digraphs. The coefficients are graphical Stirling numbers for zero-layer deletions, directed matching numbers when the deleted layer $\ell$ satisfies $1\le \ell\le\lfloor m/2\rfloor$, directed path-cover numbers when $\lfloor m/2\rfloor<\ell\le m$, and admissible gain-labeled arc sets for multilayer deletions. For $\ell=m$, a complementary path-cover expansion yields factorization consequences. The method also gives formulas for directed Ish-type arrangements in terms of path-cycle covers and outdegrees.

An edge of a graph dominates itself and each edge adjacent to it. A perfect edge dominating set is a subset of edges such that each edge outside the subset is dominated by exactly one edge of the subset. In this article, we characterize the extremal graphs on $n$ vertices in the classes of trees, forests, and chordal graphs with respect to the number of perfect edge dominating sets. Moreover, we derive linear-time algorithms for counting perfect edge dominating sets and for counting dominating induced matchings in generalized series-parallel graphs and chordal graphs.

For graphs $F$ and $H$, let $\ex(n,F,H)$ denote the maximum number of copies of $F$ in an $n$-vertex $H$-free graph. Gerbner, Győri, Methuku and Vizer proved that $\ex(n,C_6,C_8)=\Theta(n^3)$ and predicted that the unrestricted problem should have the same first-order asymptotics as the bipartite one. We determine the exact value for all sufficiently large $n$, showing that \[ \ex(n,C_6,C_8)=6\binom{n-3}{3}+12(n-5). \] Moreover, the unique extremal graph is $K_3\vee (K_2\cup I_{n-5})$. The main new ingredient is a codegree decomposition for $C_8$-free graphs: a packing lemma for triangles in the linear-codegree graph recovers an almost spanning common neighborhood, and a defect-absorption argument upgrades this stability to the exact extremal graph.

For positive integers \(m,n\), the partial permutohedron $\mathcal{P}(m,n)$ is a lattice polytope constructed as the convex hull of vectors in $\{0, 1, \dots, n\}^m$ that have distinct non-zero entries. We prove that for $n \ge m-1$, the Ehrhart polynomial of $\mathcal{P}(m,n)$ is magic positive except for the single case \((m,n)=(2,1)\). In particular, the Ehrhart polynomial of the parking function polytope (integrally equivalent to $\mathcal{P}(m,m-1)$) is magic positive for $m \ge 3$. For $n<m-1$, we discuss the magic positivity of the Ehrhart polynomial of $\mathcal{P}(m,n)$ for $n=1,2,3$. There exist infinitely many counterexamples with $n<m-1$ showing that the Ehrhart polynomial of $\mathcal{P}(m,n)$ is not magic positive. This partially resolves an open problem proposed by Ferroni and Higashitani.

Let $\pi=(<_D,<_A)$ be a pair of distinct orders on a $k$-letter alphabet $A. $ The periodic trajectories $v_i^\infty $ of a discrete $k$-interval exchange transformations $T$ with permutation $\pi$ are characterized by the following order symmetry : $v_i^\omega <_D v_j^\omega$ (lexicographically) if and only if $v_i^{-\omega}<_Av_j^{-\omega}$ (reverse lexicographically). For general words $u$ and $v$ over $A$, the orders need not agree in which case either $u^\omega<_A v^\omega<_D u^\omega$ (Type 1) or $v^\omega<_A u^\omega<_D v^\omega$ (Type 2). We partition all such order crossings amongst the set of conjugates of two words $u$ and $v$ into disjoint families $T_1(u,v)$ and $T_2(u,v)$ and define the index $i(u,v)$ by $|T_1(u,v)|+|T_2(u,v)|.$ Remarkably the difference, $|T_2(u,v)|-|T_1(u,v)|,$ depends only on the Parikh vectors $\lambda(u)$ and $\lambda(v).$ We show that $|T_2(u,v)|-|T_1(u,v)|=\lambda(u)^T \Omega \lambda(v)$ where $\Omega$ is a $k\times k$ skew symmetric matrix depending only on $\pi.$ It follows that the Parikh vectors of the trajectories of a discrete interval exchange are orthogonal with respect to $\Omega.$ Applied to dimension $3,$ we obtain an arithmetic formula for the number of orbits in a discrete $3$-interval exchange and hence a characterization of minimality. For general $k,$ the orthogonality of the trajectories gives an upper bound $\lfloor \frac{k+d}2 \rfloor$ on the number of distinct trajectories where $d=\dim \ker (\Omega).$ If $T$ is symmetric, then the number of distinct trajectories is at most$\lfloor \frac{k+1}2 \rfloor.$ An alternate interpretation of this result is that on an ordered $k$-letter alphabet, there are at most $\lfloor \frac{k+1}2 \rfloor$ primitive, pairwise non conjugate perfectly clustering words which perfectly cluster collectively in a single array in which all their conjugates are arranged in increasing order.

We show that the submonoids of the tied-symmetric monoid containing the symmetric group form a distributive lattice. Furthermore, we determine a minimal generating set for any such submonoid.

For a graph $G,$ let $\alpha(G)$ denote its second smallest Laplacian eigenvalue. The Laplacian Spread Conjecture is that $\alpha(G)+\alpha(\overline{G}) \geq 1,$ where $\overline{G}$ is the complement of $G.$ In this article, we provide a new proof of the Laplacian spread conjecture by means of linear algebra, which is more concise.

We present a short "proof from the Book" that $321$-avoiding permutations without double deficiencies are counted by the Motzkin numbers. Although this result was first proved by Rubey and Stump, our proof gives a much simpler and more transparent description of the same bijection.

Any Pythagorean triple $\{a,b,c\}$ such that $a^{2}+b^{2}=c^{2}$ satisfies an elegant relation between its partitions into three parts, namely $p(a,3)+p(b,3)=p(c,3)$. While this property follows from elementary analytic methods, we give the first combinatorial proof of this relation.

We derive new exact formulae for elliptic genera in two spacetime dimensions with $\mathcal{N}\ge 2$ supercharges, as well as their one- and zero-dimensional counterparts (for Witten indices and matrix-model partition functions). Our results are written as a discrete sum over geometric/combinatorial structures of crystals introduced previously by the authors. The contribution from each crystal may be expressed in terms of the boundary data of a finite substructure of the crystal called the molecules. Our results provide vast generalisations of the celebrated Nekrasov partition function enumerated by the Young diagrams, and uncover new combinatorics underlying the crystal melting. We also analyse the thermodynamic limit of crystals arising from two-dimensional $\mathcal{N}=(0,2)$ theories associated with toric Calabi-Yau fourfolds, where a projection of the Calabi-Yau geometry emerges in the limit.

We study the disjoint separators problem in graphs, an analogue of the famous disjoint paths problem. Given a graph $G$ and four pairwise disjoint subsets of vertices $S_r$, $T_r$, $S_b$, $T_b$, we ask whether there exist an $(S_r,T_r)$-separator and an $(S_b,T_b)$-separator which are disjoint. This is equivalent to coloring the vertices in red or blue, with $S_r \cup T_r$ in red and $S_b \cup T_b$ in blue, such that there is no red $(S_r,T_r)$-path and no blue $(S_b,T_b)$-path. On the one hand, we show that the disjoint separators problem is NP-complete. We actually exhibit several NP-complete restrictions of this problem, including planar graphs of bounded maximum degree, and graphs of bounded maximum degree when $|S_r|=|T_r|=|S_b|=|T_b|=1$. On the other hand, these hardness results turn out to be quite tight, as we provide a structural characterization and a polynomial-time algorithm for planar graphs when $|S_r|=|T_r|=|S_b|=|T_b|=1$. This has an interesting consequence about the popular board game Hex: for the generalized game that may be played on any board, our result characterizes the planar boards on which draws are impossible, thus extending the well-known result about impossibility of draws on the standard commercialized board.

In 1997, Alon and Kim conjectured that if $H$ is a $k$-uniform $t$-simple hypergraph with maximum degree $D$ sufficiently large, then the chromatic index $\chi'(H)$ is upper bounded by $(t-1+1/t+\varepsilon)D$. Using probabilistic techniques and a nibble coloring method, we prove a general coloring theorem stating that a $k$-uniform $t$-simple hypergraph $H$ with large maximum degree $D$ satisfies $$\chi'(H) \le (b+\varepsilon)kD,$$ where $b$ is a particular parameter derived from local structural information about $H$. We use structural techniques to prove sharp upper bounds on $b$ in the 3-uniform 2-simple, and 3-uniform 3-simple cases. In particular, we deduce as a corollary that for sufficiently large $D$, every 3-uniform 2-simple and 3-simple hypergraph of maximum degree at most $D$ has chromatic index at most $2.3581D$ and $2.6791D$, respectively.

We show that the standard Veronese degree of the defining ideal $I_{n,h}$ of a monomial star configuration is $\lcm(1,2,\ldots,h)$, proving a conjecture by Grifo and Seceleanu. We also provide a counter-example for their question regarding upper bounds for the standard Veronese degree of monomial ideals.

The connections between graph theory, and more generally association schemes, and coding theory were established by Delsarte for the Hamming metric and rank-metric codes. The ambient metric space of Hamming-metric codes and rank-metric codes can be seen as Cayley graphs generated by words of weight one. The metrics considered then coincide with the geodesic distances of these distance-regular graphs. We focus on a generalisation of this framework to the space of tensors over a finite field, endowed with the tensor-rank as a metric. This space corresponds to the Cayley graph generated by rank-one tensors, which is not distance-regular for tensors of order at least 3. We show that the spectrum of this graph has a recursive expression and depends on the possible intersections between tensor subspaces of large enough dimension and the Segre variety. The spectrum of this graph for 3-order tensors can be expressed with the rank distribution of the rank-metric codes generated by these tensors. In particular, we obtain the complete spectrum of the graph for 2x3x3 tensors over any finite field. We apply this result to derive bounds on the dimension of tensor codes in the tensor-rank metric using the eigenvalue method, and in particular the ratio-type bound.

We show that the existence of an oddomorphism from a graph $F$ to a graph $G$ does not imply that $G$ is a minor of $F$. This answers a question posed by Roberson (2022) and shows that the CFI graphs cannot be used to prove the Strong Roberson Conjecture. Additionally, we introduce the concept of a split-off minor and show that the existence of an oddomorphism from $F$ to $G$ implies that $G$ is a split-off minor of $F$. Consequently, every class that is closed under taking split-off minors and disjoint unions is homomorphism distinguishing closed. The split-off minor relation is the first minor-like structural relation shown to have this property, marking a meaningful advancement in our understanding of the interaction between structural graph containment and homomorphism indistinguishability relations.

The Laplacian conjecture of Brouwer asserts that for any graph \(G\) of order n with \(m\) edges, the sum of the \(k\) largest Laplacian eigenvalues satisfies \(s_k(G) \le m + \binom{k+1}{2}\) for $k=1, \ldots, n$. Later, Li and Guo in 2022 further proposed the full Brouwer's Laplacian spectrum conjecture. Recently, Kothari and Tudose in 2026 proved the Brouwer's conjecture. Motivated by their perfect proof and methods, we proved that for a simple graph of order $n$ with $m$ edges and $1\le k\le n-1$, \(s_k(G) = m + \binom{k+1}{2}\) if and only if $G$ is a threshold graph with clique number \(k+1\), which confirms the full Brouwer conjecture proposed by Li and Guo.

The Elekes-Szabó theorem establishes that an irreducible algebraic hypersurface $Z(F)$ contains few grid points unless it exhibits a specific group-related structure. Identifying this structure from the polynomial $F$ is a challenging problem in combinatorial geometry. Our first main result (Theorem 2.3) provides a local geometric criterion to detect such group-related hypersurfaces. By applying this criterion, we develop a geometric framework for boundary varieties, which are defined by the vanishing of partial derivatives along $Z(F)$. In Theorem 2.4, we show that for group-related varieties, these boundary varieties must be contained in coordinate slices. This gives a strict geometric constraint on the loci where $Z(F)$ becomes tangent to coordinate directions. As an application, we study configurations formed by $d$ coordinate-grid hyperplane families together with a one-parameter polynomial family of hyperspheres in $\mathbb{R}^d$. If one chooses $n$ members from each of these $d+1$ families and obtains $\Omega(n^{d-\eta})$ common incidence points, then the hypersphere family is forced to have a very restricted form: it is concentric in dimensions $d \geq 3$, and in dimension $2$ it is either concentric or consists of fixed-radius circles whose centres lie on a line parallel to a coordinate axis. We also generalize the pinned distance problem initiated by Elekes and Szabó for three points in the plane to $d+1$ points in $\mathbb{R}^d$. More precisely, in Theorem 2.8 we prove that if $d+1$ families of hyperspheres centred at fixed points determine $\Omega(n^{d-\eta})$ points, each lying on one hypersphere from each family, then the centres must be affinely dependent.

We develop a new approach to cross-intersection problems in extremal set theory. The method builds on the iterative procedure introduced by Kupavskii and Zakharov (2024) and the $t$-cover method. It provides a flexible framework for deriving extremal and stability results for cross $t$-intersecting families. Our approach applies to a variety of combinatorial objects. As an application, we prove a product version of the seminal Erdős–Ko–Rado theorem for sufficiently spread set systems. Two families $\mathcal{F}$ and $\mathcal{G}$ of $k$-subsets of $[n]$ are called cross $t$-intersecting if $|F\cap G|\geq t$ for all $F\in\mathcal{F}$ and $G\in\mathcal{G}$. We determine the families maximizing $\min\{|\mathcal{F}|, |\mathcal{G}|\}$ for large $n$ and all $t\ge2$, generalizing results of Mörs (1985) and Füredi (1995) for cross $1$-intersecting families. We then determine the families maximizing $|\mathcal{F}||\mathcal{G}|$ under the condition $\max\{|\cap_{F\in\mathcal{F}}F|,|\cap_{G\in\mathcal{G}}G|\}<t$ for large $n$. This improves the bound obtained by Frankl and Wang (2024), and provides a characterization of extremal configurations. For a family $\mathcal{F}$ of subsets of $[n]$, we introduce its $t$-diversity $\gamma_t(\mathcal{F})$, defined as the minimum number of sets from $\mathcal{F}$ not containing a fixed $t$-subset. This serves as a natural generalization of the important notion of diversity for $t=1$. We obtain a stability result via $\gamma_t$, and determine the maximum of $\min\{\gamma_t(\mathcal{F}),\gamma_t(\mathcal{G})\}$ for cross $t$-intersecting families $\mathcal{F}$ and $\mathcal{G}$. These yield new results for $t$-intersecting families, including a stability theorem towards a conjecture of Ellis, Keller and Lifshitz (2019), which may also be regarded as a $t$-intersection version, for large $n$, of an influential theorem of Frankl (1987).

There has been recent interest in integer partitions whose parts satisfy parity restrictions: for example, those where all the odd parts are distinct, or those where all the even parts are larger than the odd parts. Often results about such partitions have been obtained by algebraic manipulation of generating functions. We show that a number of these identities can be proved in a bijective, and sometimes simpler, manner.

We study the cohomology of regular semisimple Hessenberg varieties associated with lollipop graphs as a module under the dot action. Using the natural basis introduced by Cho, Hong, and Lee, which we call the CHL basis, we establish structural properties of the dot action, including a result for classes satisfying \(i\)-decomposability. We also obtain an explicit elementary symmetric function expansion of the chromatic quasisymmetric functions of lollipop graphs in terms of \(h\)-admissible permutations and their associated partitions. Combining these geometric and combinatorial results, we construct a permutation module decomposition of the cohomology of the corresponding Hessenberg varieties, thereby proving a conjecture of Cho, Hong, and Lee for lollipop graphs.

In 1967, Gerencser and Gyárfás determined the exact values of the two-colour Ramsey numbers of paths. In a footnote, they made the following observation: Every $2$-edge-coloured complete graph contains a Hamilton path with at most one colour change. Later, this led to a challenging and still wide open conjecture about covering edge-coloured complete graphs with monochromatic paths. Inspired by the original statement, we study paths and cycles with few colour changes in $3$-edge-coloured complete graphs. For this, we introduce a new Ramsey-type parameter: For $q,k \in \mathbb{N}$ and a graph $G$, let $R_q^k(G)$ denote the smallest $N \in \mathbb{N}$ such that every $q$-edge-coloured complete graph on $N$ vertices contains a copy of $G$ with at most $k$ vertices that are incident to edges in $G$ of different colours. For paths, we show that $R_3^1(P_n) = \frac{3n}{2} + O(1)$, and for even cycles, we show that $R_3^2(C_n) = \frac{3n}{2} + o(n)$.

We present a new quadratic model for the certification problem in adversarial robustness, which simultaneously accounts for all possible target classes. Building on this model, we propose a novel semidefinite programming (SDP) relaxation for incomplete verification. A key advantage of our approach is that it certifies robustness in a single optimization, avoiding the need for a separate resolution per class. This yields a significant computational speed-up and enables scalability to large datasets with many classes. To further improve efficiency, we also propose an effective pruning strategy of active neurons, thus reducing the problem dimensionality and accelerating convergence.

We introduce a polyhedral realizability problem for complete bipartite preference structures, the two-sided strict preference profiles that underlie the stable marriage problem. Given two parts M and W of size k, a strong polyhedral realization asks for a bipartite polyhedral graph with bipartition classes of size k in which every vertex is adjacent to all but one vertex on the opposite side. This condition attempts to represent complete opposite-side preference capacity by direct polyhedral adjacency, with one geometrically exceptional opposite-side vertex for each agent. We prove an Euler-type criticality theorem: such a strong polyhedral realization exists if and only if k=4, and in that case the underlying graph is the cube graph Q_3, equivalently K_{4,4} minus a perfect matching. The proof is the collision of the strong edge requirement E=k(k-1) with the bipartite planar bound E<=4k-4 and the minimum-degree constraint for polyhedral graphs. We then distinguish weak realizations. A family of (k-1)-gonal trapezohedra gives balanced bipartite polyhedral graphs with 2k vertices and 4k-4 edges for all k>=4, showing that weak maximal realizability persists beyond the cubic critical case. However, the Euler interval 3k<=E<=4k-4 is not fully realizable: we give a direct proof that no bipartite polyhedral graph exists with V=10 and E=15, equivalently that there is no even triangulation of the sphere on seven vertices. Finally, in the cube case, we show that cube-distance compatibility of a size-four preference profile is equivalent to the existence of a perfect matching of mutually last-ranked pairs. This gives a first preference-theoretic manifestation of the cubic criticality.

We prove a multivariate Lam–Postnikov–Pylyavskyy type inequality for hybrid Grothendieck polynomials, unifying and refining results for stable and dual stable Grothendieck polynomials established by Chan–Chen–Pak–Soskin. We also conjecture extensions of the Lam–Postnikov–Pylyavskyy inequality and a conjecture by Thomas–Yong to the (equivariant) Schubert and Grothendieck polynomial setting.