Papers

An ILD-set in a connected graph is a subset $S$ of vertices such that it is both independent and locating-dominating. The independent locating-dominating number of a graph G is the minimum cardinality of an ILD-set set of $G$. A well-known fact is that any graph with girth at least 5 has an ILD-set, but that is not clear for graphs with girth 3 and 4. In this work, we prove that there are graphs with no ILD-sets for any order $n\geq 9$ and girth 4, also showing some sufficient conditions for a bipartite graph to contain an ILD-set. Moreover, we focus our attention on trees and on unicyclic graphs, showing that every tree and every unicyclic graph contains ILD-sets, whenever in the latter case, it is twin-free. Finally, a number of bounds, realization theorems and algorithms to find an ILD-set in those families of graphs are provided.

The odd-Ramsey number $r_{\text{odd}}(n,H)$ of a graph $H$ is the minimum number of colors needed to edge-color $K_n$ so that in every copy of $H$ some color occurs an odd number of times, and the unique-Ramsey number $r_{\text{u}}(n,H)$ is the corresponding notion in which some color is required to occur not only an odd number of times but exactly once. In this paper, we address three questions from previous papers. We show $r_{\text{odd}}(n,K_{s,t})> n^{1/\left(\frac s2+\frac 1{2\lfloor t/8 \rfloor}\right)}$ when $s\leq t$ and $s$ is odd and $t$ is even, which is log-asymptotically tight when $s$ is fixed and $t\to\infty$. Next, we consider the odd-Ramsey number when the host graph to be edge-colored is a super-Dirac graph, and show that the smallest minimum degree that forces a non-trivial odd-Ramsey number of Hamilton cycles is $n/2+1$. Finally, we show that $r_\text{u}(n,C_n)> n/4$, which leads to a polynomial gap between $r_\text{odd}(n,C_n)$ and $r_\text{u}(n,C_n)$.

We solve a conjecture by Becker et al. (arXiv:2404.05963) on the topic of zero forcing regarding the number of minimal forts of a tree. They conjectured and we prove $\mathcal{F}_{T_n} \le \binom{n}{2} \mathcal{F}_{P_n}$ where $\mathcal{F}_{T_n}$ is the maximum number of minimal forts on a tree on $n$ vertices and $\mathcal{F}_{P_n}$ is the number of minimal forts of the path graph on $n$ vertices. Our solution relies on both a computational and theoretical approach. Computationally, we introduce and implement an efficient algorithm to compute the exact number of minimal forts for small trees; this is used to establish the large base case required for our strong induction. Theoretically, we provide an adaptation of the recursion relation that defines $\mathcal{F}_{P_n}$ that applies for all forests; this is used in the induction step to establish the result.

Everywhere-$\delta$-dense graphs are defined as graphs on $n$ vertices in which every vertex has degree at least $\delta n$ for some constant $\delta > 0$. Approximation schemes are vital for handling NP-hard optimization problems, but for many graph cut problems, existing PTAS algorithms often suffer from running times of $n^{f(1/\varepsilon)}$. In this paper, we bring PTASs down to EPTASs for several fundamental minimization problems on everywhere-$\Omega(1)$-dense graphs. Specifically, we present the first Efficient Polynomial-Time Approximation Scheme (EPTAS), running in time $f(1/\varepsilon)n^{O(1)}$, for the ConstrainedMinCut problem under a global constraint on vertex weights, a problem that captures BalancedSeparator and SmallSetExpansion. Moreover, we give the first EPTASs for MinQuotientCut and ProductSparsestCut on everywhere-$\delta$-dense graphs with integer-valued dense vertex weights; these problems generalize the four well-known problems UniformSparsestCut, EdgeExpansion, Conductance, and NormalizedCut. Our main technical contribution is an EPTAS for ConstrainedMinCut, based on the weak regularity lemma and sampling and estimation techniques. We then obtain EPTASs for MinQuotientCut and ProductSparsestCut via a unified reduction that invokes this algorithm as a subroutine. In contrast, previous works giving PTASs for these problems on everywhere-$\delta$-dense graphs typically rely on powerful tools such as the Lasserre hierarchy or specific integer programming technique, which we avoid.

The inertia of a graph $G$ is $\operatorname{In}(G)=(n^+(G),n^0(G),n^-(G))$, where $n^+(G),\, n^0(G),\, n^-(G)$ are the numbers of positive, zero and negative eigenvalues of the adjacency matrix of $G$, respectively, counted with multiplicities. Akbari, Elphick, Kumar, Pragada and Tang [Discrete Math. 349 (2026) 114953] conjectured that every graph $G$ satisfies \[ 2n^+(G)\le n^-(G)(n^-(G)+1). \] In this note, we construct a family of reduced graphs $\{W_{k}:\,k\ge5\}$ with \[ \operatorname{In}(W_k) = \left(\binom{k}{2}+1,\ 0,\ k-1\right), \] each of which violates the conjectured inequality. We also observe that deleting the vertex $a_1$ from $W_5$ gives a reduced graph with inertia $(10,0,4)$, answering a question raised in the same paper. The family also refutes a weaker inequality proposed there.

For a given graph $F$, a graph $G$ is said to be $F$-saturated if $G$ contains no copy of $F$ but for any edge $uv\notin E(G)$, $G+uv$ contains a copy of $F$. The saturation number $sat(n,F)$ is defined as the minimum number of edges among all $n$-vertex $F$-saturated graphs. The virus graph $K^s_t$, where $s\geq0$ and $t\geq \max\{3,s\}$, is a graph of order $s+t$ constructed by attaching $s$ distinct leaves to $s$ different vertices of a complete graph $K_t$. Hua and Peng [Discrete Math. 349 (2026) 114674] determined $sat(n,K^2_3)$ and characterized its corresponding extremal graphs. In this paper, we determine $sat(n,K^3_3)$ and $sat(n,K^2_t)$ with $t\geq 4$, together with the structural descriptions of the related extremal saturated graphs.

We resolve a problem of Anderson and Fulton by providing a symmetric and positive product rule for the equivariant cohomology of projective space.

The topological zeta function of a matroid is a rational function as well as a valuative invariant of the matroid, encoding rich combinatorial information. We analyze topological zeta functions of matroids from the vantage point of several matroid operations and operations on lattices of flats. We prove a clean recurrence relation for the Möbius inversion and use it to describe the topological zeta function of the truncation and free extension of a matroid in relation with that of the original matroid. We also characterize the Taylor coefficients of the topological zeta functions for matroids in terms of a matroid invariant, which we call the girth, and generalize an earlier result by Jensen-Kutler-Usatine.

A partition $\Sigma = \{S_1, S_2, \dots, S_k\}$ of the vertex set $V(G)$ is a resolving partition if every pair of distinct vertices in $G$ has a unique representation relative to $\Sigma$. The partition dimension, $pd(G)$, is the minimum cardinality of such a partition. Additionally, a subset $D \subseteq V(G)$ is a $k$-dominating set if every vertex in $V(G) \setminus D$ has at least $k$ neighbors in $D$; the $k$-domination number, $\gamma_k(G)$, denotes the minimum size of such a set. Determining these parameters is NP-complete and particularly challenging for non-distance-regular graphs. This paper consider the Toeplitz graph $T_{2n}(W)$, a family of non-distance-regular graphs. While some resolving parameters for this family have been established, its partition dimension and $k$-domination number remain unknown. We close this gap by computing both parameters for $T_{2n}(W)$.

The two Blanuša snarks $B_1$ and $B_2$ are 3-regular graphs on 18 vertices. Dantas, Lordelo, Niedermaier and Nogueira (Discrete Appl. Math. 361, 2025, pp. 336-346) established the first systematic bounds $23 \le \pi(B_i) \le 34$ for $i=1,2$. Bridi, Marquezino and Figueiredo (arXiv:2505.16050, 2025) then sharpened the upper side to $\pi(B_1) \le 31$ and $\pi(B_2) \le 30$ via a Weight Function Lemma heuristic. We push the upper bounds further to $\pi(B_1) \le 28$ and $\pi(B_2) \le 29$. The route is again Hurlbert's Weight Function Lemma, but applied one automorphism orbit at a time, with optimal weight functions coming from a linear program over a corpus of roughly $30{,}000$ rooted-subtree strategies per target. For the lower bound $\pi(B_i) \ge 23$ we re-derive the witnesses of Dantas et al. and re-verify them with two independent oracles: an exhaustive forward state-space search, and a sound-and-complete MILP encoding whose acyclicity constraint is motivated by the Milans-Clark No-Cycle Lemma. The interval for $B_1$ shrinks from $[23, 31]$ to $[23, 28]$, and for $B_2$ from $[23, 30]$ to $[23, 29]$.

We show the existence of a set $S\subset\mathbb{Z}^2$ avoiding collinear triples satisfying $|S\cap [n]^2|=\Omega(n/\sqrt{\log n})$ for sufficiently large $n$. This improves on the best-known lower bound on Erde's extensible no-three-in-line problem due to Nagy, Nagy and Woodroofe by $\sqrt{\log n}$, leaving the same gap to the trivial upper bound. Our construction is random.

In this paper, the strong and doubly metric dimensions of Johnson and Kneser graphs are considered. The exact value of the strong metric dimension of Johnson graph $J_{n,k}$ is obtained using the well-known results from the literature. The strong metric dimension of Kneser graph $K_{n,k}$ has been obtained for $n \ge 3k-1$. Finally, it has been shown that the doubly metric dimensions of Johnson graph $J_{n,2}$ and Kneser graph $K_{n,2}$ are both $\lceil \frac{2n}{3} \rceil$.

Blow-up in graph theory is a procedure in which each vertex is replaced by copies of itself, and two copies are adjacent if and only if the original vertices are adjacent. In this paper, we extend the concept of graph blow-up to a more general combinatorial context and discuss its potential applications.

Let $d \in \mathbb{N}$, $\delta \in (0, 1/2)$, and $X > 0$. Denote by $N_d(X, \delta)$ the maximum number of points in a subset of the closed Euclidean ball of radius $X$ in $\mathbb{R}^d$ such that every pairwise distance is at least $\delta$ away from any integer. In the planar case, Sárközy proved that for every $\varepsilon > 0$, $N_2(X, \delta) = \Omega_\delta(X^{1/2-\varepsilon})$ as $X \rightarrow \infty$ whenever $\delta$ is sufficiently small in terms of $\varepsilon$, while Konyagin proved the almost matching upper bound $N_2(X,\delta) = O_\delta(X^{1/2})$. We study this problem in higher dimensions, addressing a question of Erdős and Sárközy. Extending Sárközy's construction, we show that for every $\varepsilon > 0$, $N_3(X, \delta) = \Omega_\delta(X^{1-\varepsilon})$ for $\delta$ sufficiently small in terms of $\varepsilon$. We also provide a lifting lemma from integer distance sets to sets avoiding near-integer distances via bilipschitz embeddings of snowflaked Euclidean spaces. This allows us to prove a linear lower bound $N_4(X,\delta) = \Omega_\delta(X)$ for all sufficiently small $\delta$. Finally, adapting Konyagin's approach, we prove the upper bound $N_d(X, \delta) = O_{d, \delta}(X^{d/2})$ for all $d \in \mathbb{N}$.

We show that every proper minor-closed class of graphs admits a $(1+o(1))\log_2 n$-bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $\mathcal{G}$ and every positive integer $n$ there exists an $n^{1+o(1)}$-vertex graph $U$ such that every $n$-vertex graph in $\mathcal{G}$ is isomorphic to an induced subgraph of $U$. Both results are optimal up to the lower order term. They generalize the corresponding results for planar graphs and apex-minor-free classes (Dujmović et al., J.~ACM 2021) to all proper minor-closed classes, answering the open question raised in that paper and anticipated earlier by Bonamy, Gavoille, and Pilipczuk (SODA 2020).

Leap generators have been introduced in [Duchon et al.'04] for exact-size random generation of structures in a class of the form $\mathcal{C}=\mathrm{Seq}(\mathcal{B})$ (sequence construction), in the supercritical case. We extend these generators to supercritical composition schemes $\mathcal{C}=\mathcal{A}\circ\mathcal{B}$. Compared to the sequence construction, the obtained exact-size random generator for $\mathcal{C}$ still has linear time complexity (under conditions on the sampling complexity in $\mathcal{A}$ and $\mathcal{B}$), but perfect uniformity of the distribution is lost in general. However the distribution on $\mathcal{C}_n$, called leap distribution, is asymptotically uniform, the total variation distance from the uniform distribution being $(c+o(1))n^{-1/2}$ for an explicit constant $c$. These generators are simple to implement and can be applied to several classes of walks and trees, in particular Pólya trees. Leap generators can also be given for certain critical composition schemes, those relating planar map families, where this time the total variation distance to the uniform distribution is $\sim c\,n^{-1/3}$ for an explicit constant $c$.

Progress in graph learning is hindered by benchmark practices that conflate the contributions of node features and graph structure, making it hard to tell whether a model actually learns from the graph, or whether it even needs to. We propose measuring this using graph invariants, i.e., permutation-invariant, task-agnostic structural descriptors. Our analysis on datasets substantiates three tacit assumptions in graph learning, namely that (i) a curated subset of invariants is more expressive than standard GNNs, (ii) benchmark datasets exhibit structural heterogeneity even when originating from the same domain, and (iii) simple models are often competitive with, and sometimes exceed, approaches based on transformers or message passing. We thus posit that graph invariants should become a standard tool for measuring graph learning task complexity and the relevance of graph structure.

Integer partitions have fascinated people for centuries, from Ramanujan's groundbreaking congruences to the modern theory of modular forms. This paper investigates the statistical properties of odd unimodal sequences–a natural refinement where sequences rise to a peak and then fall, but with the constraint that all parts must be odd, and develops a comprehensive statistical theory for their rank and shape parameters. We establish the asymptotic distribution of the rank statistic and demonstrate that, when properly normalized, it converges to the hyperbolic secant distribution. Beyond the rank distribution, limiting distributions of the peak, the largest parts on either side of the peak, and the joint behavior of small parts are also proved. These results reveal a rich probabilistic structure that parallels the classical theory of integer partitions while exhibiting distinctive new features arising from the odd-part constraint. The analysis employs a synthesis of modular transformation theory, false theta function asymptotics, and conditioned Boltzmann models. This extends the probabilistic machinery previously developed for unimodal sequences into a more general and analytically demanding setting, offering a unified approach that bridges modular forms and probability.

For integers $n\ge s\ge2$, let $e(n,s)$ be the maximum size of a family $\mathcal F\subseteq2^{[n]}$ with no $s$ pairwise disjoint members. The study of determining $e(n,s)$ is closely related to its uniform counterpart, the well-known Erdős matching conjecture. Frankl and Kupavskii conjectured an exact formula for $e((m+1)s-\ell,s)$ when $1\le \ell\le \lceil s/2\rceil$. We prove that for every fixed $m\ge3$ and sufficiently large $s$, the extremal families for $e((m+1)s-\ell,s)$ are $P(m,s,\ell;L)\coloneqq\{A\subseteq [n]\colon |A|+|A\cap L|\ge m+1\}$ for some $L$ with $|L|=\ell-1$ when $1\le \ell\le (\frac{m+1}{2m+1}-o(1))s$. In particular, this confirms the Frankl–Kupavskii conjecture for every fixed $m\ge3$ and all sufficiently large $s$. For $m=3$, we determine the whole range of $\ell$ for which $P(3,s,\ell;L)$ is extremal, generalizing a theorem of Kupavskii and Sokolov.

In 2023, Gollin, Hendrey, Methuku, Tompkins and Zhang determined the maximum number of cliques in general 1-planar graphs with order $n$. Their extremal examples have connectivity at most three, except for a few small orders. At the high-connectivity end, we prove that every $n$-vertex 7-connected 1-planar graph has at most $4n-12$ edges, $4n-16$ triangles, and $n-6$ copies of $K_4$. Hence the total number of cliques is at most $10n-33$. All bounds are sharp for infinitely many values of $n$.

Fix a prime power $q$ and parameters $1\leq t\leq k\leq n$, the corresponding Steiner system in the Grassmann scheme, or the $q$-Steiner system, is a collection $\mathfrak{B}$ of $k$-dimensional subspaces of $\mathbb{F}_{q}^n$ such that for each $t$-dimensional subspace $T$, there exists exactly one element of $\mathfrak{B}$ containing $T$. The dimension of Steiner systems in the Grassmann scheme is defined to be the dimension of the $\mathbb{Q}$-vector space spanned by the characteristic vectors of all these $q$-Steiner systems. In this paper, we prove that when a quadruple $(t,k,n,q)$ admits at least one $q$-Steiner system, the corresponding dimension is equal to ${n\brack k}_{q}-{n\brack t}_{q}+1$. This generalizes the 2019 work of Ghodrati \cite{ghodrati2019dimension} on ordinary Steiner systems.

For any integer $n \geq 2$, let $(m_{1},\ldots,m_{n})$ be a strictly increasing $n$-tuple of positive integers. We show that any subset $A\subset [N]^n$ of density at least $(\log N)^{-c}$ contains a nontrivial configuration of the form \begin{equation*} \boldsymbol{x},\boldsymbol{x}+r^{m_{1}}\boldsymbol{e_{1}},\ldots,\boldsymbol{x}+r^{m_{n}}\boldsymbol{e_{n}}, \end{equation*} where $c=c(n,m_{1},\ldots,m_{n} )$ is a positive constant. This quantitative multidimensional Szemerédi theorem extends a recent two-dimensional result of Peluse, Prendiville, and Shao concerning the configuration of the form $(x,y),(x+r,y),\left(x,y+r^{2}\right)$. The theorem is obtained as a consequence of an effective “popular” version.

A graph $G$ is called $H$-good if $R(G,H)=(|G|-1)(\chi(H)-1)+\sigma(H)$, where $\sigma(H)$ denotes the size of the smallest color class in a $\chi(H)$-coloring of $H$. In Ramsey theory, it is an interesting problem to study whether a graph $G$ is $H$-good or not. In this article, we study the Ramsey goodness of the pair $(K_{2,n},C_m)$, which naturally lies between the classical star-cycle and book-cycle problems. We prove that \begin{equation*} R(K_{2,n},C_{\{m,m+1\}})=m+1. \end{equation*} for all $m\ge 2n+1$, and consequently establish that \begin{equation*} R(K_{2,n},C_{m})=m+1. \end{equation*} for all $m\ge 3n+4$. This proves that $C_m$ is $K_{2,n}$-good in this range and improves a particular case of a result on the Ramsey goodness by Pokrovskiy and Sudakov. Further, we provide a construction of a graph that disproves the $C_{m}$-goodness of $K_{2,n}$ for all even $m$ satisfying $n\geq m+2$.

As the $q$-analog of Chebyshev polynomials, $q$-Hermite polynomials form a cornerstone in the family of $q$-orthogonal polynomials, which play a fundamental role in quantum algebra and mathematical physics. Recently, Andrews obtained a series of Rogers-Ramanujan type identities by constructing Bailey pairs from Chebyshev polynomials. In this paper, by applying the expansion formula of Chebyshev polynomials in terms of $q$-Hermite polynomials and using the orthogonality relations, we derive a series of Rogers-Ramanujan type identities on double sums, which further generalized the known results due to Andrews, Shi, Sun and Yao.

In evolutionary biology, phylogenetic networks are now widely used to represent the historical relationships between species and population, when this history includes reticulation events such as hybridization, gene flow and admixture between populations. Semidirected phylogenetic networks are appropriate models when the direction of some edges and the root position are not identifiable from data. Comparing semidirected networks is important in many applications. For rooted and directed networks, a $\mu$-representation was originally introduced to distinguish tree-child networks, and has since been extended in two different directions: to the larger class of orchard directed networks by adding an extra component that counts paths to reticulations; and to semidirected networks, through an edge-based variant. However, the latter does not provide a distance between semidirected and orchard networks. We introduce here a new edge-based $\mu$-representation capable of distinguishing distinct orchard binary semidirected networks. For this class, we provide a reconstruction algorithm and therefore obtain a true distance that is computable in polynomial time.

The theory of Bailey's transform provides a systematic method for deriving $q$-identities, the key factor of which is the Bailey pair. The concept of Bailey pair was first extended to bilateral version by Paule. In this paper, following Rogers' work on Fourier series, we derive two asymmetric bilateral Bailey pairs. By inserting them into the bilateral Bailey chains, we obtain several identities of Rogers-Ramanujan type, Andrews-Gordon type and also identities on false theta functions. Furthermore, based on the Bailey lattice due to Dousse, Jouhet and Konan, we get an asymmetric bilateral Bailey lemma which leads to identities on Appell-Lerch series. Moreover, by using the asymmetric bilateral Bailey lemmas due to Andrews and Warnaar, we get some identities on false theta functions and the generalized Hecke-type series.

We consider the equal sum partition problem, motivated by distance magic graph labeling: Given $n,k \in \N$ such that $k\, | \sum_{i=1}^ni$ and a partition $p_1+\cdots+p_k=n$, when is it possible to find a partition of the set $\{1,2,\ldots,n\}$ into $k$ subsets of sizes $p_1,\dots,p_k$, such that the element sum in each subset is the same? A known necessary condition is the slack condition, requiring that for all $j$, placing the largest possible elements in the $j$ smallest sets yields a total sum that is at least what is needed. However, this condition is not sufficient, and known counterexamples exist. This work clarifies the boundary between solvable and unsolvable instances of the problem. We extend the list of unsolvable problem instances satisfying the slack condition by exhibiting infinite families where the $n/k$ ratio is any rational number in the interval $(2,\frac{24}{7})$, and a new criterion for unsolvability. Furthermore, we show that the slack condition is natural, as it is both necessary and sufficient for the fractional relaxation of the problem. Based on this result, we prove that the problem is solvable for the class of linear partitions, where $k$ is fixed, $p_1,\ldots,p_k$ grow linearly with $n$, and where the slack condition holds in a strong sense. We do this by applying a randomized rounding algorithm to a solution of the fractional relaxation of the problem and proving that the algorithm has an exponentially small failure probability.

An equivariant characteristic quasi-polynomial is a quasi-polynomial in $q$ consisting of the permutation character on the mod $q$ complement of the corresponding Coxeter arrangement. This concept is a refinement of the conventional characteristic quasi-polynomials of root systems. In this paper, we will show equivariant-theoretic refinements of the some properties of characteristic quasi-polynomials of root systems. Furthermore, we will explicitly compute equivariant characteristic quasi-polynomials of all irreducible reduced root systems and discuss the relationship with root systems constructed by the folding of the extended Dynkin diagrams.

The extended affine Weyl group of a root system is the semidirect product of the corresponding Weyl group by its coweight lattice. The stabilizer subgroup of the extended affine Weyl group with respect to the corresponding fundamental alcove induces a subgroup of automorphisms of the extended Dynkin diagram. In this paper, we construct a finite root system by folding by the elements of the subgroup.

We study the algorithmic tractability of finding large independent sets in dense random hypergraphs. In the sparse regime, much of the natural algorithms can be formulated within either the local or the low-degree polynomial (LDP) framework, and a rich literature has subsequently identified nearly sharp algorithmic thresholds within these classes by exploiting their stability. In the dense setting, however, the algorithmic paradigms are fundamentally different: they are online and thus need not be stable. Perhaps more crucially, even for the classical Erdős-Rényi random graph $G(n,p)$, LDPs are conjectured to fail in the 'easy' regime accessible to online algorithms, thereby challenging their viability for dense models. Our focus is on two models: (i) finding large independent sets in dense $r$-uniform Erdős-Rényi hypergraphs, and (ii) the more challenging problem of finding large $\gamma$-balanced independent sets in dense $r$-uniform $r$-partite hypergraphs, where the $i$-th coordinate of $\gamma\in\mathbb{Q}^r$ specifies the proportion of vertices from $V_i$ in the independent set. For both models, we pinpoint the size of the largest independent set and design online algorithms that achieve a multiplicative approximation factor of $r^{1/(r-1)}$ in the uniform and $(\max_i \gamma_i)^{-1/(r-1)}$ in the $r$-partite model. Furthermore, we establish matching algorithmic lower bounds, showing that these computational gaps are sharp: no online algorithms can breach these gaps.