Papers

Edge deletion problems ask for the fewest edges whose deletion gives a graph with a specified property. We study two such problems on block graphs. First making the graph claw-free, and second making it a line graph. Since every line graph is claw-free, the second problem is at least as difficult as the first. We show that on block graphs the two optimum values are always equal, and both are attained by the line graph of a forest. The main step is a completion argument, in which starting from any claw-free solution, we put back edges to get some nice structure inside each block still maintaining the claw-free property. This reduces both edge-deletion problems to the same problem of selecting vertices within the blocks of the input graph. We solve it by dynamic programming in $O(n+m)$ time, which also produces an optimal deletion set and a forest whose line graph is what remains after the completion argument. We also extend the method to $K_{1,r+1}$-free edge deletion for every fixed $r$.

The first major step in the theory of graph minors of Robertson and Seymour was the grid theorem, a fundamental duality result describing that any graph of sufficiently high treewidth must contain a large grid as a minor. Since this pioneering work, multiple grid theorems have been established in structural graph theory, linking various width parameters of combinatorial objects with the non-existence of grid-like obstructions. In particular, Kawarabayashi and Kreutzer [STOC'15] proved a variant of the grid theorem for directed graphs that links directed treewidth with the non-existence of topological minors of large cylindrical walls. On the other hand, to study immersions of undirected graphs $-$ another containment relation that focuses on edge-disjointness, rather than vertex-disjointness $-$ Wollan [JCTB'15] introduced a parameter, tree-cutwidth, and proved that it is dual to immersions of large walls. In this work, we present a version of Wollan's parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth, establishing that it is dual to directed immersions of large cylindrical walls.

Partially optimal assignments (also called persistencies) allow combinatorial optimization problems to be reduced by fixing a subset of variables to values consistent with at least one optimal solution. For the quadratic unconstrained binary optimization (QUBO) problem, such assignments can be computed efficiently via autarkies of quadratic posiforms. However, the largest autarky domain and thus the number of fixed variables can depend on the specific posiform representation. We show that every quadratic posiform with the greatest possible constant term (the roof-dual bound) yields the largest autarky domain obtainable from any quadratic posiform. By computing such a roof-dual-optimal quadratic posiform and a corresponding autarky with largest domain in polynomial time, one can therefore attain the maximum partial optimality obtainable by quadratic posiform autarkies in polynomial time. This justifies the computation of roof-dual-optimal quadratic posiforms and corresponding autarkies in popular polynomial-time algorithms and establishes that finding additional partial optimality in QUBO requires going beyond autarkies of quadratic posiforms.

This work focuses on planning daily routes for a group of employees of a condominium company. Given a set of employees and a set of customers with pre-scheduled visits, we want to build doubly-open routes to guarantee visits to all customers, ensuring that each customer is visited by an employee with the appropriate skills to carry out the required activity. The travel times between customers and the service time in each customer are known. The problem includes time windows for visiting customers, each employee has a maximum working time, and the daily working period is between 9 AM and 6:30 PM. The routes respect the lunch break period if they extend from morning to afternoon, which means that lunch break can be avoided if the route is fully completed in the morning or in the afternoon. The aim is to minimize the distance covered by all routes with a penalty for including lunch breaks. The distances and times between customers are collected via an API to Microsoft Azure; and the solutions are then displayed on Bing Maps. The results obtained show the operational advantages of an efficient and effective vehicle routing planning in a specific condominium management company. The model can be extended to other service provider companies.

Let $A_q(n,d)$ denote the largest size of a code of length $n$ and minimum Hamming distance $d$ over an alphabet of $q$ symbols. For fixed $q\ge2$ and $d\ge4$ we construct codes with redundancy $n-\log_q A_q(n,d)\le(d-3)\log_q n+O(\sqrt{\log n})$ for all large $n$. No algebraic structure is imposed on the alphabet, and the codes are not linear. For $d=4$ and $d=5$ the coefficient of $\log_q n$ matches the Hamming bound, so the redundancy is determined up to lower-order terms. At distance four the codes are provably better than every linear code: by the polynomial-method bound for cap sets, $\mathbb{F}_q$-linear codes with $q>2$ require a strictly larger coefficient in front of $\log_q n$. The construction imposes moment checksums over an auxiliary finite field, as BCH codes do, but one fewer than the distance would normally require. The affine-line theorem from prior work describes the dependencies left by these checks. We exclude them by placing the code positions inside a specially structured subset of the field, built from Behrend's sphere construction with the help of algebraic number theory.

Consider a directed graph G and the (generally infinite) set Walks(G) of the walks in that graph. We are interested in ordering Walks(G) as w1, w2,... in a way that ensures that each walk is obtained from the previous one by a bounded number of elementary operations, namely, push operations (which add a new edge at either end of the walk) and pop operations (which remove the first or last edge of the walk). Our goal is to optimize the aforementioned bound, when it exists, in particular when imposing the additional requirement that walks must be ordered in increasing order of length. To this end, we introduce a condition on graphs inspired by earlier work, called inner-connectedness, which is testable in linear time; we show that inner-connected graphs are precisely those which admit bounded walk orderings. Focusing on such graphs, we then introduce and study the pp-rank and the pp-increasing-rank. Namely, the pp-rank of a graph is the best possible bound on the number of push-pop operations in a bounded walk ordering for that graph; and the pp-increasing-rank is the same where we further impose that shorter walks appear before longer walks in the ordering. We show that the pp-rank of inner-connected graphs is in fact always bounded by 3. The pp-increasing-rank of inner-connected graphs is also always finite, but it can be up to linear in the input graph. More precisely, we show that the pp-increasing-rank is related to a new parameter we introduce, the peripherality of graphs. In particular, for cyclic graphs, peripherality is related to the pp-increasing-rank up to multiplicative and additive constants. We last study how to compute these parameters, and show that while peripherality can be computed in polynomial time, the pp-increasing-rank itself is generally NP-hard to compute.

Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.

Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman–Mathias collusion-avoidance criterion. While the Vapnik–Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.

We construct an approximate sampler for finite doubly free-boundary Macdonald rail-yard processes with Macdonald, boundary, and edge parameters in $(0,1)$. The construction allows arbitrary finite sequences of additions and removals of horizontal or vertical strips and all four boundary types. It reverses a finite commutation–reflection history from a partition sequence whose entries are equal, with the common partition weighted by both boundaries. We derive local reconstruction kernels from the skew Cauchy, Littlewood, and branching identities. Bulk and boundary updates combine integer increments with conditional shape sampling at a prescribed size; same-sign swaps use finite conditional resampling. For $K$ reflection periods and an initial partition-size cutoff $M$, the algorithm terminates almost surely and samples the resulting approximating law exactly. We prove total variation convergence to the target process as $K,M\to\infty$ and give explicit bounds for both truncation errors, decaying geometrically in the cutoffs for fixed input parameters. Under fixed parameter bounds, we also bound the expected operation count of direct enumeration in a unit-cost model. We further construct an exact rejection sampler for the initial partition law without a size cutoff or evaluation of its normalizing constant. Using this sampler removes the size-truncation error, leaving only the error from the finite reflection history.

In the Hunters and Rabbit game, hunters shoot at a set of vertices at each round, while an invisible rabbit must move along an edge. We prove that deciding whether a given number of hunters can guarantee capture is PSPACE-complete, even on simple bipartite graphs. The reduction uses intersection nonemptiness for inverse finite automata: one common word must put all automata in accepting states simultaneously. A clique acting as a safe haven and two families of guards force every winning strategy to simulate common transitions. Existing transformations remove the restriction on the rabbit's initial positions and yield PSPACE-completeness for the directed game with one hunter, even on oriented graphs with positive minimum outdegree. Adjusting the guard sizes also proves PSPACE-completeness of the firefighting game, in which the rabbit may remain at its current vertex.

In a recent breakthrough, Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva (arXiv:2203.00671) designed the first almost-linear-time algorithm for minimum-cost flow. Their approach uses an Interior Point Method (IPM) to achieve complexity $m^{1+o(1)}\log U \log C$. However, the $m^{1+o(1)}$ factor hides intricate recursive data structures, large constants and multiple log factors. In this paper, we give an implementation following the core ideas of their IPM with practical data structures and empirically obtained decision rules. We compare our solver with the cost scaling and network simplex solvers of LEMON on the instance families of the DIMACS Flow Challenge 2.0 core benchmark. Our implementation scales competitively on five of twelve families and better on two. On grid_wide we observe close to linear scaling: $m^{1.04}$ against $m^{1.48}$ for LEMON. We read these results as first evidence that the almost-linear-time framework can be relevant in practice, discuss our insights gained during the implementation process, and motivate where future work should focus to bridge the theory-practice gap.

I study a dynamic pricing problem in which a seller with limited inventory must sequentially price a perishable product for arriving customers with heterogeneous valuations. The key difficulty lies in balancing immediate sales against future opportunities under capacity constraints and stochastic customer valuations. I propose a simple, interpretable, and asymptotically optimal dynamic pricing algorithm, called Dynamic Run-Out Pricing (DROP), that adjusts prices in real time based on current inventory and anticipated future demand. Under the assumption that customers' valuations follow bounded or exponential distributions, our theoretical results show that DROP's expected revenue converges to the optimal revenue as market size grows. Unlike traditional notions of near-optimality, where the ratio of the algorithm's revenue to the optimal revenue converges to 1, I show that the absolute difference between the two revenues converges to 0 as the market size increases, underscoring the algorithm's effectiveness. Furthermore, I extend our analysis to heavy-tailed valuation distributions, specifically the Pareto distribution, where standard run-out heuristics severely underprice inventory by ignoring the value of waiting for extreme valuations. To correct this, I introduce the Tail-Aware DROP (TA-DROP) heuristic, which intentionally inflates prices to protect inventory, and I prove that it restores asymptotic optimality with a strict polynomial convergence rate.

We study block sensitivity and certificate complexity of rotation symmetric Boolean functions, with particular emphasis on monomial rotation symmetric Boolean functions. We first show that every odd-degree monomial rotation symmetric Boolean function on $n$ variables satisfies $s=bs=C=n$. We then determine sensitivity, block sensitivity, and certificate complexity for every quadratic monomial rotation symmetric Boolean function. For the quadratic function $Q_{n,k}$ generated by $x_0x_k$, we prove, outside the short-orbit case, that \[ C(Q_{n,k})= \begin{cases} n,&4\mid n/\gcd(n,k),\\ n-\gcd(n,k),&4\nmid n/\gcd(n,k). \end{cases} \] Moreover, \(bs(Q_{n,k})=C(Q_{n,k})\) for every quadratic MRS function, and outside the short-orbit case, strict separation \(s<bs=C\) occurs exactly when \[ \frac{n}{\gcd(n,k)}\equiv2\pmod4. \] Finally, for the consecutive quartic family \[ R_n(x)=\bigoplus_{i\in\mathbb Z_n}x_ix_{i+1}x_{i+2}x_{i+3}, \] we determine all three measures in every residue class modulo $6$, using the sensitivity formulas and, in one residue class, finite-state results established in our companion preprint~\cite{LiZhangRSBFSensitivity}. In particular, for $r=2,3$ and $6q+r\ge5$ we obtain strict separation, \[ \boxed{s(R_{6q+r})=6q<bs(R_{6q+r})=C(R_{6q+r})=6q+1,\qquad r=2,3.} \] Thus this family gives an infinite collection of rotation symmetric Boolean functions for which sensitivity is strictly smaller than block sensitivity, while block sensitivity and certificate complexity coincide.

Rotation symmetric Boolean functions are Boolean functions invariant under cyclic permutation of their variables and can be represented by binary necklaces. We express local sensitivity as a weighted bichromatic degree in the necklace quotient and derive an exact formula for the multiplicities between neighboring necklaces. For an odd prime number of variables, we obtain explicit sensitivity formulas and show that multiplicity corrections occur only on an asymptotically negligible family of necklaces. For monomial rotation symmetric Boolean functions, we prove that every odd-degree function has maximum sensitivity, determine the sensitivity of every quadratic function, and determine the sensitivity of the consecutive quartic family. We also determine exactly the sensitivity of cyclic run-threshold functions for arbitrary length and threshold.

We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.

We study the number of improving steps that local search may require for $(2,2,r)$-MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constraints in which every constraint involves at most two variables, every variable occurs in at most two constraints, and every variable takes one of $r$ values. We consider the flip neighborhood, where two assignments are neighbors if they differ in the value of exactly one variable; moving to such a neighbor is called a flip. Local search repeatedly performs improving flips, that is, flips that strictly increase the objective value, until a local optimum is reached. Our main result is that $(2,2,5)$-MCA has the all-exp property: there is an infinite family of instances with initial assignments for which every sequence of improving flips ending in a local optimum has length exponential in the number of variables. Thus, on these instances, local search requires exponentially many steps regardless of which improving flip is chosen at each step. This is the first all-exp result for $(2,2,r)$-MCA for any value of $r$, and our result extends to every $r\ge 5$. In contrast, for $(2,2,2)$-MCA every sequence of improving flips has length at most quadratic in the number of variables~\cite{Kaz2020,KCJ2020}. We give a short, direct proof of this result.

In this short note, we prove that any closed interval in a well-ordered and discrete space is finite. The coincidence between finiteness and boundedness can then be established for transition systems where the state space is well-ordered and discrete. Finally, this result is also proven when the state space is a Cartesian product of $d$ discrete and well-ordered sets.

The central object in this work is the Boolean network, a function $f:\{0,1\}^V \to \{0,1\}^V$. Often identified with $f$ is its dynamics $D_f$, the digraph with exactly $\{x \to y : f(x)=y\}$ as its arcs. The interaction graph of $f$ is the digraph $G$ on $V$ which can be thought of as representing the dependencies of the components of $f$ on one another. On the other hand, model-checking is a major field of study in graph algorithms and complexity. We consider problems at the intersection of these paradigms: for a given property $\phi$, we say that a digraph $G$ is $\phi$-dynamic if $G$ is the interaction graph of some Boolean network $f$ such that $D_f \models \phi$. The corresponding decision problem $\phi$-DYNAMIC asks whether $G$ is $\phi$-dynamic. Problems of this form are well-studied in the Boolean networks community. For example, it is a well-known result that, letting $\phi$ be 'No fixed points' (i.e. $\nexists x:x\to x$), $\phi$-DYNAMIC is equivalent to the structural digraph problem NON-ACYCLIC, which is solvable in linear time. We establish, for the first time, properties $\phi$ for which $\phi$-DYNAMIC is computationally hard. These include the 'Unique fixed point' property $\exists!x:x\to x$, and a range of properties concerning the periodic points of $f$ (i.e. vertices of $D_f$ which lie on a cycle). More widely, we exhibit an infinite family of natural properties $\phi$ such that $\phi$-DYNAMIC is $\mathrm{NEXPTIME}$-complete, which we call PERIOD PIECE. As a special case, these include all properties of the form 'Unique cycle of length $k$' and 'Exactly $k$ fixed points' for any $k \ge 1$. On the other hand, we show that if the input digraph has bounded in-degree, then for those same problems $\phi$-DYNAMIC collapses down to $\mathrm{NP}^{\mathrm{NP}}$, the second level of the polynomial hierarchy, though it remains $\mathrm{NP}^{\mathrm{NP}}$-complete.

Conway's $99$-graph is a strongly regular graph with parameters $(v,k,\lambda,\mu) = (99,14,1,2)$ and whose existence has long been an open problem. We use both a sum-of-squares program and the fact that a strongly regular graph with $\lambda = 1, \mu = 2$ has no diamond or $K_{2,3}$ subgraph to derive a loose upper bound for the number of triangles that such a graph could contain. This bound is less than the number of triangles that the graph's spectrum asserts, implying that it does not exist.

A graph is elementary if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chvátal–Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipartite multigraphs and all complements of bipartite graphs. We prove that every elementary graph $G$ satisfies $\ch(G)=\chi(G)=\omega(G)$, confirming for this class the conjecture of Gravier and Maffray that claw-free graphs are chromatic-choosable. The proof combines the Maffray–Reed description of elementary graphs as augmentations of line graphs of bipartite multigraphs, Galvin's theorem, an extremal (edge-maximal) choice of counterexample, and a Hall-type lemma describing how list colourings of a complete graph minus a matching can fail.

A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\mathcal O(m^b)$. We show that Max Weight Independent Set (MWIS) admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. In particular, this applies to graphs excluding any fixed graph as an induced minor, by a separator theorem of Korhonen and Lokshtanov [SODA 2024]. Our theorem generalizes the QPTASes for axis-parallel rectangles [Adamaszek and Wiese, FOCS 2013] and polygons [Adamaszek, Har-Peled, and Wiese, JACM 2019], or equivalently for packing connected subgraphs of a planar graph [Pilipczuk, van Leeuwen, and Wiese, Algorithmica 2020]. It also generalizes the QPTAS for MWIS on hereditary classes with strongly sublinear separators measured in vertices [Dvořák, EJC 2018; Dvořák and Lahiri, ESA 2021], as well as the QPTASes for graphs excluding particular induced minors [Chudnovsky et al., arXiv 2025; Bonnet et al., SWAT 2026; Czyżewska et al., arXiv 2026].

The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $\Theta(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.

Distributed Constraint Satisfaction Problems (DCSPs) model distributed decision-making in multi-agent systems, where agents assign values to local variables while satisfying shared constraints. However, many DCSP solvers still rely on broad, repeated peer-to-peer communication and are largely reactive, with limited support for strategic coordination or learning. This increases communication overhead, can lead to stagnation, and reduces the success of hard instances. Hence, we propose Dynamic Conflict Clustering-Incomplete (DCC-Incomplete), a repair-based solver that combines conflict-centred decomposition, structured coordination, strategic repair, and lightweight learning for stagnation recovery. DCC-Incomplete groups the unsolved part of the problem into conflict clusters and restricts communication via a coordination layer to agents within the same conflict region. It also introduces memory-guided restart, enabling agents and clusters to pause, revise, and adapt repairs based on neighbouring conflict states. A thorough evaluation of DCC-Incomplete on distributed graph-colouring benchmarks with planted satisfying assignments shows that its memory-guided restart improves the success rate from 37.50% to 61.11%, reduces median runtime from 0.565s to 0.367s, and cuts median communication from 12.493 to 6.503 messages per constraint. These results suggest that dynamic conflict clustering, combined with lightweight strategic and learning-guided repair, improves both communication efficiency and robustness in incomplete DCSP solving.

Codes in the Levenshtein metric that can correct multiple edits (including deletions, insertions, and substitutions) have attracted a lot of attention recently owing to their application in DNA-based storage and racetrack memories. In this work, we present new techniques for designing explicit binary codes of length $n$ that correct $t$ edits with at most $(2t+1)\log n+O_t(\log\log n)$ bits of redundancy. We first propose to use a polynomial hash to construct a systematic code that corrects $t$ edits with $(4t+2)\log n+O_t(\log\log n)$ bits of redundancy. Then we observe that there are many polynomial hashes like this, some are good, some are bad. So, we propose the second technique, called entropy recycling, to use the indices of good hashes to carry information. As a consequence, we obtain a partial-systematic code of length $n$ that corrects $t$ edits with at most $(2t+1)\log n+O_t(\log\log n)$ bits of redundancy. Finally, we provide deterministic polynomial-time encoding and decoding algorithms for our code.

Can quantum communication determine the size of an anonymous network when no size bound is known? Classical impossibility proofs rely on the covering lemma: an execution can be reproduced on a larger network with the same local structure. Quantum interference invalidates this argument - a measurement record possible on a network can become impossible on a cover. We show that the impossibility of exact counting nevertheless survives. Our main result is a quantum analogue of the covering lemma that preserves local possibilities rather than complete executions. Within a cyclic covering family, every local measurement outcome possible at a node remains possible at a corresponding node in every sufficiently large network. This holds even after information has travelled around the smaller network, beyond the reach of a simple locality argument. We extend the principle to the universal covering tree and finite covers with sufficiently long cycles. The proof combines tensor-network methods with graph coverings: a common representation across network sizes turns normalization into a constraint on which local outcomes can occur. For uniform synchronous protocols with independently prepared nodes, this support-lifting principle rules out zero-error counting and even the production of a guaranteed finite size bound on anonymous rings and the other cyclic covering families considered here. It also rules out exact leader election with termination in finite time with probability one on these families. Measurements, classical control, and local memory growing with time are allowed; no predetermined running-time bound is assumed. Quantum interference thus defeats execution lifting without enabling infallible certification of network size.

FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood. We prove that this rule can require $n^{\Omega(1)}$ many colors on certain bipartite graph of $n$ vertices even when the vertices arrive in a uniformly random order. This refutes the conjecture of Bosek, Gutowski, Lasoń, and Przybyło [BGLP24] that FirstFit uses a polylogarithmic expected number of colors on every bipartite graph in the random order model. We obtain the lower bound by analyzing the FirstFit coloring process on random bipartite graphs, where vertices arrive to either side with equal probability, and with an independent edge density $n^{-x}$ for some $0 < x < 1$. Our result can also be viewed as a qualitative strengthening of Kučera [Kuč91], who showed that, for every $\epsilon > 0$, there are graphs with chromatic number at most $n^{\epsilon}$ on which FirstFit uses $\Omega(n/\log n)$ colors in expectation under a uniformly random order. Our result shows that such poor behavior of FirstFit already occurs for $\chi(G) = 2$.

We exhibit a fixed $4\times 4$ binary matrix with no polynomial induced ordered removal bound. At depth $h\geq 1$, let $m=2^h$. Our explicit host has order $(14h+2)m$, exactly $2m^6+\frac{1}{2}(m-2)m^5$ induced copies, and exact editing distance $m^2$ cells. Its normalized editing distance is $\Theta(h^{-2})$, while its induced-copy density is $\Theta(4^{-h}h^{-8})$. The lower bound holds against arbitrary cell edits through an injective family of $m^2$ protected selections. An exhaustive arithmetic classification identifies every induced copy and proves that a matching canonical repair creates none. The original-copy transversal number is exactly $m$, yielding an unbounded gap between hitting existing copies and eliminating all copies. The identities and the obstruction at every depth are formalized in Lean, with verification sources included as ancillary files.

We study a natural greedy algorithm for the Airplane Refueling Problem (ARP), based on a well-known priority rule. We show that this algorithm achieves an approximation guarantee of $9/20$, noticeably improving the previously known $1/12$ guarantee for a fast algorithm. We also show that the same priority rule can be implemented in $O(n\log n)$ time and $O(n)$ space using a dynamic convex-hull data structure. These results provide a worst-case approximation guarantee for an existing greedy priority rule and establish an efficient implementation. In the real-RAM model, the running-time bound is independent of the magnitude of the processing times. The resulting method is also suitable as a fast primal routine inside more complex exact and approximation algorithms for large instances. These results narrow the gap between theoretically strong but complex approximation schemes and lightweight algorithms that can be used directly in computational pipelines. The algorithm combines a simple selection rule with a provable performance bound, making it a useful baseline for further algorithmic studies of ARP.

The Game of Cycles, invented by Francis Su, is a two-player game in which the players take turns drawing arrows on the edges of a plane graph, never creating a sink or a source. On a tree only the sink-source rule matters, and the player who makes the last move wins. Several authors conjectured that on a tree the second player wins exactly when the number of markable edges is even. We show that this parity conjecture is false, and we explain why. The explanation is a hidden game of Nim: a path segment that is blocked by an arrow at one end and free at the other behaves exactly like a nim heap whose size is its length. Combined with a calculus for cutting and gluing trees at vertices next to leaves, this shows that the conjecture fails as soon as a single tree has Grundy value at least 2. The smallest counterexamples have 15 vertices. Trees with Grundy values 2 and 4 first appear at 17 vertices, and every value up to 63 occurs, which answers a question of Fokkink and Zandee. We also refute a related conjecture of Zandee. We then look closely at spiders. The spiders S(2,3,z) violate the conjecture for every z >= 14. The Grundy values of S(1,2j,z) are given by an exact formula governed by binary carries. For 99 pairs (x,y), the value of S(x,y,z) is eventually the parity of z. On the positive side, the conjecture holds for all trees in which every thread has at most two edges, and this bound is sharp. Along the way we prove a twin-branch reduction, give an algorithm that is polynomial for spiders with a fixed number of legs, and collect the questions that we could not answer. The boldest asks whether every non-negative integer is the Grundy value of some tree.

The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$ except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed–Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.