Papers

Motivated by recent work on tree independence number, we study the path independence number of a graph $G$: the minimum integer $k$ such that there is a path decomposition of $G$ where each bag induces a graph with independence number at most $k$. We show that every graph excluding both an induced forest minor and an induced star has bounded path independence number. This characterises when a graph class that excludes an induced star has bounded path independence number while also partially resolving a conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel and Wiederrecht (2024). Furthermore, we show that graphs excluding both an apex-forest induced minor and an induced star have bounded tree independence number. As a consequence, for every fixed apex-forest $H$ and integer $t$, there is a polynomial-time algorithm to test whether a $K_{1,t}$-induced-subgraph-free graph contains $H$ as an induced minor. Moreover, it follows that the Maximum Weight Independent Set problem, as well as several other NP-hard problems, can be solved in polynomial-time on $K_{1,t}$-induced-subgraph-free graphs that exclude $H$ as an induced minor.

Let $\lambda$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $\alpha>1$, we prove that there are $O(n^{\lceil2\alpha\rceil-1})$ cuts of size strictly below $\alpha\lambda$. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families of vertex sets.

For a graph $F$, the Turán number $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Turán numbers of even cycles is a central problem in extremal graph theory and remains open in general. For $C_6$, the best previous upper bound was due to Füredi, Naor, and Verstraëte [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq \lambda n^{4/3}+O(n)<0.6272 n^{4/3}, $$ where $\lambda$ is the real root of $ 16\lambda^3-4\lambda^2+\lambda-3=0$. We improve this bound by showing that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq \alpha n^{4/3}+O(n)<0.6144 n^{4/3}, $$ where $\alpha$ is the unique real root of $ 4 \alpha^{3} (3/2)^{1-1/(2\alpha)} =1$ in the interval $(1/2,2/3)$.

Identifying codes in graphs have been widely studied since their introduction by Karpovsky, Chakrabarty and Levitin in 1998. In this paper, we consider the vertices that are in every minimum identifying code in a graph. There are two types of such vertices: always-forced vertices that belong to all identifying codes (minimum or not) and min-forced vertices that belong to all minimum identifying codes. A vertex is called proper-min-forced if it is min-forced but not always-forced. We show an upper bound $2n/3$ for the number of such proper-min-forced vertices in a closed-twin-free graph of order $n$. Moreover, for integers $n$ divisible by three, we construct an infinite family of graphs in which there are $2n/3-1$ such vertices. In addition, we determine the maximum number of edges in a graph of even order such that the graph contains proper-min-forced vertices. We also show that the decision problem of determining whether a given vertex in a graph is proper-min-forced is co-NP-hard.

Coloring Discovery asks whether a possibly improper initial coloring can be made proper within a prescribed number of allowed changes. We study the parameterized complexity of three modification step models that were studied previously in the literature: recoloring one vertex (color flipping), swapping the colors of arbitrary vertices (color swapping), and swapping colors only across an edge (color sliding). For color flipping, we give exact fixed-parameter algorithms for the parameters vertex cover and distance to complete. For color swapping, we obtain fixed-parameter tractability for the parameter vertex cover plus the number of colors. Our lower bounds show W[1]-hardness for treedepth plus feedback vertex set in the color flipping model and for the number of colors plus bandwidth or distance to disjoint paths in the swapping and sliding models. All three variants remain NP-complete with four colors on graphs of diameter two.

The increasing penetration of renewable energy and rising electricity demand are driving the need to integrate new buses and transmission lines into transmission grids. These trends are reshaping transmission expansion planning (TEP), motivating the development of effective methodologies to manage the resulting complexity. This paper introduces the longest shortest-path connection (LSPC) algorithm, a graph-based method to enhance the mixed-integer linear programming disjunctive formulation of TEP using valid inequalities (VIs). Traditional approaches for determining big-M coefficients in disconnected TEP networks typically rely on solving the computationally intensive longest path problem (LPP). In contrast, LSPC circumvents these limitations by efficiently identifying relevant power-flow paths between disconnected buses within the expansion network. We demonstrate that the VIs generated from these identified paths dominate those derived from LPP-based methods and other existing approaches.

Let $X$ be a finite set with $|X|=n$ and let $\mathrm{Jac}(a,b)=|a\,\triangle\, b|/|a\cup b|$ be the Jaccard distance on the power set $2^X$. Lladser and Paradise recently proved that the metric dimension of $(2^X,\mathrm{Jac})$ is $\Theta(n/\ln n)$, with the constant left open; their bounds are $(\ln 2)\,n/\ln n\lesssim \beta(2^X,\mathrm{Jac})\lesssim 2\ln(2e)\,n/\ln n$. We determine the constant: \[ \beta(2^X,\mathrm{Jac})=\frac{2n}{\log_2 n}\,(1+o(1))=(2\ln 2)\,\frac{n}{\ln n}\,(1+o(1)). \] The proof identifies the problem, on each “slice” of subsets of fixed cardinality, with the Erdős–Rényi coin-weighing problem for a spring scale (the problem of detecting matrices). The lower bound is the Erdős–Rényi entropy argument applied to the middle slice; the upper bound follows from the explicit detecting families of Lindström and of Cantor and Mills, augmented by a single extra landmark that reveals cardinality.

We construct an explicit infinite family of simple two-dimensional Cayley complexes over $\mathbb{F}_2^n$ whose degree is polynomial in $n$ and whose nontrivial vertex-link eigenvalues lie in $[-\lambda,\lambda]$ for every fixed $\lambda>0$. For every fixed $d\ge2$, we also obtain an explicit infinite family of weighted $d$-dimensional Cayley complexes over $\mathbb{F}_2^n$ with codimension-two local spectral norm at most $1/d$ and Cayley degree $\Theta_d(n)$. Our two-dimensional construction uses evaluation at rational points of algebraic curves to produce projective direction sets and many functions affine along these directions, which may be useful for further constructions and improvements.

Let $A\in\mathbb{R}^{m\times n}$ have columns of Euclidean norm at most one. We prove that $\operatorname{disc}(A)\le2395\left(1+\log_+\frac n9\right)^{1/4}+2\sqrt2$. Here $\log_+t=\max\{0,\log t\}$. Building on Bansal and Jiang's affine spectral independence framework, we remove the $(\log\log n)^{7/4}$ factor from their bound. The fourth root comes from balancing the logarithmic decrease in the alive dimension against the fourth power of the row thresholds. Historical exponential sums control the covariance budget across size classes with summable thresholds. An exact threshold-sum certificate gives the coefficient $2395$, and rounding at most eight remaining fractional coordinates costs $2\sqrt2$. The finite construction also gives partial colourings from any prescribed starting point and at any prescribed depth, preserving existing signs. We formalize the partial- and full-colouring theorems in Lean, including the finite trajectory, exact threshold sum and final rounding, with Bansal–Jiang Theorem A.4 as the sole external research theorem assumption.

Let $P_t$ denote the induced path on $t$ vertices. Let $\omega(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gyárfás (1987) proved that every $P_t$-free graph $G$ satisfies $\chi(G)\le(t-1)^{\omega(G)-1}$, and Gravier, Hoàng, and Maffray (2003) improved this to $\chi(G)\le (t-2)^{\omega(G)-1}$ for $t\ge4$. We lower the base of the exponential by one: for every $t\ge5$, every $P_t$-free graph $G$ satisfies \[ \chi(G)\le 3\,(t-3)^{\omega(G)+4}. \] The proof combines two refinements of the Gyárfás path argument and was developed with the assistance of Claude Fable 5.1 of Anthropic and GPT Pro of OpenAI.

We derive linear programming (LP) bounds on the minimum distance of binary and ternary linear complementary dual (LCD) codes by imposing arithmetic constraints on their weight enumerators. Special values of the weight enumerator give finitely many Gauss phases, each of which yields linear equations in the ordinary weight-distribution variables. The resulting bounds strengthen the real-valued LCD counting LP without introducing additional variables; both the number of branches and the number of added equations per branch are bounded independently of the code length. Exact certificates establish strict improvements for 62 binary parameter pairs of length at most 20 and 39 ternary pairs of length at most 14. For four binary pairs, the bounds also improve the joint-weight-enumerator LP while using fewer variables per branch. These comparisons show that Gauss-phase information provides a compact strengthening of existing LP relaxations for LCD codes.

Graph search algorithms and their corresponding graph search trees are commonly used in algorithmic graph theory. In recent years, the recognition problem of these graph search trees has received significant attention. So far, the research has focused on two types of search trees: first-in trees that behave like BFS-trees and last-in trees that behave like DFS-trees. The search tree paradigms differ from each other by the parent a vertex is connected to. In first-in trees, it is the first visited neighbor, while in last-in trees it is the last neighbor visited before that vertex. Here, we will generalize these concepts of graph search trees by allowing every preceding neighbor of a vertex to be the parent. We study the complexity of the recognition problem of these generalized graph search trees. We present NP-completeness proofs for most searches. We also show that the problem is trivial for Generic Search and polynomial-time solvable for several searches on bipartite graphs and chordal graphs. We also study the question how fixing the start vertex influences the complexity of the problem.

The directed clique number $\vec{\omega}(T)$ of a tournament $T$ is the minimum, over all orderings of the vertices of $T$, of the clique number of the graph whose edges are the arcs that point backward with respect to the ordering. In this paper, we prove that, for every integer $k \geq 3$, deciding whether $\vec{\omega}(T) \leq k$ is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether $\omega(G) \leq k$ is polynomial-time solvable for every fixed integer $k$. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with $\vec{\omega}(T) \leq 2$ from those with $\vec{\omega}(T) > 100$. We also study the tournament analogue of the Gyárfás–Sumner conjecture. We construct new $\vec{\chi}$-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is $\vec{\chi}$-bounded. We then exhibit new tournaments that are not $\vec{\chi}$-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-$\vec{\omega}$-critical and 4-$\vec{\omega}$-critical tournaments.

The independent set polytope, or stable set polytope, of a graph $G$ is the 0/1-polytope defined by the convex hull of the characteristic vectors of all independent sets of $G$. We present a simple algorithm for computing a Hamilton path on the independent set polytope of a given $n$-vertex graph $G$ with amortized delay $\mathcal{O}(n)$. The independent sets are listed such that two consecutive sets differ either in removing a vertex, or adding a vertex and removing its neighbors from the independent set, i.e., the symmetric difference between two consecutive independent sets induces a star in $G$. As applications of this result, we obtain an algorithm to compute a Hamilton path on the matching polytope of an $m$-edge graph $G$ with worst-case delay $\mathcal{O}(m)$, which lists all matchings of $G$ in such a way that the symmetric difference between two consecutive matchings is a path on at most three edges. Furthermore, we obtain an algorithm to compute a Hamilton path on the chain polytope and order polytope of an $n$-element poset $P$ with amortized delay $\mathcal{O}(n)$, which lists all antichains of $P$ or all ideals of $P$, respectively, by star exchanges. Our algorithms are derived from the generic framework proposed by Merino and Mütze (FOCS'23+SICOMP'24) for computing Hamilton paths on arbitrary 0/1-polytopes, which uses a linear optimization procedure as a black box. Our algorithms bypass solving the computationally intractable maximum weight independent set problem by a simple and purely combinatorial greedy rule.

Given a graph $G=(V,E)$, let $S$ ($\subseteq V$) be a set of vertices. Two vertices are mutually visible if there exists a shortest path in $G$ between them that does not contain any other vertex of $S$. A set $S$ is a Mutual Visibility Set (\MVS) if every pair of vertices in $S$ is mutually visible. The concept of \MVS s in graphs has attracted significant attention since its introduction, as it provides an important structural property of graphs. However, determining a maximum \MVS\ in general graphs is computationally intractable; the decision problem of whether a graph admits an \MVS\ of size at least $k$ has been shown to be NP-complete. Thus, prior work has focused on finding maximal \MVS s or restricting attention to specific graph classes. Cactus graphs form a fundamental low-treewidth class, yet the maximum \MVS\ problem for this class remains open. In this paper, we first determine the size of maximum \MVS~in cactus graphs, and introduce two self-stabilizing algorithms that construct such sets. The first algorithm uses a single BFS tree and stabilizes in $O(D)$ rounds with $O(\log n)$ bits per process on average; the second one uses parallel BFS trees and stabilizes in $O(|C_{\max}|+|T_{\max}|)$ rounds, which we show to be asymptotically tight as a function of these two parameters, even on graphs where $|C_{\max}|+|T_{\max}| = o(D)$.

Let $C \le \mathbb{F}_q^n$ be a uniformly random $\mathbb{F}_q$-linear code of rate $1 - h_q(\rho) - \varepsilon$, and let $L^*(C,\rho)$ be the least $L$ such that every Hamming ball of relative radius $\rho$ contains at most $L$ codewords of $C$. That $L^* = \Theta_{q,\rho}(1/\varepsilon)$ has been known since work of Guruswami, Håstad and Kopparty and of Guruswami and Narayanan. Guruswami, Li, Mosheiff, Resch, Silas and Wootters proved that the constant in front of $1/\varepsilon$ is at least $h_q(\rho)$ for all $q$, along with an upper bound special to $q = 2$ which narrowed $L^*$ to within three consecutive integers in that case. But for $q \ge 3$ no upper bound with the correct constant was known. We determine $L^*$ for every prime power $q$. Let $\zeta := h_q(\rho)/\varepsilon$. For every sufficiently small $\varepsilon$, with probability $1-o(1)$ over the choice of $C$, $$L^*(C,\rho) = \lceil \zeta \rceil,$$ unless the fractional part of $\zeta$ is at most $q^{-\Omega_{q,\rho}(\zeta)}$, in which case $L^*(C,\rho)$ is $\lfloor \zeta \rfloor$ or $\lfloor \zeta \rfloor + 1$. By the threshold characterization of random linear codes due to Mosheiff, Resch, Ron-Zewi, Silas and Wootters, both bounds reduce to a two-sided estimate of a single quantity $V(q,L,\rho)$, where $1-V(q,L,\rho)$ is the threshold rate for $(\rho,L)$-list-decodability. We prove for all large $L$: $$h_q(\rho)(1 + 1/L) - q^{-\Omega_{q,\rho}(L)} \le V(q,L,\rho) \le h_q(\rho)(1 + 1/L).$$ The upper bound rests on a new entropy inequality for sparse random vectors under pairwise non-proportional linear constraints, proved with the Erdős-Rado sunflower lemma. The lower bound is an exact analysis of the distribution introduced by Guruswami, Li, Mosheiff, Resch, Silas and Wootters.

Is it possible to walk to infinity, avoiding three collinear points, using as steps only the standard unit basis vectors $(0,0,\ldots, 0, 1, 0, \ldots, 0)$? We prove this is possible in $16$ dimensions.

Families of sequences with low mutual aperiodic crosscorrelation assist the design of systems for multi-user asynchronous communications and multiple-input multiple-output radar. The crosscorrelation demerit factor of a pair of sequences is the sum of the squared magnitudes of their crosscorrelation values at every shift when the sequences are normalized to unit Euclidean norm, and the merit factor is the reciprocal of the demerit factor. For each positive integer $\ell$, we endow the $2^{2 \ell}$ pairs of binary sequences of length $\ell$ with uniform probability measure and study the distribution of their crosscorrelation demerit factors. Sarwate showed that the mean value is always $1$ regardless of length $\ell$. We develop a method for finding an exact formula for the $p$th central moment (for any positive integer $p$) as a function of $\ell$. Formulae for the variance and third central moment ($p=2$ and $3$) are then obtained by hand calculations, while the fourth through sixth central moments are obtained by computer-assisted calculations. Our theory also shows that all the central moments must be strictly positive for $p\geq 2$ and $\ell \geq 3$.

We study the mixing time of the systematic scan dynamics for high-dimensional discrete distributions. This Markov chain updates coordinates sequentially according to a fixed predetermined order, in contrast to the Glauber dynamics that updates coordinates selected uniformly at random. The systematic scan is often favored in practice because it exhibits strong empirical performance, but its theoretical analysis remains far less developed than that of Glauber dynamics. We take a step toward addressing this imbalance by showing that two standard functional notions of weak dependence between the coordinates of the distribution provide strong convergence guarantees for the systematic scan dynamics. First, we show that approximate tensorization of entropy implies optimal $O(\log n)$ mixing time for every scan order under standard marginal, connectivity, and bounded interaction degree assumptions about the distribution. Second, we show that approximate tensorization of variance yields a constant-factor contraction of the variance functional per scan, which in turn implies an optimal $O(1)$ relaxation time for the natural additive and multiplicative reversibilizations of the systematic scan dynamics. Compared with our entropy result, the variance bound improves the dependence on the maximum interaction degree from exponential to quadratic and requires weaker assumptions on the distribution. As concrete applications of our results, we establish optimal $O(\log n)$ mixing of the systematic scan dynamics for bounded-degree antiferromagnetic two-spin systems in the tree-uniqueness region and for the ferromagnetic $q$-state Potts model on square boxes in $\mathbb{Z}^2$ throughout its subcritical regime.

In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with the Arora-Rao-Vazirani rounding gives an $\mathcal{O}(\sqrt{\log n})$ approximation on arbitrary graphs on $n$ vertices. We study this relaxation on finite Abelian Cayley graphs. First we show that when the second normalized Laplacian eigenvalue of $G= \mathrm{Cayley}(\Gamma, S)$ is realized by a Fourier character with image size at most four then $\lambda_2(G)=\mathrm{SDP}_{\mathrm{GL}}(G)=\psi(G)$. Geometrically, a character maps the vertices onto a regular polygon where the squared chord distance satisfies the triangle inequalities exactly when the polygon has at most four vertices. Grouping equal character fibers gives a cyclic quotient where the optimal cut can be found exactly and so the relaxation is exact on finite Abelian Cayley graphs on groups of exponent at most four. Second, we replace each generator $s$ of $S$ by a uniformly random element of its cyclic subgroup (including identity). If $r_s$ is the order of $s$, we let $\alpha(r_s)$ to be the average number of $\pm s$ steps needed to simulate such a move, and let $\rho(S)=\max_{s\in S}\alpha(r_s)$ be its worst case. Full cyclic averaging eliminates character phases and choosing a nontrivial character $\chi^*$ minimizing the auxiliary eigenvalue and taking $K=\mathrm{ker}\chi^*$ gives \[ \psi(G)\leq\psi_G(K)\leq\frac{q^*}{q^*-1} \cdot\rho(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G)\leq 2\rho(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G), \] where $q^*=|\chi^*(\Gamma)|$. If all generator orders are at most $R$, this is an $R/2$ approximation. Finally, we construct an infinite family of finite Abelian Cayley graphs with Goemans-Linial integrality gap exactly $16/15$.

A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardinalities of any two color classes differ by at most one. Stemock conjectured that every $4$-total coloring of a cubic graph of order less than $20$ is equitable. In this paper, we disprove this conjecture: the circular ladder $L_{12}$ admits a non-equitable $4$-total coloring and, moreover, no smaller counterexample exists: order $4$ is vacuous, and every $4$-total coloring of a cubic graph of order $6$, $8$, or $10$ is equitable. We also prove that the same property holds at order $14$. Our proofs rely on a decomposition lemma, which states that, in any $4$-total coloring of a cubic graph $G$, each color class consists of an independent set $S$ together with a perfect matching of $G-S$. We use the lemma to determine all possible color class configurations for orders $12$, $16$, and $18$, and we show that every listed configuration is attained. Finally, we provide a splicing construction showing that, for every even $n\geq16$, some connected cubic graph of order $n$ admits a non-equitable $4$-total coloring. We may conclude that $14$ is the largest order for which every $4$-total coloring of every cubic graph is equitable.

A colorful graph relation enhances the minor relation by merging color sets along contractions and by allowing the removal of colors; it generalizes rooted minors and models problems on graphs with several, possibly overlapping, annotated vertex sets. A graph has the Erdős-Pósa property for minors if and only if it is planar, by a classical theorem of Robertson and Seymour. In this work we determine, for the colorful minor relation, exactly which colorful graphs have the Erdős-Pósa property. Our characterization takes three equivalent forms. The first is structural: the colorful graphs with the property are those that can be drawn with all their colored vertices on one face and whose colors are, in a precise sense, laid out along that face without interleaving. The second is given by an obstruction set: they are those excluding every member of an explicit infinite family $\mathcal{O},$ of which only $\mathbf{O}(|I|^{4})$ members have colors that are a subset of $I,$ for every finite set $I$ of colors. The third is grid-like: they are exactly the colorful minors of unions of particular families of segregated grids, the colorful analogues of the grids that drive the classical proof.

For a finite abelian group $G$ and $k \geq 1$, the generalized Davenport constant $D_k(G)$ is the least $\ell$ such that every sequence over $G$ of length at least $\ell$ has $k$ pairwise disjoint nonempty zero-sum subsequences. A theorem of Freeze and Schmid gives $D_k(C_5^3) \geq 5k+10$ for every $k \geq 2$. We prove the matching upper bound: $D_4(C_5^3)=30$, and hence $D_k(C_5^3)=5k+10$ for every $k \geq 2$, so the Freeze–Schmid bound is attained by $C_5^3$ from $k=2$ onward, as it is by $C_2^3$ and unlike $C_3^3$. The proof is finite and computer-assisted. The remaining case reduces to showing that every zero-sum sequence of length $31$ over $C_5^3$ contains a nonempty zero-sum subsequence of length at most five. A saturation argument confines the multiplicities of a hypothetical counterexample to $\{1,2,4\}$, its support pattern to one of $60$ solutions of two linear equations, and its geometry to one of $78$ rank/plane branches normalized to a standard basis; an exhaustive search exhausts every branch with no survivor. The search was carried out by three independently written implementations, and the branch cover was regenerated by separate programs from the lemmas alone; two further machine-verified values, $D_3(C_5^3)=25$ and $s_{\leq 6}(C_5^3)=24$, enter the second statement, and their records accompany the paper.

We study the job shop scheduling problem with a conflict graph, in which adjacent jobs cannot be processed simultaneously on different machines, with the objective of minimizing the makespan. We establish a polynomial equivalence with a resource-constrained job shop problem having unit-capacity resources and binary resource requirements The problem is strongly NP-hard even on two machines with unit-time operations. For this setting, we derive an optimal-makespan formula and a linear-time algorithm when the conflict graph is a cluster graph, given the clique partition. We also develop a polynomial-time $4/3$-approximation algorithm for arbitrary conflict graphs on two machines when each job has exactly two unit-time operations. For the general problem, we propose four mixed-integer linear formulations, lower bounds, and a genetic algorithm with active, non-delay, and hybrid decoding procedures. Computational experiments on instances derived from the Lawrence and Taillard benchmarks and on randomly generated generalized job shop instances evaluate the proposed methods and show that the genetic algorithm generally improves on constructive heuristics.

Synchronization strings provide deterministic position labels for recovering coordinates after insertions and deletions. Haeupler and Shahrasbi introduced these objects, and subsequent work proved that four symbols suffice for some fixed parameter epsilon < 1, whereas two symbols cannot support arbitrarily long synchronization strings. We resolve the remaining ternary case: every length admits a ternary 2001/2002-synchronization string. Thus three is the exact minimum constant alphabet size. A computer-assisted refinement based on a larger 54-uniform family yields ternary epsilon-synchronization strings for every epsilon > 215/216. The previous four-symbol construction uses a ternary square-free backbone to exclude short repetitions and a fourth symbol to carry long-range synchronization marks. Our main technical contribution is a local-entropy transfer theorem: every square-free block-local source with a positive interval conditional min-entropy rate supports synchronization strings with a fixed gap. We instantiate this theorem using occurrence-wise branching in a Brinkhuis family. Every outcome remains ternary and square-free, while every long interval retains linear conditional min-entropy after all choices outside it are exposed. A deletion-ball estimate converts this entropy into an exponentially small probability of a near-complete common subsequence between adjacent intervals, and an asymmetric Lovasz Local Lemma enforces all interval constraints simultaneously. The same framework also yields exponentially many valid words, synchronization circles, and synchronization within a class of extremal square-free words. Adding constraints on distant intervals gives a Las Vegas construction in expected O(n^2 log^3(n+2)) time.

The way numbers are represented strongly influences which arithmetic structures are easy to see. The prime clockwork is a recursively growing discrete dynamical system: a list of autonomous two-hand clocks driven by one common $+1$ signal. No primes or primality labels are supplied. Starting empty, the process appends a clock of period $n$ whenever none already present rings; the primes are generated internally as its growth times. For each installed prime $p$, the seconds reading $R_p$ advances through $0,\ldots,p-1$, and each return to zero increments the minutes reading $M_p$, which counts completed $p$-cycles. The hands use only increment, comparison, reset, and carry, without explicit mod or div operations. At time $n$, $n=pM_p(n)+R_p(n)$. The valuation readout $V_p(n)=\nu_p(n)$ is generated locally: it is zero when the seconds counter is non-zero (silent state) and otherwise (when the p-clock rings) one plus the earlier valuation addressed by the current minutes reading. The valuation vector gives the integer in unique prime-factorized form. Its coordinates add and subtract under multiplication and division, representing every positive rational uniquely; divisibility becomes weak componentwise order, and unique factorization is natural in this representation. Finite seconds arrays form Cartesian-product state spaces whose common orbit visits every joint state once before repeating; this grand cycle is the order-sensitive dynamical counterpart of the Chinese remainder theorem. The same coordinates expose gcd, lcm, perfect powers, Bézout's identity, and Euler's totient. Rational valuation levels reach certain positive algebraic irrationalities, but not algebraic numbers in general.

This paper studies the problem of fair division of indivisible goods among $k$ groups of $n_1,\ldots, n_k$ agents. We look at the worst downward deviation $\textit{PROP}(n_1,\ldots, n_k)$ of an agent in a group from its $1/k$-share. We improve the bounds of (Manurangsi and Meka, 2026) and show that $\textit{PROP}(n_1,\ldots, n_k) = \tilde{\Theta}(\sqrt{n/k})$, where $n = n_1 + \ldots + n_k$ is the total number of agents. For the proof of the upper bound, we develop novel discrepancy-type tools and, in particular, a way to efficiently work with one-sided discrepancy constraints.

Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal $\alpha$-spanner of a temporal graph with $n$ vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of $\alpha$. While general temporal graphs may not admit sparse temporal $\alpha$-spanners for any value of $\alpha$, temporal cliques are known to admit temporal $(2k-1)$-spanners of size $\widetilde{\mathcal{O}}(kn^{1+1/k})$ for every positive integer $k$. We present a simple recursive algorithm that computes, for every temporal clique on $n$ vertices, a temporal $3$-spanner of size $n^{1+2/\sqrt{\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\widetilde{\mathcal{O}}(n^{3/2})$. We also show that a modified version of our algorithm computes temporal $3$-spanners of size $\mathcal{O}(nL)$ when the lifetime is bounded by $L$, i.e., all time labels are in $\{1,\ldots,L\}$, thus improving the previous bound of $\mathcal{O}(2^Ln\log n)$. Both results are particularly striking in light of the known lower bound of $\Omega(n^2)$ on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime $L\geq 3$. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only $\mathcal{O}(n)$ carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.

For more than 20 years, the Model-RB benchmark frb100-40 remained an open challenge; since 2014, its public record had stood at 99 of 100 variables. We give a directly checkable 100-vertex independent set for its 4,000-vertex graph. Together with a verified partition into 100 cliques of size 40, the witness proves that the maximum independent-set size is 100 and the minimum vertex-cover size is 3,900. The stochastic run that found the witness is kept separate from this proof. We evaluated its added pair and triple repair operators in a preregistered campaign comprising 8,668 valid runs. The primary comparison found no detectable acceleration over base ULSA (hazard ratio 0.967, 95% confidence interval 0.915-1.023; p=0.248), and the factorial ablation reached the same conclusion. On a smaller FRB suite, the group-aware CSP pipeline solved 2,500/2,500 runs, compared with 2,391/2,500 for LibMVC-NuMVC. On frb100-40, full ULSA, base ULSA, and NuMVC each produced 0/56 new certificates. With no events, the planned cross-solver hazard ratios remain unidentified. NuMVC ended with cover size 3,902 in 40 runs and 3,903 in 16. Exhaustive enumeration showed that none of the 108 unique recorded conflict-two states had a strictly improving group-aware CSP neighbor within Hamming radius three. The certificate settles the instance. The experiments characterize the search barrier, and the preregistered comparisons show no heuristic advantage.

Although almost all graphs are asymmetric – having no nontrivial global automorphisms – they may still possess local symmetries in the form of isomorphisms between induced subgraphs, i.e., partial automorphisms. We study such local symmetries via asymmetric depth, defined in terms of the maximum rank of a nontrivial partial automorphism. We prove a tight upper bound on asymmetric depth in the class of planar graphs and identify the extremal graphs: duals of IPR fullerenes attain the maximum already on $47$ vertices. Our main structural result concerns the IPR fullerenes that are neither maximally asymmetric nor symmetric. In such a cage no purely local action realises a low asymmetric depth, and we show that the map which does realise it cannot be confined to a small part of the cage either: neither to a single face, nor behind an interface of at most $5-k$ edges, $k \le 3$ being the deficiency. A cage of asymmetric depth $2$ or $3$ is therefore not asymmetric in one place; it carries a broken symmetry invisible to its automorphism group. Such cages are rare – under $2\%$ of the asymmetric IPR fullerenes at $n = 118$. In all $727$ of them the largest partial automorphism is a near-mirror reflection, which we state as an explicit conjecture. We also extend the asymmetric depth bound to graphs of higher genus.