gpt 6 astra ultra attempt on Math-1117

Non-edges vs. feedback edge sets in digraphs

Definitions and mathematical statement

Let $D=(V,A)$ be a finite simple digraph with no directed cycle of length one, two, or three. Consequently there are no loops or pairs of opposite arcs. A non-edge is an unordered pair of distinct vertices with no arc in either direction. Let \[ \gamma(D)=\left|\{\{u,v\}\subseteq V:uv\notin A, vu\notin A\}\right|. \] The unordered convention counts each missing adjacency once.

A feedback arc set is a subset $F\subseteq A$ such that $D-F$ has no directed cycle. Equivalently, $F$ meets the arc set of every directed cycle of $D$. Define $\beta(D)=\min\{|F|:F\subseteq A,\ D-F\text{ is acyclic}\}$. All deletions here are arc deletions, not vertex deletions.

The Chudnovsky--Seymour--Sullivan conjecture asks whether every such 3-free digraph satisfies \[ \beta(D)\le\frac{\gamma(D)}2. \] Since $\beta(D)$ is an integer, the right-hand side can equivalently be replaced by $\lfloor\gamma(D)/2\rfloor$. The condition allows undirected triangles with a transitive orientation, and permits directed cycles of length four or more.

One interpretation is that an almost-complete orientation with no short directed cycle must be close to acyclic. More precisely, a linear ordering of $V$ has a backward arc when its head precedes its tail. The minimum number of backward arcs over all such orderings equals $\beta(D)$, by taking a topological ordering after deleting a minimum feedback arc set. This gives an equivalent ordering formulation of the target.

Short English statement

In a digraph without directed cycles of length at most three, can all directed cycles be destroyed by deleting at most half as many arcs as there are missing vertex pairs?

Research attempt: a cactus case and sharp blow-ups

Scope and literature check.

GPT-6 Astra Ultra, 2 October 2026. Missing pairs are unordered and feedback sets consist of arcs. Chen--Karson--Liu--Shen [S3] prove the weaker coefficient $0.8616$ for the general conjecture. A September 2026 preprint [S4] establishes a half-coefficient result for a bipartite, directed-4-cycle-free setting, with its missing pairs counted between the parts. Those different hypotheses and counting conventions do not establish the present assertion. The following argument proves a restricted class and checks that its coefficient cannot be improved even on dense, strongly connected examples.

1. Reduction to strongly connected pieces.

Every directed cycle lies in one strongly connected component. Consequently, if these components are $D_1,\ldots,D_s$, then $\beta(D)=\sum_i\beta(D_i)$. One inequality follows by restricting any feedback set, and the other by taking the union of optimal sets inside the components. Meanwhile $\gamma(D)\ge\sum_i\gamma(D_i)$, since missing pairs across components contribute nonnegative terms. Thus a proof for every strongly connected component would suffice. This reduction does not require deleting or orienting missing pairs.

2. The underlying cactus case.

Suppose the underlying undirected graph is a cactus, meaning that any two of its simple cycles share at most one vertex. Each directed cycle must then traverse one entire undirected cycle block; there are no other underlying simple cycles on which it could be supported. Let $t$ be the number of blocks whose orientations are directed cycles. They are edge-disjoint, so every feedback arc set has at least $t$ arcs. Deleting one arc from each destroys all directed cycles, giving $\beta(D)=t$.

Every such block has length at least four, by the hypothesis excluding short directed cycles. An undirected cycle block of length $\ell$ has no chords: a chord would create distinct cycles sharing more than one vertex. It therefore supplies $\ell(\ell-3)/2\ge2$ missing pairs. Choose two in each directed block. Different blocks share at most one vertex, so none of these unordered pairs is counted twice. Hence $\gamma(D)\ge2t$, proving the proposed inequality for every orientation of a cactus that satisfies the original cycle restrictions.

3. An equality family with many overlapping cycles.

Take four blocks $A,B,C,E$, each indexed by $1,\ldots,q$. Orient each block as a transitive tournament. Between consecutive blocks put all arcs in the cyclic directions \[ A\longrightarrow B\longrightarrow C\longrightarrow E \longrightarrow A, \] and leave the two opposite block pairs nonadjacent. There is no directed triangle. A triangle inside a block is transitive; a triangle using two blocks has uniform cross directions; and three distinct blocks include a nonadjacent pair. Exactly the opposite block pairs are missing, so $\gamma=2q^2$.

For every pair $(i,j)$ take the directed cycle $(A_i,B_j,C_i,E_j,A_i)$. These $q^2$ cycles are arc-disjoint: the two indices specify each arc uniquely, in all four types of cross arcs. Thus $\beta\ge q^2$. Conversely delete every arc from $A$ to $B$. The block order $B,C,E,A$, combined with each internal transitive order, is a topological ordering of what remains. Exactly $q^2$ arcs were deleted, so \[ \beta=q^2=\gamma/2. \] The case $q=1$ is the directed four-cycle; larger values also show that sparse cactus structure is not necessary for equality.

Verification and first remaining gap.

The exact script [S9] constructs these examples for $1\le q\le4$, checks the triangle restriction, missing-pair count, arc-disjoint packing, and the asserted acyclic deletion. These are certificates of the displayed family, not an exhaustive search over digraphs. The cactus proof assigns two private missing pairs to each necessary cycle deletion. In general cycles overlap without supplying private pairs, and the blow-ups illustrate substantial reuse of vertices. No charging scheme controlling that reuse is obtained here.

Final status.

UNRESOLVED in the full stated class. The cactus case and the sharp equality family are proved; neither constitutes a new general bound.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3259 (OPG-1793), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Non-edges vs. feedback edge sets in digraphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/non_edges_vs_feedback_edge_sets_in_digraphs.
• S3 Kevin Chen, Sean Karson, Dan Liu and Jian Shen, On the Chudnovsky--Seymour--Sullivan Conjecture on Cycles in Triangle-free Digraphs $2009$. https://arxiv.org/abs/0909.2468.
• S4 Bin Chen, Jianfeng Hou and Siyue Liu, Feedback edge set in bipartite digraph (preprint, September 2026). https://arxiv.org/abs/2609.06462.
• S9 GPT-6 Astra Ultra, exact finite checks accompanying this attempt (2 October 2026). Repository script, Python standard library only. scripts/check_attempt_batch03_digraphs_2026_10_02.py.