Norin 2016 triangle independent sets vs cuts

../

algorithm_1: Proves termination, residual conditioning and color symmetry for the ordered-pair randomized partition on a triangle-free trigraph.

clebsch_example: Proves from the even-subset graph model that every run of Algorithm 1 leaves exactly twelve uncut edges on the Clebsch graph.

component_law: Proves independence of the component outputs by finite trajectory coupling and gives the exact deficit decomposition across S-components.

conjecture_3: Derives the exact E621 inequality and proves both directions of its equality classification, including the triangle-free deletion calculation.

cut_parameters: Proves the finite deletion and cut equivalences and the comparison between triangle-edge covers and bipartite-making edge sets.

deterministic_algorithm: Derandomizes the source construction using an exact pair average, a residual color flip and conditional assignment of the remaining vertices.

extremal_connected: Proves that a nonempty S-connected equality trigraph has no C-edges and is complete balanced bipartite, with all shortest-path cases explicit.

historical_context: Records the exact preprint version, later published uptake and the historical assertions that are not resolved or formally verified by this source unit.

lemma_6: Proves both ordered-tuple inequalities by explicit nonnegative squares and records the pointwise equality consequences.

lemma_7: Derives every term of the trigraph counting identity and corrects the extra star coefficient in the source equation (15).

local_characterization: Proves the source’s unnumbered characterization by nonadjacency classes, a matching quotient and the exact balance deficit.

mantel_bound: Gives a complete elementary proof of Mantel’s bound used to compute triangle-deletion numbers of the extremal joins.

notation: Defines the trigraph, cut and ordered tuple conventions used in the complete Norin–Sun proof, including repeated vertices and diagonal indicators.

question_8: Proves the complement identity, coefficient interval and fractional scaling surrounding the source-dated edge-count question.

theorem_4: Proves the sharp alpha_1 plus tau_B inequality and its exact join classification, including explicit extremal cardinalities.

theorem_5: Assembles the expectation theorem and its complete equality characterization as C-joins of balanced complete bipartite trigraphs.

theorem_5_bound: Proves the randomized trigraph bound by induction and an exact nonnegative gap identity, with all averaging factors and empty cases explicit.

---

Sergey Norin and Yue Ru Sun, Triangle-independent sets vs. cuts, arXiv:1602.04370v1 (13 February 2016). The copy read for this card is the fourteen-page v1 PDF. The source record identifies its version and the bounded later-primary search. The arXiv record names arXiv's non-exclusive distribution license (arXiv:1602.04370), every other right reserved.

Theorem 4 proves, for every finite simple graph on $N$ vertices,

$$\alpha_1(G)+\tau_B(G)\le N^2/4.$$

Here $\alpha_1$ is the maximum size of an edge set meeting each triangle at most once, and $\tau_B$ is the minimum number of edges whose deletion makes the graph bipartite. Exact equality holds precisely for joins of complete balanced bipartite graphs, including the empty join. This concerns equality with $N^2/4$, not the rounded bound at odd $N$.

Since $\tau_1\le\tau_B$, the result implies the Erdős–Gallai–Tuza inequality in Problem 621. That page also proves the weak equality converse with a local proof of Mantel’s bound; the comparison of the two deletion parameters alone would not establish that converse.

Main proof. The full trigraph argument is divided into its exact finite-probability and counting steps:

• Definitions and ordered tuple counts, cut parameters, and Algorithm 1 with its residual law.
• Both inequalities of Lemma 6 and the complete identity of Lemma 7.
• The expectation inequality and exact gap identity, the independent component law, and the connected equality case.
• Theorem 5 and its full trigraph equality class, followed by the graph theorem and E621 specialization.

The proof is computer-free. Four printed slips are corrected explicitly on the corresponding pages: the misplaced square in Lemma 6, the extra star coefficient in equation (15), the cross-edge prose before (17), and the equality sign used for an upper bound on p. 10. These are compilation repairs, not author errata. All tuple sums allow repeated vertices, and the algorithm chooses uniformly ordered pairs.

Further deductions. Complete expansions are given for the local characterization of extremal trigraphs, the deterministic cut algorithm with supplied S, the exact Clebsch output, and the complement and fractional observations around Question 8. The Clebsch result limits this algorithm; it is not a counterexample to the triangle-free deletion conjecture.

History and limits. The version and historical record retains the source’s Lehel/Puleo and Erdős–Gallai–Tuza attributions, earlier Puleo/Xu bounds, EFPS method context, and source-dated questions. Those contextual proofs and the asserted NP-hardness of computing $\alpha_1$ are not claimed reconstructed. Neither Question 8 nor Erdős's triangle-free $N^2/25$ conjecture (the source's Conjecture 1) is assigned a current status here.

The current arXiv record and author list still point to v1; no separate journal version was located in the bounded search. A 2025 published primary paper explicitly adopts the theorem and cites v1. Its new proofs and a distinct August 2026 lower-bound preprint are outside this source unit. No formal proof or local kernel verification is certified here.

Read status: claims checked. The statements of Theorems 4 and 5 (pp. 2 and 5), Lemmas 6 and 7 (pp. 6 and 8), Algorithm 1 (p. 4), Conjectures 1--3 (pp. 1--2), Question 8 (p. 13) and the concluding remarks (pp. 11--13) were read clause by clause against the print, with the four slips above checked there. The proofs on the result pages are the corpus's own reconstruction; no independent review of them is recorded.

Bears on.

• Problem 621: Theorem 4 (p. 2) with $\tau_1\le\tau_B$ proves the asked inequality $\alpha_1(G)+\tau_1(G)\le n^2/4$ for every finite simple graph on $n$ vertices, the paper's Conjecture 3; the Conjecture 3 page adds that equality with $n^2/4$ holds exactly for joins of complete balanced bipartite graphs.
• Problem 23: the paper states Erdős's conjectured bound $\tau_B(G)\le n^2/25$ for triangle-free graphs on $n$ vertices as its Conjecture 1 (p. 1), which Problem 23 asks for $n$ divisible by five, and proves nothing towards it; its Clebsch remark (p. 12) shows only that Algorithm 1 alone cannot give that bound at order $16$.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.