Papers

We introduce and analyze a new model of graph burning, in which two competing fires (coloured yellow and green) ignite vertices of a given signed graph and propagate along its edges. The boolean sign of an edge determines whether a fire spreading along the edge changes colour or not. In each step, a player ignites a new vertex in a colour of their choice, while previously activated fires continue to spread. Given a signed graph $\Gamma$, the objective is to burn the maximum possible number of vertices in a single colour; the optimal achievable value is called the plurality number of $\Gamma$. We express the plurality number through Hamming distances to a binary code associated with $\Gamma$. In particular, the minimum plurality number over the switching class of $\Gamma$ equals the number of vertices minus the covering radius of this code. Under certain conditions on the signature, we determine exact values of the plurality number of signed paths. By contrast, we prove hardness results for multiple variants of the problem of determining or approximating the plurality number.

We construct near-spanning balanced antidirected trees that fail to embed in highly symmetric tournaments despite the conjectured semidegree condition being satisfied. More precisely, for every sufficiently large odd integer $n$, we exhibit a regular vertex-transitive tournament on $n$ vertices and a balanced antidirected caterpillar on $n-1$ vertices with maximum degree at most $(1+o(1))n/\log_2 n$ that is not contained in the tournament. The host satisfies the strict $k/2$ threshold in both the semidegree and pseudo-semidegree settings, where $k$ is the number of arcs of the target tree. Consequently, this gives counterexamples to the uniform sublinear-degree interpretations of Conjectures~6.8 and~7.6 in Stein's survey (2024). The order $n-1$ of the target is best possible under the strict semidegree hypothesis. We also give a six-vertex balanced antidirected double-star missing from the seven-vertex Paley tournament, and show that seven is the smallest host order for a pseudo-semidegree counterexample with this fixed double-star.

An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $\rho_e^o(G)=\alpha(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively. For chordal graphs, we develop an $O(n^4)$-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an $O(n^4)$-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.

We present a version of the vector balancing problem in which each vector may be given a sign and a permutation of its coordinates. We prove that this vector balancing problem and its corresponding prefix problem admit an explicit bound, and we further show that it is asymptotically optimal in the dimension. Our method of proof is purely geometric.

An assignment of tasks to servers can resist every small improvement and still make tasks wait longer than necessary. We determine exactly how inefficient such an assignment can be when each task requires one unit of service and the eligibility constraints permit all tasks to use distinct servers. For every move size $r$ and maximum current server load $K$, we give a closed formula for the worst ratio between locally optimal and globally optimal total completion time. Local optimality here allows every feasible reassignment changing at most $r$ tasks. Every finite-cap bound is attained on a tree where each task has at most two eligible servers. Thus the worst behavior already occurs under simple eligibility constraints. At load cap two, the exact ratio is $1+1/(r+2)$, attained on a path with $r+2$ tasks. Without a load cap, the worst-case supremum is $3/2$ for single-task moves and approximately $1.294503159$ for two-task moves; its excess above one is $1/(r+2)+O(2^{-r}/r)$ as $r$ grows. The proof uses an explicit rational potential on a comparison graph and matching extremal constructions. These results give sharp guarantees for bounded-size local search on matchable semi-matchings, including exact guarantees under degree bounds.

We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $\kappa>0$, find signs $\sigma_1,\dots,\sigma_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N \sigma_i A_i$ is at most $\kappa\sqrt{N}$. Focusing on the proportional regime $N/d^2\to \tau\in(0,\infty)$ as $d\to\infty$ followed by the small-margin limit $\kappa\downarrow 0$, we characterize the density required by stable offline algorithms and by online algorithms. In the offline setting, we construct a polynomial-time recenter-and-round algorithm that is noise-stable and succeeds whenever $\tau=\Omega(\frac{1}{\kappa^2\log(1/\kappa)})$, along with a matching lower bound for all stable algorithms. In the online setting where each sign must be chosen irrevocably upon observing the corresponding matrix, we determine the exact limiting performance of the Frobenius-greedy algorithm, establishing that it succeeds when $\tau>\tau_{\rm FG}(\kappa)\sim \frac{\pi}{4\kappa^2}$, as well as a matching lower bound for all online algorithms by conditioning on a revealed prefix. At the core of our algorithms lies rotational symmetry, which enables us to transfer Frobenius norm control into operator norm guarantees. Together, our results identify the algorithmic phase transition points for random matrix discrepancy: $\Theta(\frac{1}{\kappa^2\log(1/\kappa)})$ for stable offline algorithms and $\Theta(\frac{1}{\kappa^2})$ for online algorithms. Both thresholds lie far above the satisfiability scale $\Theta(\log(1/\kappa))$, as shown by Maillard~\cite{maillard2025}.

A strong odd $k$-coloring of a graph $G$ is a proper $k$-coloring such that every color appearing in the neighborhood of a non-isolated vertex appears an odd number of times. The minimum $k$ for which $G$ admits a strong odd $k$-coloring is the strong odd chromatic number, denoted by $\chi_{\text{so}}(G)$, of $G$. Given a graph $G$ and an integer $k$, \textsc{strong odd $k$-colorability} problem asks whether $G$ admits a strong odd $k$-coloring. It is known that STRONG ODD $k$-COLORABILITY is NP-complete in general graphs. In this paper, we prove that the problem is NP-complete on perfect elimination bipartite graphs for $k\geq3$, which is a subclass of bipartite graphs. Furthermore, we show that $\chi_{\text{so}}(G)$ is inapproximable within a factor of $O(n^{\frac{1}{2}-\varepsilon})$ for every $\varepsilon>0$. On the positive side, we obtain a linear time algorithm to compute an optimal strong odd coloring for block graphs. From a parameterized perspective, we present an FPT algorithm for STRONG ODD $k$-COLORABILITY when parameterized by treewidth. Moreover, we show that the problem cannot be solved in time $(k-\varepsilon)^{\texttt{tw}}n^{O(1)}$ for every $k\geq3$ and $\varepsilon>0$ when parameterized by treewidth under SETH. Furthermore, we show that STRONG ODD $k$-COLORABILITY does not admit a polynomial kernel when parameterized by feedback vertex set. Lastly, we prove that STRONG ODD $k$-COLORABILITY is W[1]-hard when parameterized by clique-width.

In 1965, D. H. Lehmer conjectured that the permutations of every multiset admit an imperfect Hamiltonian traversal by adjacent swaps: a walk in the neighbor-swap graph that visits every word, with some words visited twice in order to reach a neighbor and return. The question is posed as an unsolved research problem in Knuth's Art of Computer Programming. Verhoeff (2017) chose the stutter words, in which every domino is a double, as the words to be reached this way, and reformulated the conjecture as the Hamiltonicity of the graph $N(S)$ on the non-stutter words, with two exceptional families — binary signatures with an odd multiplicity, and the permutations of $(2k,1,1)$ — that admit a Hamiltonian path but no cycle. This article proves the reformulated conjecture, and with it Lehmer's conjecture. The key structure is a partition of the words into hypercubes: the swaps inside dominoes turn each class of words with the same domino contents into a hypercube, and the stutters are exactly the $0$-dimensional classes. When every multiplicity is even, Hamiltonian cycles of the hypercubes are glued along a spanning tree, with no finite check. The case of exactly one odd multiplicity reduces to the all-even case and to a theorem of Stachowiak (1992), the one inherited Hamiltonicity input, which also settles two or more odd multiplicities. The only finite ingredients are two explicit cycles, of 28 and 84 words. Every construction is implemented in Python and checked against brute-force graphs, and the proof is formalized in Lean 4 over Mathlib.

In this work, we study bilevel optimization problems where all variables are integer, all constraints and the leader objective function are linear, and the follower objective function is non-convex quadratic. Relying on bilevel-free sets derived from improving directions, we develop a disjunctive cut approach to exclude bilevel-infeasible solutions within a branch-and-cut algorithm. We show that our disjunctive cuts can be obtained by solving a cut generating linear program. Furthermore, we discuss conditions that allow the number of disjuncts in the cut generating linear program to be reduced, and we propose several strategies to identify improving directions and generate disjunctive cuts efficiently. We evaluate various aspects of the proposed branch-and-cut algorithm on both convex instances from the literature that fit our setting and new non-convex instances and compare the performance of our best approach with existing state-of-the-art approaches, which we significantly outperform.

We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with $\smash{O(n^{4/23}) = O(n^{0.17391\ldots})}$ colors, improving on the recent bounds of $O(n^{0.19539})$ by Bansal, Huang, and Lee and Narang and Tang who obtained $O(n^{(13-\sqrt{97})/18+\epsilon})=O(n^{0.17506\dots + \epsilon})$ colors for every fixed $\smash{\epsilon>0}$. To prove our result, we start from a fixed-level semidefinite relaxation, where we use a finite-depth recursion on Gaussian covers. Fixing a root vertex, we group vertices by correlation with the root vector. Here, each step extends a cover of directions by one edge and transfers it to a successor group. Our key analytic ingredient is a variance bound for Gaussian maxima: for a maximum of $m\geq 2$ centered linear forms with coefficient norms at most $r$, mean $\mu$, and variance $v$, we prove $v\leq r^2-\mu^2/(2\log m)$ using Chen's Gaussian convexity theorem. Together with a variance-scale lower-tail estimate, this controls the threshold loss at each extension, which shows that root-conditioned vector colorings can either extract a large independent set from a group or bound its size, forcing a contradiction after constantly many steps. The resulting sparse-case guarantee combines with the dense progress bound of Kawarabayashi, Thorup, and Yoneda, and the recursion's numerical inequalities are verified via rational interval arithmetic.

Let $K_t$ be obtained by attaching a pendant path of length $t$ to a fixed rooted graph $K$. We prove that $\mathrm{Mo}(L(K_t))-\mathrm{Mo}(K_t)$, the difference between its line-graph and original Mostar indices, is exactly affine on each parity class beyond a sharp uniform cutoff. The slope depends on distance-level neighbor counts and is positive for every non-bipartite core. Triangle chains give infinitely many graphs with $\mathrm{Mo}(L(G))>\mathrm{Mo}(G)$ at every positive cyclomatic number $c$, with maximum degree three, resolving Alex-Indulal Problem 3.3. At zero slope, a cactus branch-mass formula decides equality; identical vertex profiles need not give identical intercepts. Fixed cores giving equality for all sufficiently long attachments exist exactly when $c$ is odd. Maximum degree three suffices, and at every even $c$ a binary-tree construction gives equality on one eventual parity class.

We introduce the quantum Černý complexity $\mathrm{qc}(w)$ of a binary word $w$: the least dimension $d$ for which there exist quantum channels $A_0,A_1$ on $d\times d$ density matrices and a start state $\rho_0$ such that $w$ is the unique shortest word whose associated channel is constant on the reachable set. We show that $2\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil$ for every nonempty $w$, a quadratic saving over the classical analogue, and that constant words are extremal: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceil$. In contrast, $\mathrm{qc}(01^n0)=2$ for every $n\ge 1$, realized by a single qubit whose rotation angle acts as a counter; consequently there is no quantum analogue of the Černý function, and $\mathrm{qc}$ is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant $\mathrm{qcp}$ in which the synchronization target is required to be a pure state. We prove that in dimension $2$ no word of length at least $2$ can be a unique shortest synchronizing word with pure target, and we exhibit an explicit qutrit instance, combining a coherent rotation with a measure-and-funnel channel, achieving $\mathrm{qcp}(01^n0)=3$ with target a computational basis state and with synchronization holding universally over all input states. Thus purity of the reset state costs exactly one dimension on this family. We also observe that $\mathrm{qc}$ is computable, by reduction to the first-order theory of the reals.

We present a new lower bound on the number of lattice points of all totally unimodular polytopes, generalizing previous lower bounds on contingency tables, integer flows, and beyond. Our bound is based on the Gurvits capacity convex optimization problem, and thus our result implies an efficient deterministic algorithm for approximate counting of the lattice points up to an explicit exponential factor. We achieve our bounds by showing that the associated generating polynomials fit into a new general class of log-concave polynomials called VLC ("variable-wise log-concavity”). This also implies a conjecture of Ferroni and Higashitani on the evaluations of the Ehrhart polynomials of unimodular polytopes. The essential ingredient for these results is the resolution of Barvinok's log-concavity conjecture for contingency tables on lines, which was proven using ChatGPT 6 Astra. We conjecture a generalization of Barvinok's conjecture, which we believe will lead to stronger and more general bounds.

Routing unknown quantum information across distributed communication networks requires autonomous, measurement-free mechanisms to prevent wave-function collapse. Szegedy quantum walks provide a mechanism for spatial state transport. The conventional walks on unweighted graphs suffer from severe back-reflection, spatial dispersion, and channel crosstalk. In this paper, we introduce a deterministic topological quantum routing architecture based on coined Szegedy quantum walks on edge-duplicated signed graphs. By treating edge signs as localized phase shifts within a balanced coin reflection, we enforce an exact zero back-scattering condition across routing nodes. We demonstrate deterministic Perfect State Transfer (PST) with unit fidelity at exact arrival times across fundamental archetypes, including the signed dumbbell switch $D_{2m,0,2n}$ and scalable glued binary trees. Furthermore, we analyse routing performance under realistic open-system amplitude and phase damping noise channels.

The analysis of observable phenomena (for instance, in biology or physics) allows the detection of dynamical behaviours. If the conditions are ideal and the number of observations is sufficient, we can represent these phenomena by a dynamical system, also called a functional digraph, that is to say a graph where each node has out-degree exactly one. Up to isomorphism, these dynamical systems, equipped with disjoint union as addition and direct product as multiplication, form a commutative semiring. Several previous studies on this semiring have aimed to establish algebraic properties (primality, injectivity) or complexity results (division, factorisation). However, no work has yet been conducted on graphs derived from imperfect observations that result in missing transitions or nodes, in other words, in cases where each node in the graph has an out-degree of at most one. In this case, we say that the system is partial. In this paper, we show that partial dynamical systems, up to isomorphism and equipped with the same addition and multiplication, still form a commutative semiring. We then characterise the prime elements of this semiring, which differ from those of the semiring of dynamical systems. Finally, we highlight two properties shared by both semirings. First, injective univariate polynomials admit the same characterisation in both. Second, division can be computed in polynomial time for partial dynamical systems if and only if it can be for dynamical systems.

Effective spatial organization of post-disaster shelter camps is essential for ensuring access to basic services while making efficient use of limited space and resources. In this paper, we propose a graph-theoretic framework for shelter-camp facility placement based on rainbow $k$-domination and Roman domination. Rainbow $k$-domination models the simultaneous accessibility of distinct facility types, such as sanitation units, kitchens, water points, and schools, whereas Roman domination is used to represent services with different capacity levels, illustrated through Wi-Fi deployment. We present an $O(nk)$-time algorithm for finding a minimum rainbow $k$-dominating set of a tree with $n$ vertices, which is linear in $n$ for fixed $k$, and computational experiments confirm its scalability on large instances. For general graphs, we establish new lower and upper bounds on the rainbow $k$-domination number. We further investigate its relationship with Roman domination, derive structural properties of graphs attaining the extremal equality between the two parameters, and prove that recognizing such graphs is NP-hard. These results provide a theoretical foundation for domination-based approaches to facility placement in post-disaster shelter planning.

For an $n$-vertex undirected, unweighted graph $G=(V,E)$ and a positive integer $k$, we present new spanner constructions with $O_k(n^{1+1/k})$ edges that achieve nearly optimal guarantees for all distances $d\le k$. Specifically, we construct a spanner $H\subseteq G$ with $O(n^{1+1/k}+(k+d\log d)n)$ edges, ensuring that any pair at original distance at most $d$ satisfies $\mathrm{dist}_H(u,v)\le 2k+O(d\log d)$. Equivalently, the multiplicative stretch for pairs at distance $d$ is $2k/d+O(\log d)$. In particular, setting $d=k/\log k$ yields an $(O(\log k),O(k))$-spanner with $O(n^{1+1/k}+kn)$ edges. For comparison, Ben-Levy and Parter (SODA'20) obtained, for every fixed $\varepsilon>0$ and sufficiently large $k$, an $(O(k^\varepsilon),O_\varepsilon(k))$-spanner with $O_{\varepsilon,k}(n^{1+1/k})$ edges. Our result improves the multiplicative stretch from $O(k^\varepsilon)$ to $O(\log k)$ while keeping the additive term linear in $k$, bringing us closer to the goal of $(O(1),O(k))$-spanners. Furthermore, Ben-Levy and Parter obtained multiplicative stretch $O_\varepsilon(k/d)$ for distances $d\le k^{1-\varepsilon}$, for every fixed $\varepsilon>0$, and an explicit bound of $7k/d$ for $d\le\sqrt{k}/2$. We achieve $2k/d+O(\log d)$, which is $(2+o(1))k/d$ whenever $d=o(k/\log k)$. Our second result is an improved construction of $k$-hybrid spanners, which guarantee stretch $2k-1$ for adjacent pairs and $k$ for non-adjacent pairs. Parter's original construction uses $O(k^2 n^{1+1/k})$ edges; we achieve the same guarantees with $O(n^{1+1/k}+kn)$ edges, removing the $k^2$ factor from the $n^{1+1/k}$ term. For every fixed $k$, our edge bound is optimal up to a constant factor under Erdős' girth conjecture.

Let $W_s=K_1+C_{s-1}$ denote the wheel on $s$ vertices. We give structural proofs that $R(C_{14},W_{11})=27$ and $R(C_{15},W_{11})=29$. Together with the theorem of Chen et al. for $n\ge16$, these equalities give $R(C_n,W_{11})=2n-1$ for every $n\ge14$. The two boundary values were included in an earlier survey announcement. We also give structural proofs of $R(C_8,W_7)=15$, $R(C_9,W_7)=17$, and $R(C_8,W_9)=15$. The common starting point is a Hamilton-connected core lemma. For the eleven-vertex wheel, bounds on vertex connectivity and on the matching number of a bipartite graph associated with a local cycle yield a vertex cut of order nine. Paths with prescribed endpoints then rule out every possible pair of orders of the two remaining vertex sets. For the smaller wheels, we use the structure of critical cycle colorings and local cycle-shortening arguments. We also give complete structural classifications of the $(C_8,C_6)$- and $(C_9,C_6)$-critical colorings, recovering the previously reported counts 24 and 26. All proofs are combinatorial and use no exhaustive graph enumeration.

For a connected graph $G$ with at least one edge, the eternal connected vertex cover number $ecvc(G)$ is the minimum number of guards that can maintain a connected vertex cover after every response to an arbitrary sequence of edge attacks. Denote the minimum size of a connected vertex cover by $cvc(G)$. It is known that $cvc(G)\leq ecvc(G)\leq cvc(G)+1$. A necessary condition for $ecvc(G)=cvc(G)$ is that every vertex belongs to some minimum connected vertex cover. We show that this condition is not sufficient: there exists a $32$-vertex graph $G$ that has $cvc(G)=19$ and $ecvc(G)=20$, although every vertex of $G$ belongs to some minimum connected vertex cover. For connected graphs with minimum degree at least two, we establish the sharp bound $cvc(G)\geq 2|V(G)|-|E(G)|-1$ and $\mathcal F$ denotes the class attaining equality. We prove that $G\in\mathcal F$ if and only if the vertices of degree at least three induce a forest. Within $\mathcal F$, the conditions $ecvc(G)=cvc(G)$, membership of every vertex in some minimum connected vertex cover, and the presence of at least two degree-two vertices on every cycle are equivalent. As applications, we obtain $ecvc(G)=cvc(G)$ for full subdivisions of connected graphs of minimum degree at least two and for minimally $2$-connected graphs. In both the families, every minimum connected vertex cover is an eternally winning configuration. This is not true in general for graphs outside $\mathcal{F}$, we show one example of such a graph.

Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to $n$ agents in connected bundles so that the cost of every agent is at most its connected maximin share; for goods, this is a theorem of Bouveret, Cechlárová, Elkind, Igarashi, and Peters. We answer the question affirmatively, even for monotone costs. The answer follows from a combinatorial theorem: if $\mathcal P_1,\ldots,\mathcal P_k$ are partitions of the vertex set of a finite tree, each into at most $k$ connected parts, then the vertex set can be split into disjoint sets $B_1,\ldots,B_k$, some possibly empty, such that each nonempty $B_i$ is connected and contained in a part of $\mathcal P_i$. Equivalently, if each of $k$ colours occurs on at most $k-1$ edges of a tree, then the vertices can be partitioned into connected sets labelled by distinct colours, none containing an edge of its own colour; in particular, one can choose for every colour a component of the forest obtained by deleting that colour so that the chosen components cover the tree. The bound is already best possible for paths, and for additive costs, the theorem is equivalent to the fair-division statement. The proof reduces the problem to inward partitions of oriented trees, which we obtain from the colourful KKM theorem on a simplex of edge weights, using a leaf-elimination labelling that remains compatible when weights vanish. We also give an algorithm running in time $k^{O(k)}$ plus polynomial time.

Evaluations of graph reconstruction by language models typically report a single aggregate distance between the original and the reconstructed graph. We prove that for the Wasserstein distance between Laplacian spectra such a summary is bracketed by two edge counts, the net change in edge number from below and the symmetric difference from above, each scaled by $2/n$ where $n$ is the number of vertices. The bracket is sharp: its two ends coincide exactly when the reconstruction only adds edges or only deletes them, and on that class the distance is a rescaled edge count that says nothing about which edges changed. When the ends differ, the residual between the distance and the lower end is positive only if the reconstruction both invented and lost edges, which turns it into a certificate of mixed editing computable from the reported summaries alone. We characterize these regimes in 135 reconstructions produced by three open-weight models over 45 synthetic graphs. Seventy-seven outputs are one-sided and 29 mixed outputs have $X > 0$, including cases where edge count is exactly preserved while nineteen edges were simultaneously invented and lost. The three models differ in editing policy, ranging from copying the input to attempting completion at the cost of large hallucination volume, a distinction that aggregate distortion does not reveal.

A graph is $K_3$-irregular if its vertices belong to pairwise distinct numbers of triangles. We prove that no $8$-regular $K_3$-irregular graph exists, settling the last unresolved case. Following the initial discovery of such graphs for regularities $r \in \{10,11,12\}$ (Stevanovi'c et al., 2024), our previous work (Hak et al., 2025) showed that no such graphs exist for $r \le 7$, provided the first example for $r=9$, and proved that any $8$-regular candidate must have between $17$ and $22$ vertices. We exclude these possible orders for $r=8$ by combining careful analysis of triangle degrees with integer linear programming techniques. Meanwhile, a recent construction (Zhang, 2026) established that regular $K_3$-irregular graphs do exist for all $r \ge 9$. Together with our results, this establishes that an $r$-regular $K_3$-irregular graph exists if and only if $r\geq 9$.

A majority coloring of a graph $G = (V,E)$ is a coloring of $V(G)$ such that, for each vertex $v$, the number of neighbors of $v$ with the same color as $v$ is at most $deg(v)/2$. A strong majority coloring is a coloring of $V(G)$ such that, for each vertex $v$, every monochromatic subset of $N(v)$ has size at most $deg(v)/2$. The (strong) majority coloring game is a two-player Maker-Breaker-type game, in which two players Alice and Bob color the vertices of a graph $G$ alternately, maintaining the (strong) majority condition. The least number of colors such that Alice has a winning strategy in such a game is called the (strong) majority game chromatic number of the graph $G$, denoted $\mu_g(G)$ (or $\mathrm{Maj}_g(G)$ for the strong version). For the majority coloring game, we prove that $\mu_g(G) \le 3$ under the following cases: $G$ is a $2$-caterpillar, $G$ is a rooted tree with all leaves at depth $k \le 4$, and $G$ is a subdivision of some graph. The latter resolves a problem posed by Bosek–Grytczuk–Jakóbczak in 2019, who also asked whether $\mu_g(T) \le 3$ for every tree $T$. For the latter question, we discuss various difficulties that arise when natural strategies are attempted by Alice to win the majority coloring game on trees. We include a comparison with the marking game and relaxed coloring game on trees, and with the majority coloring game on locally finite acyclic graphs $G$ with $\delta(G) > 1$. For the strong majority coloring game, we compute $\mathrm{Maj}_g(C_n)$ exactly for each cycle $C_n$, $n \ge 3$. We also initiate the study of the computational complexity of the strong majority coloring game; specifically, we prove that the decision version of the Strong Majority Game Chromatic Number problem is PSPACE-complete. We also show that the Strong Majority 2-Coloring problem is NP-complete on Eulerian graphs.

Covers in hypergraphs are frequently studied to capture various forms of dependence between hyperedges. For example, even covers–which check if each vertex appears in an even number of hyperedges–have found much success recently in the study of locally decodable codes. Inspired by a recently-emerging line of work on the non-redundancy of constraint satisfaction problems (CSPs), we introduce and study two novel families of covers of hypergraphs which are stricter than even covers: Abelian covers and Catalan covers. Abelian covers are similar to even covers, except that arithmetic is now done over the integers rather than modulo 2, allowing us to capture dependences over arbitrary Abelian groups. Catalan covers capture the behavior of non-Abelian groups by only allowing local cancellations in a sequence of hyperedges. We prove three main results about Abelian and Catalan covers. First, using tools from lattice theory, we show that any $r$-uniform hypergraph with $n$ vertices and $n \log(r)$ hyperedges has an Abelian cover. Second, using tools from algebraic topology, we show that in any $3$-uniform hypergraph, Abelian covers and Catalan covers are equivalent; thereby showing that Catalan covers emerge after $O(n)$ hyperedges in $3$-uniform hypergraphs. Finally, using the theory of nilpotent groups, we show that there exists a $4$-uniform hypergraph which has an Abelian cover but not a Catalan cover. Collectively, these results exactly characterize the reach that Abelian covers have in deducing dependences in hypergraphs. As our primary application, we show that any arity-$3$ CSP with an infinite-domain Mal'tsev extension has linear non-redundancy. This implies near optimal streaming, sparsification, and kernelization algorithms for this family of CSPs. Previously, such a result was only known for the much simpler case of arity-$2$ CSPs.

For a graph $H$, $\langle H \rangle$ denotes the class of all subdivisions of $H$ and $tw(H)$ denotes the treewidth of $H$. In this paper, we prove the following. For $k\geq 1, R\geq 1$, let $G,H$ be two graphs such that strong isometric path complexities (Chakraborty et al. [Disc. Math., 2026]) of both $G$ and $\langle H \rangle$ are at most $k$, and $G$ admits an honest, “nicely rooted” $R$-bounded $H$-partition. Then, there is a graph $F$ with $tw(F)\leq tw(H)$ such that $G$ admits a $(1,33\cdot R\cdot k^2)$-quasi-isometry to $F$. Using results of Albrechtsen, Distel, and Georgakopoulos (2025), we also obtain that $K_{2,t}$-asymptotic minor-free graphs admit quasi-isometries with additive distortion to $K_{2,t}$-minor-free graphs. This answers an open question raised by the above authors. As part of our proof, we combine the graph-partition based method and the layering partition based method (Chepoi et al. [Discrete Comput. Geom. 2012]) to obtain additive quasi-isometry when both the source and all subdivisions of the target graph have bounded strong isometric path complexity.

We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. Optimal truthful auctions may be randomized and complicated. We analyze the approximation ratios of three simple deterministic auctions: selling all items separately, selling them as a single grand bundle, and choosing the better of the two. Our technical cornerstone is a nonlinear mathematical programming formulation of the worst-case approximation ratio of selling separately, in discrete auctions where values lie in the grid $\{0,1/K,2/K,\dots ,1\}$. For two iid items, we construct novel tight Lagrangian dual certificates that determine this ratio exactly for any discretization parameter $K$. Taking $K\to\infty$, we obtain the tight bound $1+W(1/e)\approx 1.278$ in the continuous-valued setting, where $W$ denotes the Lambert-W function, closing the $[1.278,1.368]$ gap from the work of Hart and Nisan [EC'12, JET 2017]. For $m\geq2$ independent items, a different dual construction gives an upper bound on the approximation ratio of selling separately in terms of basic statistics of the item values. Combining this bound with new inequalities relating optimal revenue (REV), separate-selling revenue (SREV), and grand-bundle revenue (BREV), we derive improved guarantees for all three auctions. Most notably, we prove \[REV\leq 3 \max\{SREV,BREV\},\] improving upon the long-standing $5.2$ factor of Ma and Simchi-Levi [arXiv 2015, AISTATS'21] and the $6$ factor of Babaioff, Immorlica, Lucier and Weinberg [FOCS'14, JACM 2020]. For iid items, we also prove $REV\leq 4.18 BREV$.

Bourneuf, Charbit and Thomassé [BCT25] showed that the domination number of a tournament can be bounded as a function of its fractional dichromatic number. The function proved was exponential and the tools were based on VC-dimension. In this paper, we present two new proofs of this theorem. The first proof is based on a reduction to the problem of bounding the domination number of a $(1/2-\epsilon)$-majority tournament, for which [BCT25] and Charikar, Ramakrishnan and Wang [CRW26] gave tight bounds. This proof yields the same exponential bound on the domination number as in [BCT25]. The second proof gives a quasilinear bound for the domination in terms of the fractional dichromatic number. It was obtained via AI and was inspired by the recent book proof of the existence of a Condorcet Winning Set of size five due to Ramakrishnan [Ram26].

Spencer's 1985 “six standard deviations suffice” theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4 < 2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential function to a vertex of the cube. We also show that, for every power of two $n \ge 2^{50}$, there exists a matrix $A \in \{-1,1\}^{n \times n}$ such that $\|Ax\|_\infty >1.0000002\sqrt{n}$ for every choice of signs $x \in \{-1,1\}^n$. The construction simply replaces a $2^{-22}$ fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the $\sqrt{n}$ lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.

When a vertex is selected as the most damaging single attack target under one damage objective, how much of the optimal damage under a different objective does it retain? We study this for the three objectives commonly used in critical node detection – pairwise connectivity (PC), size of the largest surviving component (LCC) and number of components (NC) – for single-vertex attacks on connected graphs, with the attacked vertex counted in the damage and ties resolved optimistically. For the pair PC, LCC the loss is bounded: a PC-optimal vertex retains at least a $2-\sqrt2$ fraction of the optimal LCC damage, an LCC-optimal vertex at least 2/3 of the optimal PC damage, and both constants are best possible. Neither bound depends on the choice among tied optimal vertices or on whether the attacked vertex is counted, and both remain valid as lower bounds for attack sets of any fixed size. For the four directions involving NC no positive constant exists; explicit families have ratios decaying like 1/k, and no single attack set retains a positive fraction of all three optima uniformly. We also determine the smallest orders at which the sets of optimal vertices become disjoint: 7 for LCC/NC, 8 for PC/NC, 9 for PC/LCC and 11 for all three pairwise, with trees realising the triple separation for every n>=11; these values rest on an exhaustive enumeration of the 11,989,762 connected graphs with 3<=n<=10. Finally, the most critical vertex in a Birnbaum-type sense may depend on the failure probability: a six-vertex graph, of smallest possible order, changes leader once, at $p^*=3-\sqrt5$. Adding universal vertices lifts the budget-one examples to every fixed budget, so over all connected graphs the same constants are optimal at every fixed budget; behaviour within restricted classes such as trees is left open.

In this paper, we investigate three fundamental convexity parameters of graphs under cycle convexity, namely the Helly number, Radon number, and rank. We first study the computational complexity of these parameters. For each of these parameters, we consider the associated threshold decision problem of determining whether the parameter of a given graph is at least a prescribed integer. We establish that all three problems are $\NP$-hard and $\W[1]$-hard when parameterized by the threshold. Moreover, we strengthen these results by showing that the $\NP$-hardness persists even when the input is restricted to planar graphs of maximum degree at most $6$. We also focus on the structural properties of connected graphs corresponding to extremal values of these parameters. In particular, we characterize the graph classes for which the three parameters attain the values $n-1$ and $n-2$, where $n$ is the order of $G$.