Papers

We introduce the multiorbital bivariate chromatic polynomial F_\Gamma(G;x,y) = \sum_{H\leq G}\frac{1}{|H|}\sum_{h\in H}P_{\Gamma/h}(x,y), which aggregates the orbital bivariate chromatic polynomials associated with all subgroups of a finite group acting on a graph. We derive the equivalent element-wise representation F_\Gamma(G;x,y) = \sum_{g\in G}c_G(g)P_{\Gamma/g}(x,y), where c_G(g) = \sum_{\langle g\rangle\leq H\leq G}\frac{1}{|H|}. The coefficient function depends only on the cyclic subgroup generated by the element and is constant on conjugacy classes. This yields decompositions by cyclic subgroups and conjugacy classes and an interpretation in terms of the incidence algebra of the subgroup lattice. After normalization, the coefficients define a probability distribution obtained by choosing a subgroup uniformly and then an element uniformly from that subgroup. We also establish diagonal multiplicativity for disjoint unions and a weighted cycle-index expression for edgeless graphs. A further contribution concerns the distinguishing power of the orbital bivariate chromatic polynomial. We answer a question of Dohmen and Lange-Geisler affirmatively by exhibiting two non-isomorphic graphs, P_3 and K_2 \mathbin{\dot\cup} K_1 under C_2-actions, with identical orbital bivariate chromatic polynomials. The two actions nevertheless have different multiorbital bivariate chromatic polynomials. Thus the multiorbital polynomial is not determined by the orbital bivariate polynomial, whereas the converse question remains open.

The asymptotic McEliece–Rodemich–Rumsey–Welch bound (1977) limits the largest attainable rate of binary codes as a function of the relative distance. After a nearly half-century hiatus, this result was recently improved in two concurrent works, by OpenAI and by O. Alrabiah and V. Guruswami. The two arguments look entirely different, a Delsarte certificate on the one hand, a classical-quantum channel and the pretty good measurement on the other, and they yield the same bound. The purpose of this note is to explain why: in both proofs, a subspace is attached to every codeword and moved with it, and the bound counts how many such subspaces fit in the ambient space, exactly in the first case and in the probabilistic sense of typicality in the second. We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.

A graph $G$ is weakly $H$-saturated if one can obtain $K_n$ by adding one edge to $G$ at a time, where each additional edge creates at least one new copy of $H$. The minimum number of edges needed for a weakly $H$-saturated graph $G$ of order $n$ is known as the weak saturation number of $H$, written $wsat(n,H)$. A graph $G$ is minimum weakly saturated if $wsat(n,G)=|E(G)|-1$ for some value of $n$. We explore classes of minimum weakly saturated graphs and their connection to the $H$-bootstrap percolation process, as well as weak saturation in a more general setting than the complete graph.

In this paper, we prove that for every integer $k\geq2$ and every $c>1$ sufficiently close to $1$, there is $\kappa>0$ such that every sufficiently large subset of $\{1,\ldots,N\}$ of density at least $(\log\log N)^{-\kappa}$ contains \[ x,\quad x+\lfloor n^c\rfloor,\quad x+\lfloor n^c\rfloor^2, \quad\ldots,\quad x+\lfloor n^c\rfloor^k. \] We also prove pointwise almost-everywhere convergence of the associated multiple ergodic averages.

We give a nibble-free construction proving $R(3,k)\ge(1/200+o(1))k^2/\log k$. We also include Shearer's proof bounding the independence number of a triangle-free graph, which implies $R(3,k)\le (1+o(1))(k^2/\log k)$.

We construct an infinite walk in $\mathbb{Z}^3$ whose steps come from a fixed set of sixteen vectors and no three of whose vertices are collinear, answering a problem of Gerver and Ramsey popularized as Erdős Problem 193.

We survey biLipschitz (BL) and bounded displacement (BD) equivalence of Delone sets, with an emphasis on examples arising in aperiodic order. After recalling the classical results of Burago-Kleiner, McMullen, and Laczkovich, we discuss criteria for rectifiability, uniform spreadness, and BD equivalence, and how these relate to discrepancy and point-counting estimates. We then focus on Delone sets associated with substitution tilings, where these questions can often be studied through the combinatorial and spectral properties of the underlying substitution rules. We also consider selected classes of cut-and-project sets and briefly discuss extensions beyond BL and BD equivalence.

In the localization game on a graph $G$, a team of cops searches for an invisible, mobile robber on $G$ by "probing" vertices; each probe tells the cops the distance from the probed vertex to the robber. The cops win if they can uniquely determine the robber's location. In this paper, we introduce a related game: the directional localization game. In this game, instead of probes returning distances, they return directions: when the cops probe a vertex $v$, the robber must respond with one or more neighbors of $v$ that lie on a shortest path from $v$ to the robber's location. The minimum number of cops needed to win this game on $G$ is the directional localization number of $G$. We study the directional localization game on several classes of graphs, including chordal graphs, Cartesian products, and incidence graphs of projective planes. We also bound the directional localization number of a graph $G$ in terms of the degeneracy and the treewidth of $G$.

For integers $h,k\geq 1$, let $hA$ be the $h$-fold sumset of $A$ and put $\mathcal{R}(h,k)=\{|hA|:A\subset\mathbb{Z}, |A|=k\}$. Previously, the fixed-cardinality exponent law was known only for $k\leq 3$; every fixed $k\geq 4$ remained open. We settle the problem in full by determining the complete fixed-cardinality exponent law: $|\mathcal{R}(h,k)|=\begin{cases}1,&k\leq 2,\\ h,&k=3,\\ h^{k-1+o_k(1)},&k\geq 4\end{cases}$. Here $o_k(1)\to 0$ as $h\to\infty$ with $k$ fixed. More sharply, for fixed $k\geq 4$, an interval of length $\Theta_k(h^{k-1})$ contains at least $h^{k-1-o_k(1)}$ attainable values. At $k=4$ we prove $|\mathcal{R}(h,4)|=\Theta(h^3)$ with positive lower density in its ambient interval, disproving Nathanson's proposed $o(h^3)$ and $O(h^2)$ bounds. One bounded addition-table geometry drives these results, coupling Hilbert-energy amplification to optimal finite-observation compression. Every ordered real $k$-set ($k\geq 2$) has an integer model in $[0,O_k(h^{k-2})]$ preserving every sum equality and strict comparison through degree $h$; the exponent $k-2$ is sharp. The universal label-realization length is therefore $\Theta_k(h^{k-2})$, one power sharper than Nathanson's $O_k(h^{k-1})$ bound. For $h\geq 2$ and $k\geq 3$, minimum active rank equals realization-frequency codimension, exponent-shape codimension, and sampling-rarity exponent; a full-exponent family has maximal-rank witnesses with Cohen-Macaulay toric coordinate rings. At rank zero, for $h\geq 2$, it proves the conjectural OEIS A227589 formula $\binom{h+2}{2}+\mathbf{1}_{\{2\nmid h\}}$ for the least normalized diameter of a four-point $B_h$-set. It also gives exact fixed-$(h,k)$ popularity laws for $k$-subsets of $\{1,\ldots,q\}$ as $q\to\infty$, resolving Nathanson's Problems 9 and 10.

Albertson's conjecture states that every graph of chromatic number r has crossing number at least that of the complete graph K_r. We prove the conjecture for all r. The proof combines new clique-sensitive edge bounds for critical graphs, maximum-clique sampling, and a reserved immersion construction. For graphs of order close to r, we construct edge-disjoint routes while preserving a complete bipartite subgraph whose forced crossings compensate for those introduced when the immersion is smoothed into a drawing. For larger orders, we derive explicit edge bounds using independent-triple deletion and structural properties of critical graphs, then combine them with sampling inequalities that account for crossings within a maximum clique. The remaining numerical inequalities are certified using exact rational arithmetic, with a reproducible certificate and standalone Python verifier.

We prove that, for every integer $k\ge 2$, there exists a constant $c_k>0$ such that every graph on $n\ge R(k,k)$ vertices with maximum degree $\Delta$ contains an induced subgraph on at least $n-c_k\sqrt{\Delta}$ vertices whose maximum degree is attained by at least $k$ vertices. This confirms a conjecture of Caro and Yuster in strong form.

An electrical network can be summarized at its boundary by a response matrix: prescribed boundary voltages determine boundary currents. A superport network adds a constraint by grouping boundary terminals into superports, requiring the total current in each group to be zero and making voltage differences inside the groups the natural coordinates. Earlier work determined forest formulas for a single response entry and for the determinant of the whole response matrix. The missing case was an arbitrary subdeterminant, or minor: one needs to know not only which spanning forests contribute, but also the sign carried by each forest. This paper supplies that sign rule. After choosing one reference vertex in each superport, the response is \[ L=\left(D^{T}K^{-1}D\right)^{-1}, \] with \(K\) the grounded weighted Laplacian and \(D\) recording the selected voltage differences. Contracting the components of a physical spanning forest \(F\) produces a much smaller quotient port graph \(H_F\). Its reduced incidence matrix \[ B_F=Q_FD \] has columns only of the forms \[ 0,\qquad \pm e_a,\qquad e_a-e_b. \] Hence every square incidence minor is exactly \(0\) or \(\pm1\). For a \(k\)-set of response coordinates \(I\), append to \(B_F\) the selector rows \(E_I^{T}\) and define the completed quotient-incidence determinant \[ \widehat{\chi}_F(I) = \det \begin{pmatrix} B_F\\ E_I^{T} \end{pmatrix}. \] For coordinate sets \(I,J\) of the same size, the arbitrary response minor is a weighted spanning-forest sum whose coefficient is simply \[ \widehat{\chi}_F(I)\widehat{\chi}_F(J). \] Thus the Jacobi complementary-minor factors used in the derivation disappear from the final theorem. Direct block-triangular reduction gives \[ \widehat{\chi}_F(I)\in\{0,\pm1\}, \] with nonvanishing occurring exactly when the complementary quotient edges \(N\setminus I\) form a spanning tree of \(H_F\).

For $n\in\mathbb{N}$, we consider the set of lattice paths from $(0,0)$ to $(n,n)$ using only unit north and east steps. Given a point $B$ to be avoided, we ask: at which point $A$ on the grid with corners $(0,0)$ and $(n,n)$, different from the endpoints, does the largest number of $B$-avoiding lattice paths pass through? We show that for $n\ge 9$, regardless of the location of $B$, the maximum is attained at one of ten specific points clustered near the two endpoints of the grid. This stability, however, conceals an interesting anomaly. When the obstruction $B$ lies on the antidiagonal $x+y=n$, the points of maximal traffic migrate from the near-corner points $(1,1)$ and $(n-1,n-1)$ to boundary points in the set of possible maximizers. The migration occurs for every $8\le n\le 375$, and intermittently up to $n=495$. We conjecture that the anomaly disappears for $n\ge 496$.

We establish multiplicative comparisons between Rényi entropies of different orders for weighted sums of independent Bernoulli random variables. In particular, we prove a logarithmic comparison between the zeroth- and infinity-order Rényi entropies, which yields a polynomial improvement over the square-root bound of Jain, Sah, and Sawhney. As an application, this leads to an improved parameterized running time for the randomized bin-packing algorithm of Nederlof, Pawlewicz, Swennenhuis, and Wȩgrzycki. We also obtain explicit dimension-free, constant-factor comparisons between Rényi entropies of positive orders.

An orthodox dominating set on an $n\times n$ chessboard occupies every row of one parity and every column of a possibly different parity. For $n\ge400001$, every such set contains more than $(1/2+1/80000)n-2$ queens, on odd and even boards and with attacking or boundary queens allowed. Second-moment estimates and an exact rational line-weight certificate give a stronger bound for $p$-covers; finite diagonal completion and board extension transfer it to orthodox covers. The cost of extending an arbitrary dominating set to an orthodox cover yields an inequality with an explicit defect term. The previously constructed independent, border-free Type-A $1$-cover of $Q_{221}$ with $111$ queens supplies a finite seed. Classical amplification gives ordinary and independent domination upper bounds with coefficients $112/221$ and $113/221$, respectively. Its order 221 is below the density threshold 400001. For admissible seeds whose orders tend to infinity, the lower limit of these coefficients is at least $1/2+1/16000$.

We introduce the class of star cluster algebras and classify their singularities. Then we focus on the combinatorial structure of the desingularization by determining the number of irreducible centers that are blown up.

The Erdős–Stone Theorem asserts that if a graph has edge density $1-1/r+\delta$ then it contains a complete $(r+1)$-partite graph with $b$ vertices in each part, where $b=b_n(r,\delta) \gg 1$. The celebrated Chvátal–Szemerédi theorem determined the exact order of $b_n(r,\delta)$ for every $\delta < 1/r^3$. Their bound, however, is not tight when $\delta=1/r-\epsilon$, that is, when the graph has edge density $1-\epsilon$ for small $\epsilon$. Our main result in this paper determines the correct order in this remaining regime, thereby enabling us to give a tight bound for the Erdős–Stone problem for all edge densities. More precisely, we prove that for every integer $r\geq 2$ and $0< \delta < 1/r$ we have $$ b_n(r,\delta)=\Theta\left(\frac{\log n}{(1/r-\delta)r\log(1/\delta)}\right)\;. $$ The lower bound is obtained using a Kövari-Sós-Turán-type argument combined with a variant of Nikiforov's method of constructing large blow-ups, while the upper bound is proved using a correlated random graph construction, related to tensor powers.

For a finite graph $G$ on $n$ vertices, let $\eta(G)$ denote the least order of a finite abelian group $\Gamma$ for which $G$ is an induced subgraph of some Cayley graph of $\Gamma$. Babai and Sós (1985) settled the worst-case order of magnitude: it is $\Theta(n^2)$. We treat $\eta$ instead as an invariant of the individual graph, minimised over all finite abelian groups rather than over the cyclic groups alone, which is the restriction implicit in the literature on representation numbers modulo $n$. We prove a local order floor: $\eta(G)$ is at least the maximum of $n$ and twice the largest independence number of a neighbourhood of $G$. This localises at an arbitrary vertex the correspondence of Babai and Sós between induced stars and sum-free sets; a corollary of the classification of maximum sum-free sets in abelian groups does not lower this floor, but restricts which host orders are admissible and so prunes the search. We determine $\eta$ exactly for paths, where it equals $n+1$, and for complete bipartite graphs $K_{a,b}$, where it equals $2\max(a,b)$ and meets the floor. A Cartesian product bound gives $\eta(P_m \,\square\, P_m) = (1+o(1))n$. We report certified exact values of $\eta$ for $22$ graphs, computed over all abelian groups. Seventeen of the $22$ optimal hosts are cyclic, so on most of these graphs the cyclic restriction costs nothing; where it bites, however, it is expensive. A search restricted to cyclic groups returns $36$ for the Petersen graph against the true value $16$, and $59$ for the Frucht graph against $27$. The cost of the restriction is concentrated rather than diffuse, and we identify the graphs on which it is paid. We also determine $\eta$ exactly for the double stars $D_{q,q}$ with $2 \le q \le 6$, obtaining $5q$ in each case. Since $\eta(D_{6,6}) = 30$ exceeds $2n = 28$, no constant below $15/7$ can bound $\eta(T)/n$ over all trees.

We construct additive rank-metric and sum-rank-metric codes from Drinfeld modules by restricting bounded-degree morphisms to prime-to-characteristic torsion. For supersingular Drinfeld modules of rank $r$ in characteristic $\mathfrak{p}$ of degree $d$, the stabilization formula for morphism spaces yields rank-metric codes of $\mathbb{F}_q$-dimension $mrt-c$ and minimum distance $r-t+1$, where $c=r(r-1)(d-1)/2$. Simultaneous restriction to $\ell$ distinct degree-$m$ torsion modules gives additive sum-rank codes of the same dimension and minimum distance at least $\ell r-t+1$. Their normalized Singleton defects tend to zero, while in characteristic $(T)$ the module $\phi_T=\tau^r$ makes the defect vanish and produces an explicit MSRD family. We identify this family with a skew Chinese remainder theorem code supported on central skew polynomials and prove that its poly-skew weight is exactly $m$ times its sum-rank weight. This gives a specialized Singleton-type bound and a polynomial-time unique decoder up to the full sum-rank unique-decoding radius. We also derive a Welch-Berlekamp-type filter equation for the general supersingular sum-rank construction; it becomes an effective decoder whenever bases of the relevant morphism spaces and the restriction maps are computable.

A pair $(\mathcal{A}, \mathcal{B})$ of families of subsets of $[n]$ is cancellative if whenever $A, A' \in \mathcal{A}, B \in \mathcal{B}$ satisfy $A \cup B=A' \cup B$, then $A=A'$, and whenever $A \in \mathcal{A}, B, B' \in \mathcal{B}$ satisfy $A \cup B=A \cup B'$, then $B=B'$. We show that for every cancellative pair $(\mathcal{A}, \mathcal{B})$, the inequality $|\mathcal{A}||\mathcal{B}| \le 2.25^n$ holds, matching Tolhuizen's $(2.25-o(1))^n$ lower bound construction.

We study linear codes whose coordinates are the ordinary edges and self-loops of complete undirected graphs; a node erasure removes all coordinates incident with a failed vertex. The construction results are binary. For triple-node erasures, we extend the published cyclic construction by allowing a suitable cyclic check slope to depend on the prime graph length. An explicit determinant test proves that one of three fixed slope choices works at infinitely many prime lengths, unconditionally, and gives redundancy $3n-2$, one bit above the graph Singleton bound. We also give Singleton-optimal triple-node codes at $n=6,8,10,12$, together with a general ordinary-edge framework that isolates the remaining loop-completion problem. When $2$ is primitive modulo an odd prime $n$, a binary multi-slope construction corrects every $\rho$-node erasure for $2\leq\rho<n$, with redundancy $\rho n-(\rho-1)$ in the range $2\leq\rho\leq(n+1)/2$. Returning to arbitrary prime powers, we derive exact generating transforms and inclusion–exclusion formulas for node-metric ball volumes, fixed-radius asymptotics, and packing, existence, and covering bounds. Finally, for the complementary clique-erasure metric, we obtain an exact weight enumerator and a Singleton-optimal node–clique duality.

It is well known that the Young lattice is the Bratelli diagram of the symmetric groups, expressing how irreducible representations restrict from $\mathfrak{S}_{N}$ to $\mathfrak{S}_{N-1}$. In 1975, Stanley discovered a similar lattice called the Young-Fibonacci lattice which was identified as the Bratelli diagram of a family of algebras $\{\mathbf{O}_N(X,Y)\}_{N \geq 0}$ by Okada in 1994. In this paper, we first realize the Okada algebra $\mathbf{O}_N(X,Y)$ and the associated monoid $\mathbf{O}_N$ using a labelled version of non-crossing arc-diagrams appearing in the description of the Temperley-Lieb algebra and Jones monoid. We establish, for general parameters $(X,Y)$, that the dimension of the Okada algebra $\mathbf{O}_N(X,Y)$ is $N!$, noting that Okada proved this result only in the semisimple case. We interpret a natural bijection between permutations and labelled arc-diagrams as an incarnation of Fomin's version of the Robinson-Schensted correspondence associated to the Young-Fibonacci lattice. The arc-diagram formalism allow us to probe the structure of the Okada monoid and algebra. In particular we prove that the Okada monoid is a regular, aperiodic $*$-monoid and we describe its Green relations and order. These results allow us to construct a cellular basis of the Okada algebra and to show that $\{\mathbf{O}_N(X,Y)\}_{N \geq 0}$ forms a coherent tower of cellular algebras in the sense of Goodman and Graber. We present some conjectures expressing the Gram determinant of the invariant bilinear form attached to each cell module in terms of Okada's clone Schur functions. We conclude the paper by presenting two follow-up, ongoing projects along with a series of questions pushing further the analogy between the symmetric groups and the Okada algebras.

For every $n$, we construct a 2-dimensional $n$-element poset whose Hasse diagram has independence number $n\exp(-\Omega(\sqrt{\log n}))$, and consequently, chromatic number $\exp(\Omega(\sqrt{\log n}))$. This also yields an $n$-point planar set whose box-Delaunay graph satisfies the same bounds.

The set of the triangulations with vertex set $X$ of a simple polygon $\mathrm{P}$ can be structured into a flip-graph $\mathcal{F}(\mathrm{P},X)$ whose edges connect two triangulations that differ by a single arc. The geometry of flip-graphs has been thoroughly studied and it is known that the subgraph $\mathcal{F}_\varepsilon(\mathrm{P},X)$ induced by the triangulations that contain a given arc $\varepsilon$ is strongly convex in $\mathcal{F}(\mathrm{P},X)$ when $\mathrm{P}$ is convex and $X$ contains no puncture (points in the interior of $\mathrm{P}$) and at most one flat vertex (points in the interior of an edge). When $X$ contains at least two punctures or flat vertices, it is also known that this strong convexity property fails. Here, we close the last open case by showing that, for any convex polygon with sufficiently many vertices, one can always place a single puncture in $X$ in such a way that $\mathcal{F}_\varepsilon(\mathrm{P},X)$ is not strongly convex in $\mathcal{F}(\mathrm{P},X)$. We prove a similar result for simple polygons with a single reflex vertex. The main ingredients in our proofs are a decomposition lemma for a class of $3$-dimensional triangulations and a hyperbolic volume argument regarding their embedding into $\mathbb{H}^3$.

On the once-punctured torus, we give an exact formula for the number of curves in any given mapping class group orbit of given word length. This settles a conjecture of Chas in [Cha16].

For a finite permutation group, a base is a set of points with trivial pointwise stabiliser, and the generalised Saxl graph records which pairs of points lie together in a base of minimum size. Burness and Giudici conjectured that any two vertices of the Saxl graph of a primitive group of base size two have a common neighbour, and Freedman, Huang, Lee and Rekvényi extended this conjecture to arbitrary base size. We disprove both. For each integer $B\ge2$ we construct infinitely many primitive groups of base size $B$ whose generalised Saxl graphs contain two nonadjacent vertices with no common neighbour. At base size two, where this is the usual Saxl graph, we obtain three further infinite families, one each of affine, product and twisted wreath type, so the conjecture fails in three of the five O'Nan–Scott types; in the affine and product type families the Saxl graphs have diameter exactly three. This answers Problem~21.29 in the Kourovka Notebook in the negative. In the positive direction, we prove the Burness–Giudici conjecture for every primitive affine group whose point stabiliser is almost quasisimple of sporadic type, completing work of Lee and Popiel. We conjecture that no base-two counterexample of almost simple or diagonal type exists.

The Modulo Krinkle tilings of Imura (arXiv:2506.07638) form a family of non-periodic, spiral monohedral tilings parametrized by a reduced fraction $m/k$ and an integer $t\ge 2$. We show that the Farey sum (mediant) $(m_1+m_2)/(k_1+k_2)$ of two Farey-adjacent parameters is realized by an exact geometric operation on prototiles: the lower boundary path of the $(m_1+m_2,k_1+k_2)$-prototile is obtained by concatenating the parents' lower paths after an edge-length-preserving progressive rotation (fan-twist) of their edges. Conversely, every prototile admits exactly one fan-twist splice decomposition – no non-adjacent parameters ever splice – the cut position being $k_1=m^{-1}\bmod k$, and the recursion descends the Stern-Brocot tree to a single unit edge. The combinatorial core of the operation is the classical standard factorization of Christoffel words; the contribution here is its exact edge-isometric realization on circular direction systems and the resulting structure theory for the Modulo Krinkle family, including the recently introduced variants: we prove a separation theorem stating that every variant prototile is the common recursively-generated core plus finitely many direction-invariant decoration edges. As a corollary of Imura's spiral-arm count formula, the two Farey parents are visible in the offset-free tiling itself: the numbers of counterclockwise and clockwise spiral arms are $tk_1$ and $tk_2$.

For integers q at least 3 and r at least 1, consider the directed Cayley graph on the cyclic group of order qr whose allowed steps are the integers from 1 through r. A Hamilton cycle H is called a q-layer balanced Hamilton starter if, for every step from 1 through r and every residue class modulo q, H contains exactly one arc of that step whose tail belongs to the given residue class. The r translates of H by successive multiples of q then form a Hamilton decomposition of the digraph. A q-layer balanced Hamilton starter is called chain-compatible if one arc can be selected from each Hamilton cycle in this decomposition so that the selected arcs form a simple directed path. In both constructions, the compatible deletion chain is the arithmetic step-2 path beginning at 0 and ending at 2r. For q equal to 4, a chain-compatible starter is obtained explicitly whenever r is congruent to 1 modulo 4 and r is at least 9, while for q equal to 3 one exists for all sufficiently large r congruent to 5 modulo 6. The proofs are constructive: the four-layer case uses an ABAB step word, while in the three-layer case a directed rotational terrace is lifted to a 3-layer balanced directed 1-factor and a fixed four-arc trade joins its two cycles. Deleting the unique prescribed-path arc from each translated Hamilton cycle gives r Hamilton paths; together with the prescribed path, these form an optimal decomposition of the arc set into r+1 directed paths in both cases.

We prove that a relation obtained by composing arbitrary functions of arity $\leq k$ with a relation definable in an $n$-dependent structure is $kn$-dependent. This confirms a conjecture of Chernikov and Hempel. We also demonstrate optimality of the result.

Let $G$ be a finite simple graph on $[n]$ and let $I_c(G)$ denote its complementary edge ideal in the polynomial ring $S = K[x_1,\dots,x_n]$. We give a combinatorial description, in terms of the structure of $G$, of the minimal generators of the symbolic Rees algebra $\mathcal{R}_s(I_c(G)) = \bigoplus_{k \geq 0} I_c(G)^{(k)} t^k$, and show that this algebra is generated in degree at most $6$. Moreover, we completely determine the minimal generators of $\mathcal{R}_{s}(I_{c}(G))$ in graph-theoretic terms. We then study in more detail the homological invariants of the symbolic powers $I_c(G)^{(k)}$ for the classes of cycle graphs and complete multipartite graphs. For theses families, we study the behavior of the symbolic depth function $k\mapsto\operatorname{depth} S/I_c(G)^{(k)}$, we obtain the limit depth of the symbolic powers and the Waldschmidt constant of $I_c(G)$, and further prove that all the symbolic powers $I_c(G)^{(k)}$ are componentwise linear.