Papers

The spectral characterization of graphs is a central problem in spectral graph theory. In this paper we study when a tree is determined, among trees, by its generalized spectrum. We use the equivalent formulation given by the adjacency spectrum together with the total-walk sequence $W_k(G)=\mathbf 1^{\mathsf T}A(G)^k\mathbf 1$. We determine the exact matching-number threshold for this tree-level reconstruction problem. If $T$ and $T'$ are trees with matching number at most 4 and have the same adjacency spectrum and the same total-walk sequence, then $T\cong T'$. Moreover, in this range it is enough to require equality of $W_k$ for $3\le k\le8$. The bound is sharp: for every positive integer $m$ we construct a pair of non-isomorphic trees with matching number 5 having the same adjacency spectrum and identical total-walk sequences. The proof of the positive result is based on a finite-core reduction and an algebraic reconstruction of the possible pendant attachments.

A $t$-wise balanced design on the edge set of a complete graph is graphical if its block multiset is invariant under the induced action of the symmetric group on the vertices. Chouinard conjectured that, for each fixed index $\lambda$, there are only finitely many nontrivial simple graphical $t$-wise balanced designs with $t>1$. We prove the conjecture for $t$-designs, which are the $t$-wise balanced designs whose blocks all have the same size. Our theorem does not require simplicity, and we bound all parameters of the designs by explicit polynomials in $\lambda$.

A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle is rainbow. Let $q_B(G)$ be the minimum number of colors in such a coloring. Gyárfás and Sárközy (2023) determine $q_B(G)$ when $G=P_m\square P_n$ is a rectangular grid. In this paper, we completely determine $q_B(G)$ for cylindrical and torus grid graphs $G$. For a torus grid $G=C_m\square C_n$, where $m,n\ge3$ are integers, we prove that $q_B(G)=4=\Delta(G)$ if both $m$ and $n$ are even and $G\not\cong C_4\square C_{4k+2}$ for any integer $k\ge1$, and that $q_B(G)=5=\Delta(G)+1$ if at least one of $m,n$ is odd or $G\cong C_4\square C_{4k+2}$ for some integer $k\ge1$. For a cylindrical grid $G=C_s\square P_m$, $q_B(G)$ also depends on the parity of $s$ and the length of $P_m$. For integers $m\ge2$ and $n\ge2$, we have $q_B(C_{2n}\square P_m)=4$. For integers $m\ge2$ and $n\ge1$, we have $q_B(C_{2n+1}\square P_m)=4$ if $2\le m\le n$, whereas $q_B(C_{2n+1}\square P_m)=5$ if $m\ge n+1$. In higher dimensions, we discuss the B-coloring of discrete torus and $\ell$-cylindrical grid, obtaining some exact results and certain bounds.

We provide an explicit algebraic construction showing that, uniformly for integers $3 \leq s \leq t$, as $t \to \infty$, \[ R( s,t ) \geq t^{(1-o(1)) \log s / \log(\log s + 1) }. \] For large fixed $s$, this improves the dependence on $s$ in the general off-diagonal construction of Alon and Pudlák. In particular, $R(33, t) \geq t^{2.1-o(1)}$, to our knowledge, the first explicit construction showing $R(s, t) \geq t^c$ for some fixed $s$ and some $c > 2$. In the diagonal case, it improves the leading constant in the exponent of the classical Frankl–Wilson bound from $1/4$ to $1$, while being almost as simple to describe.

Chen, Mohar and Wu [J. Combin. Theory Ser. B 161 (2023)] conjectured that every graph of orientable genus $g$ has proper orientation number $O(\sqrt g)$. We prove this conjecture. Our main result extends the potential-outdegree method from independent color classes to three parts of bounded internal degree. Let $k,D\in\mathbb Z_{\ge0}$. If $G$ has maximum average degree at most $2k$ and $V(G)=V_1\cup V_2\cup V_3$, where each $V_i$ induces a subgraph of maximum degree at most $D$, then $$\pchi(G)\le k+9D+6+\floor{\frac32\ceil{\frac{2D+2}{5}}}\le k+\floor{\frac{48D}{5}}+8.$$ When the partition is given, we construct such an orientation in polynomial time. For every $D\ge1$, we also construct a graph with a partition into three parts of internal maximum degree at most $D$ for which $\pchi(G)-\ceil{\mad(G)/2}\ge6D+5$; hence the linear dependence on $D$ is unavoidable. Finally, Woodall's defective-coloring theorem yields $\pchi(G)=O(\sqrt{\gamma+1})$ for every graph of Euler genus $\gamma$.

Let $A$ be a stochastic $n\times n$ matrix with $\operatorname{rank}A\leq k$, where $1\leq k\leq n$. Write $n=qk+s$, where $0\leq s<k$. The author conjectured in 2018 that $\operatorname{per}A\leq (q!/q^q)^{k-s}((q+1)!/(q+1)^{q+1})^s$, with equality if and only if $A=P(J_q^{\oplus(k-s)}\oplus J_{q+1}^{\oplus s})Q$, where $P,Q$ are permutation matrices and $J_t$ is the $t\times t$ matrix with every entry $1/t$. We prove this conjecture in full.

For a tree $T$, let $[T]$ be the set of isomorphism classes of trees that are mutually topological minors of $T$. Bruno and Szeptycki proved that every locally finite tree satisfies $|[T]|\in\{1,2^{\aleph_0}\}$ and that every tree with a ray containing infinitely many vertices of degree at least $3$ has at least $2^{\aleph_0}$ topological twins. Hence equality holds in the latter case when the tree is countable. We treat the complementary countable case, without any bound on the degrees. For every such tree $T$, we prove that $|[T]|\in\{1,\aleph_0,2^{\aleph_0}\}$ and give a well-founded recursive description based on Schmidt rank. The proof uses a finite canonical subtree extracted from the subtree generated by the branching vertices and a counting theorem for countable multisets over a well-quasi-order. The same trichotomy follows for every countable tree and hence for every tree all of whose vertices have countable degree.

We find a bijection to prove that the set of patterns {3412, 4321} is Wilf-equivalent to the set of patterns {3412, 4231, 45321, 54312}. This provides a bijective proof of an identity recently shown by Azam and Richmond.

Among the four well-known anti-foundation axioms, $\mathsf{BAFA}$, $\mathsf{FAFA}$, $\mathsf{SAFA}$, and $\mathsf{AFA}$, the latter three are all special cases of $\mathsf{AFA}^\sim$ ($\sim$ is one of the regular bisimulations). In this paper, we generalize it to $\mathsf{AFA}^\sim$ ($\sim$ is regular and has the so-called set property), and show that this generalization is substantial by constructing new anti-foundation axioms.

A nonnesting permutation of the multiset {1,1,2,2,...,n,n} is a word containing no subsequence abba with a distinct from b. Elizalde and Luo enumerated nonnesting permutations avoiding each set of two or more patterns of length three, and left open the enumeration of those avoiding the single pattern 123 (Problem 1 of their paper). We solve this problem. Writing $c_n$ for the number of nonnesting permutations of {1,1,...,n,n} avoiding 123 and $C(z)=\sum_{n\ge 0}c_nz^n$, we prove $C(z) = 1 + z(1+U)/(2 - z(1+U)(1+V))$, where $V = 1+zV^2$ and $U = 1+3z+zU^2$ are the formal power series branches with constant term 1. In particular $C$ is algebraic of degree exactly 4 over $\mathbb{Q}(z)$, and $c_n \sim \frac{9+6\sqrt{3}}{8\sqrt{\pi}}\, 6^n n^{-3/2}$. The proof constructs a generating tree for these objects whose labels consist of two nonnegative integers, and applies the kernel method twice.

Grid theorems provide a fundamental link between the structure of ends and the existence of grid-like subgraphs in infinite graphs and digraphs. For every fixed width $n$, let $k(n)$ denote the least positive integer such that every digraph with an end of in-degree at least $k(n)$ contains a subdivision of the directed hexagonal grid of width $n$. Hamann and Heuer asked the exact vaule of $k(n)$. We solve this problem by proving that $$ k(n)=\left\lfloor\frac{3n}{2}\right\rfloor-1 \qquad\text{for every }n\geq4, $$ while $k(1)=1$, $k(2)=2$, and $k(3)=4$. For the upper bound, we establish a finite vacancy theorem for labelled token slides, convert it into a closed directed schedule on an auxiliary ray digraph, and lift the schedule through fresh clean linkages. For the matching lower bound, we use alternating orientations of products of a ray with a three-armed tree and prove a no-passing property for disjoint directed paths. We also determine the dual extremal parameter. Let $W(d)$ denote the largest width that is always forced by an end of in-degree $d$, with all branch rays remaining in that end, then $$W(d)=\left\lfloor\frac{2d}{3}\right\rfloor+1 \qquad\text{for every }d\geq4,$$ with $W(1)=1$ and $W(2)=W(3)=2$.

Let $G=(V,E)$ be a finite loopless directed graph. Each directed two-step diamond identifies its two pairs of opposite edges, and the connected components of the resulting auxiliary graph on $E$ define a canonical partition $\Pi_{\mathrm{opp}}(G)$. We ask whether a finite relational certificate built from the blocks of an edge partition identifies this canonical partition. We prove the functoriality and a universal coarsening property of $\Pi_{\mathrm{opp}}(G)$, count its complete fixed-profile fibre and its exact radius-one transposition neighbourhood, and reduce the parity condition in the certificate to an odd closed walk in a directed $\mathbb Z_2$-gain graph. In a fixed catalogue, four labelled target-positive rows, representing three isomorphism types, each admits a noncanonical positive partition obtained by a single cross-block transposition. In one row a stronger positive comparison partition also preserves every per-vertex, fixed-role incoming and outgoing count; it arises from a 12-edge alternating trade. The corresponding incidence fibre is a singleton in the other three rows. A deterministic 64-index family of comparison partitions yields 78 bounded positives among 256 nonidentity partitions. On the same profile fibre, one member has a complete 885-element relation semigroup and no write-preserve-use certificate, giving an exact negative. Thus the certificate has genuine but intermediate selectivity: it is neither determined by block sizes nor specific to the canonical target. The claims are finite statements in computational combinatorics and are supported by explicit, independently checkable certificates.

Let $E$ be a finite set, and let $V \subseteq \mathbb{C}^E$ be a linear subspace that is not contained in any coordinate hyperplane. The closure of $V$ in the product of projective lines $(\mathbb{P}^1)^E$ is a singular variety $Y_V$ known as the matroid Schubert variety (or arrangement Schubert variety). We use operational Chow cohomology to prove that every line bundle on $Y_V$ is the restriction of a line bundle on $(\mathbb{P}^1)^E.$ We then give combinatorial characterizations of when $Y_V$ is Gorenstein and $\mathbb{Q}$-Gorenstein, respectively. We provide examples of linear subspaces $V$ such that $Y_V$ is Gorenstein but not smooth, $\mathbb{Q}$-Gorenstein but not Gorenstein, and not $\mathbb{Q}$-Gorenstein, respectively.

We give a new intrinsic construction of the continuous tropical Prym variety, originally due to Röhrle and Zakahrov. In particular, given a harmonic double cover of graphs we explicitly construct the tropical Prym as integral torus. Moreover, we show that the tropical Prym–Torelli map from the moduli space of harmonic double covers to the moduli space of principally polarised tropical abelian varieties is continuous.

Every $n$-vertex plane triangulation admits a polychromatic red–blue vertex coloring with discrepancy at most $n-2\ceil{n/3}\le\floor{n/3}$, resolving a conjecture of Asayama and Matsumoto. The proof follows by combining Loyola et al. 2026 and Kawarabayashi et al. 2026. For $n\ge6$ and $n\not\equiv5\pmod6$, we prove the sharper bound $n-2\ceil{(n+2)/3}$. An exhaustive census of all $9{,}150$ non-isomorphic sphere triangulations with $4\le n\le12$ verifies the bounds and also confirms the sharper estimate at $n=11$, the first order in the remaining open residue class.

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ \Theta(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $\Omega(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

Stabilizer states play a central role in quantum information theory, and understanding their entanglement has motivated a large body of work. A well-studied question in particular is when a stabilizer state $|\psi\rangle$ can be transformed into another stabilizer state $|\phi\rangle$ using only single-qubit Clifford operations and Pauli measurements. If this is possible, we say that $|\phi\rangle$ is a vertex-minor of $|\psi\rangle$. Assuming Geelen's weak structural conjecture on vertex-minors, we establish the following general statement. For any fixed stabilizer state $|\phi\rangle$, the entanglement in stabilizer states $|\psi\rangle$ that do not contain $|\phi\rangle$ as a vertex-minor is asymptotically constrained. More concretely, we show that the distance of any sufficiently rank-connected $|\psi\rangle$ not containing $|\phi\rangle$ as a vertex-minor grows as $O(\log n)$, and prove similar results for the so-called locally accessible information, a quantity that captures the amount of information that can be learned through single-qubit Pauli measurements. Our results rely on (i) connecting the above two entanglement measures to rank functions of multimatroids, (ii) connecting the rank functions of circle stabilizer states to rank functions on $4$-regular multigraphs, which asymptotically constrains the entanglement of circle stabilizer states, and (iii) using Geelen's weak structural conjecture on vertex-minors to `lift' the previous result to sufficiently connected states in proper vertex-minor-closed families of stabilizer states. Our results establish a connection between asymptotic stabilizer entanglement and forbidden vertex-minors, with direct implications for the entanglement that can be generated in quantum devices.

Lattice polytopes are called very ample if for every sufficiently large $k$ every lattice point of height $k$ in the cone over the lattice polytope is the sum of $k$ lattice points of height $1$. This is a weakening of the well-known integer decomposition property (also called IDP). We give an example of a very ample lattice polytope whose $h^*$-vector is non-unimodal. Here, the $h^*$-vector is the coefficient vector of the numerator of the Ehrhart series of the lattice polytope. This answers a question of Ferroni and Higashitani, as well as a related question by Balletti. The main question whether IDP lattice polytopes have unimodal $h^*$-vector is still open. The example was found using ChatGPT 5.6 Sol. It is just the Cartesian square of a lattice polytope belonging to a class of very ample examples constructed by Lasoń and Michalek.

Let $G$ be a simple undirected graph with adjacency matrix $A(G)$. A graph $G$ is said to be unimodular if $\det A(G)\in\{-1,1\}$. A connected graph with $m$ vertices and $m+k-1$ edges is called \emph{$k$-cyclic}; in particular, a bicyclic graph has $m$ vertices and $m+1$ edges. Unimodular unicyclic graphs have been completely characterized. In this paper, we investigate the corresponding problem for bicyclic graphs. We provide a complete characterization of unimodular bicyclic graphs and determine all possible values of $\det A(G)$ for a bicyclic graph $G$. Our study is motivated by the central role of unimodular graphs in the theory of graph inverses and their connections with eigenvalue reciprocity and other spectral properties of graphs.

A canon permutation is a $k$-regular word over $[n]$ in which, for each $j$, the $j$-th copies of the letters form the same permutation $\sigma$. These were introduced by Elizalde as a generalization of nonnesting multipermutations, which are the case $k = 2$. We study classical pattern avoidance in them for arbitrary $k$. We show that avoiding any one of $112$, $122$, $211$ or $221$ is counted by the $k$-Catalan numbers $\frac{1}{n}\binom{kn}{n-1}$. We enumerate the classes obtained by forbidding one of these together with any $\tau \in \mathcal{S}_3$, and we give a bijection with $k$-ary trees that we use to generalize a theorem of Gabriel, Peske, Pudwell and Tay. We then show that avoiding a set of patterns closed under relabeling reduces, up to a factor of $n!$, to avoidance in $k$-regular lattice words. We use this to enumerate the canon permutations avoiding some natural generalizations of the nonnesting and noncrossing patterns, as well as the family $\{1^a21^b, 2^a12^b\}$. We close with several conjectures and questions.

For fixed integers $k\ge3$ and $1\le d\le k-1$ and sufficiently large $n\in k\mathbb N$, we establish the sharp minimum $d$-degree thresholds that forces perfect matching in every $n$-vertex $k$-uniform hypergraphs. This was conjectued by Treglown and Zhao, and the $d=1$ case was conjectued by Kühn, Osthus and Treglown.

Cluster varieties contain the union of cluster tori and the points not in this union are called $\textit{deep points}$, and the locus of these points is called the $\textit{deep locus}$. In arXiv:2402.16970, a description of this locus is conjectured for locally acyclic cluster algebras, in particular, stating that this should be the stabilizer locus of the cluster automorphism group. We resolve this conjecture for the case of cluster algebras arising from surfaces, introduced in arXiv:math/0608367, and the remaining finite type cases as categorized in arXiv:math/0208229. In particular, we show locally acyclic surface type cluster varieties have no deep points not contained in the stabilizer locus, and finite type cluster algebras also have no deep points not contained in the stabilizer locus, validating the mysterious points conjecture in these cases.

We study \emph{$T$-Robinson spaces}, a tree-based generalization of Robinson spaces in which every path of a compatible tree induces a Robinson subspace. This framework extends the classical notion of Robinsonian representations from linear orderings to tree structures, allowing the modeling of hierarchical and branching data. We establish a complete combinatorial characterization of $T$-Robinson spaces by proving their equivalence with several graph- and hypergraph-theoretic properties. In particular, we show that a dissimilarity space is $T$-Robinson if and only if all its level graphs are dually chordal with a common compatible tree. Combined with the characterization of hypertrees established by Brucker~\cite{brucker2005hypertrees}, this yields the equivalent characterization in terms of the associated cluster, ball, and 2-ball hypergraphs being hypertrees. Building upon these structural results, we develop a recognition algorithm with complexity \(O(K n^{2})\), where \(K\) denotes the number of minimum spanning trees of the dissimilarity space, improving upon existing hypertree-based approaches whenever \(K\) remains moderate. We further introduce a quantitative measure of $T$-Robinson structure that evaluates the extent to which an arbitrary dissimilarity space admits a tree-like representation. Finally, we discuss applications to real-world datasets, illustrating how $T$-Robinson spaces provide an interpretable framework for analyzing and organizing relational data.

Richardson tableaux were introduced by Karp and Precup in their study of irreducible components of Springer fibers that are Richardson varieties. Guo gave an explicit bijection between Richardson tableaux and Motzkin paths through noncrossing involutions and the Robinson–Schensted (RS) algorithm. In this paper, we study Richardson tableaux of a fixed shape from the viewpoint of Motzkin paths. We introduce a shape algorithm, independent of the RS algorithm, that directly determines the shape of the corresponding Richardson tableau from a Motzkin path. Based on this algorithm, we construct a local bijection which keeps track of the major statistic and reproves combinatorially Karp and Precup's $q$-enumeration formula for Richardson tableaux of a given shape. We also prove in two ways a conjecture of Guo on the comajor generating function for Richardson tableaux with a prescribed number of odd columns.

The game domination numbers $\gamma_{\rm g}$ and $\gamma_{\rm g}^\prime$, and the game total domination numbers $\gamma_{{\rm{tg}}}$ and $\gamma_{{\rm{tg}}}^\prime$ are investigated on Sierpiński graphs $S_p^n$. For the domination game, the trivial bounds arising from the known domination number and the Grundy domination number of $S_p^n$ are significantly improved by proving that $(2p-3)p^{n-2}\leq \gamma_{\rm g}(S_p^n), \gamma_{\rm g}^\prime(S_p^n) \leq (2p-2)p^{n-2}$. For the total domination game the bounds $\gamma_{{\rm{tg}}}(S_p^n), \gamma_{{\rm{tg}}}^\prime(S_p^n) \geq (2p-2)p^{n-2}$ are established.

In this paper, we study the maximal pattern complexity of two-dimensional words up to Abelian equivalence. We establish a lower bound for the Abelian maximal pattern complexity of two-dimensional words that are non-doubly periodic by projection under the existence of a transverse recurrence direction or strong recurrence. We further show that the bound is attained for every alphabet size. As a consequence, we characterize double periodicity of strongly recurrent binary words by the boundedness of their Abelian maximal pattern complexity.

We prove that the uniform random non-separable planar map with $n$ edges admits the Brownian sphere as Gromov–Hausdorff–Prokhorov scaling limit as $n$ tends to infinity. Our proof introduces a non-bijective “common-core transfer method” that constitutes a novel and universal proof strategy for scaling limits of random discrete structures. As an application, we complete the phase diagram for limiting shapes of block-weighted planar maps by Stufler~(2019). We describe phases with limits given by the Brownian sphere, stable trees, and Brownian sphere decorated stable trees recently introduced by Sénizergues, Stefánsson and Stufler~(2023).

The power graph $P(G)$ of a finite group $G$ is the graph with vertex set $G$ and edge set $E(P(G))=\{uv:\ u,v \in G,\ u \neq v,\ u \in \langle v \rangle \ \text{or}\ v \in \langle u \rangle\},$ where $\langle x\rangle$ denotes the cyclic subgroup generated by $x$. In this paper, we characterise all the finite groups with exponent $q$ whose power graphs are friendship graphs, firefly-type graphs, or torch graphs. We prove that the power graph of a finite group $G$ with exponent $q$ is a friendship graph if and only if $q=3$. In particular, in the abelian case, this is equivalent to $G\cong\mathbb{Z}_3^{n}$. We further show that, among all the symmetric and alternating groups, only $S_3$ and $A_4$ have firefly-type power graphs, whereas no finite group has a power graph isomorphic to a torch graph. Finally, we determine the generalised distance spectra $D_{\alpha}$-spectra of these graph classes.

A graph $G=(V,E)$ is called $d$-rigid if, for a generic embedding of its vertices in $\mathbb{R}^d$, the only continuous motions of the vertices preserving the distances between all pairs of adjacent vertices are those induced from the isometries of $\mathbb{R}^d$ (that is, translations and rotations of the whole graph). In this paper, we study rigidity properties of pseudorandom graphs. First, we consider $C$-expander graphs, a class of graphs recently studied in the context of Hamiltonicity of pseudorandom graphs. These are $n$-vertex graphs for which every vertex set $A$ of size smaller than $n/(2C)$ has a neighbourhood of size at least $C|A|$, and for every pair of disjoint sets $A,B$ of size at least $n/(2C)$ each, there is at least one edge between $A$ and $B$. We show that for every $C\ge 8$ and every integer $n\ge 9C$, every $n$-vertex $C$-expander is $\lfloor C/8\rfloor$-rigid. Next, we study $(n,r,\lambda)$-graphs, which are $n$-vertex $r$-regular graphs whose non-trivial adjacency eigenvalues are bounded in absolute value by $\lambda$. This is a well-known family of graphs, known to possess various pseudorandom properties. We prove that there exist absolute constants $c_1,c_2>0$ such that every $(n,r,\lambda)$-graph $G$ with $\lambda\le c_1r$ is $\lfloor c_2r\rfloor$-rigid. Our results are sharp up to the value of the universal constants involved, and they improve and extend previous work by the authors on the rigidity of random and pseudorandom graphs.

The existence of sets of balanced incomplete block (BIB) designs with pairwise additivity, called pairwise additive BIB designs, has been studied through direct and recursive constructions in the literature. This paper presents a new method of constructing such designs from affine resolvable semi-regular group divisible (ARSRGD) designs. Since many known ARSRGD designs are obtained from generalized Hadamard matrices, we also describe the corresponding construction of pairwise additive BIB designs from generalized Hadamard matrices. Using the construction together with known existence results for generalized Hadamard matrices, we obtain several new infinite series of pairwise additive BIB designs, including designs with parameter sets whose existence was previously unknown.