Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments
Pith reviewed 2026-05-25 12:00 UTC · model grok-4.3
The pith
Every f(k)-arc-strong semicomplete digraph has a spanning eulerian subdigraph avoiding any k prescribed arcs, where f(k) is at most ceiling of (6k+1)/5.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove that f(k) ≤ ceiling((6k+1)/5), where f(k) is the smallest function such that every f(k)-arc-strong semicomplete digraph has a spanning eulerian subdigraph avoiding any prescribed set of k arcs.
What carries the argument
The function f(k) defined as the minimal arc-connectivity guaranteeing a spanning eulerian subdigraph that avoids k prescribed arcs.
If this is right
- The required arc-connectivity grows at most linearly with k instead of quadratically.
- For every k the bound is at most roughly 1.2 times k.
- The result applies to all semicomplete digraphs and therefore to the subclass of tournaments.
- Combined with the known lower bound of k plus 1 it shows that f(k) lies between k plus 1 and ceiling((6k+1)/5).
Where Pith is reading between the lines
- Refinements of the construction might eventually reach the conjectured exact value f(k) equals k plus 1.
- The same linear growth rate may hold for analogous problems that replace eulerian subdigraphs by other balanced spanning subdigraphs.
- The technique could be tested on digraphs that are not semicomplete but satisfy weaker density conditions.
Load-bearing premise
The result assumes the prior proof that f(k) exists and is finite together with the exact values f(2) equals f(3) equals k plus 1 from earlier work.
What would settle it
A counterexample would be any semicomplete digraph whose arc-connectivity equals ceiling((6k+1)/5) yet possesses no spanning eulerian subdigraph that avoids some particular set of k arcs.
read the original abstract
A digraph is {\bf eulerian} if it is connected and every vertex has its in-degree equal to its out-degree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. A digraph is {\bf semicomplete} if it has no pair of non-adjacent vertices. A {\bf tournament} is a semicomplete digraph without directed cycles of length 2. Fraise and Thomassen \cite{fraisseGC3} proved that every $(k+1)$-strong tournament has a hamiltonian cycle which avoids any prescribed set of $k$ arcs. In \cite{bangsupereuler} the authors demonstrated that a number of results concerning vertex-connectivity and hamiltonian cycles in tournaments and have analogues when we replace vertex connectivity by arc-connectivity and hamiltonian cycles by spanning eulerian subdigraphs. They showed the existence of a smallest function $f(k)$ such that every $f(k)$-arc-strong semicomplete digraph has a spanning eulerian subdigraph which avoids any prescribed set of $k$ arcs. They proved that $f(k)\leq \frac{(k+1)^2}{4}+1$ and also proved that $f(k)=k+1$ when $k=2,3$. Based on this they conjectured that $f(k)=k+1$ for all $k\geq 0$. In this paper we prove that $f(k)\leq (\lceil\frac{6k+1}{5}\rceil)$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that the function f(k) — the smallest integer such that every f(k)-arc-strong semicomplete digraph admits a spanning Eulerian subdigraph avoiding any prescribed set of k arcs — satisfies the upper bound f(k) ≤ ⌈(6k+1)/5⌉. This improves the authors' earlier quadratic bound f(k) ≤ (k+1)^2/4 + 1 while relying on the existence of f(k) and the exact values f(2)=f(3)=k+1 established in the cited prior work.
Significance. If correct, the linear upper bound constitutes a meaningful advance toward the conjecture f(k)=k+1, substantially tightening the gap from the previous quadratic estimate and supplying a fresh proof argument that does not reduce to fitted parameters or self-referential quantities.
major comments (1)
- [Proof of the main result] The derivation steps that produce the specific linear coefficient 6/5 (and the ceiling function) from the arc-connectivity construction are not supplied in sufficient detail; without these intermediate claims the central bound cannot be verified from the manuscript alone.
Simulated Author's Rebuttal
We thank the referee for the careful reading and the positive assessment of the significance of the linear upper bound. We address the single major comment below.
read point-by-point responses
-
Referee: [Proof of the main result] The derivation steps that produce the specific linear coefficient 6/5 (and the ceiling function) from the arc-connectivity construction are not supplied in sufficient detail; without these intermediate claims the central bound cannot be verified from the manuscript alone.
Authors: We agree that the manuscript would benefit from greater explicitness in the derivation. In the revised version we will insert a dedicated subsection that spells out every intermediate inequality and the precise manner in which the arc-connectivity hypothesis is converted into the coefficient 6/5 together with the ceiling function, so that the bound f(k) ≤ ⌈(6k+1)/5⌉ can be verified directly from the text without external reconstruction. revision: yes
Circularity Check
Minor self-citation for existence; new bound proved independently
full rationale
The paper assumes the existence and finiteness of f(k) plus the exact values f(2)=f(3)=k+1 from the authors' prior work [bangsupereuler], which is a standard incremental reliance and does not reduce the new upper-bound proof to a self-definition or fitted input. The derivation of f(k) ≤ ⌈(6k+1)/5⌉ is presented as a fresh argument building on that foundation, with no equations or steps in the manuscript that equate the claimed result to its inputs by construction. This matches the default expectation of no significant circularity.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Standard definitions of tournaments as orientations of complete graphs, semicomplete digraphs, arc-connectivity, and eulerian subdigraphs (in-degree equals out-degree and connected).
- domain assumption Existence of the function f(k) as the smallest integer such that every f(k)-arc-strong semicomplete digraph admits a spanning eulerian subdigraph avoiding any k prescribed arcs (from cited work).
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.