{"id":"8a4366ee-2e15-4e5d-8c8a-5318e1d55f26","arxiv_id":"1908.06480","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every large oriented graph has at least 1/9 - o(1) probability that a random triple is a transitive triangle or an independent set, and the bound is tight.","lead":"This paper finds the smallest possible chance that three random vertices of a one-way directed graph form a transitive triangle or an independent set. The answer is exactly one ninth, with a unique extremal shape, proved by a computer-assisted method for counting local patterns.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2 depends on the unverified finite computation that the displayed Section 9 matrix is PD and satisfies all 42 certificate inequalities; without a machine-checkable certificate, the proof is not fully auditable.","rationale":"The paper's central claim is a sharp asymptotic Goodman-type bound for oriented graphs, proved by flag algebras. The upper bound via the balanced cyclic blow-up is elementary and solid, and the theoretical framework of SDP certificates is standard. The only place where the argument leaves the realm of fully checkable mathematics is the assertion in Section 9 that the displayed matrix Qbar is positive definite and satisfies the 42 linear inequalities. This is exactly the weakest assumption identified by the reader: the proof of Theorem 5.1, and therefore of Theorem 1.2, depends on a finite computation that is reported but not supplied. I examined whether any more substantive conceptual gap exists in the reduction from the original SDP to the projected SDP or in the stability argument. The projection lemma is correct, and the stability proof uses the certificate only through Claim 5.4, whose quantitative dependence is explicit. The displayed certificate is concrete enough that an independent exact check is feasible, so the concern is not that the result is likely wrong but that the proof is incomplete as presented. If the exact check passes, the concern disappears and the verdict should be ACCEPT; if it fails, the theorem has no proof. Since the reader's conditional verdict already reflects this state, I recommend no change.","tokens_in":46024,"tokens_out":2954,"duration_ms":32493,"concrete_test":"Reconstruct the exact matrices Qbar_phi, Qbar_Ebar, and Qbar_E from the displayed blocks in Section 9 using exact rational arithmetic together with the algebraic symbols sqrt(2), sqrt(3), and sqrt(6). Independently compute the 42 projected matrices Abar_i = R^T A_i R from the flag definitions in Section 5 and Figures 8-10, or from a clean implementation of the flag-algebra construction. Then verify, with exact arithmetic in Q(sqrt(2), sqrt(3)), that Qbar is positive definite (for example, by checking all leading principal minors) and that ci - <Qbar, Abar_i> >= 1/9 holds for every i = 1,...,42. Publish the certificate and the verification script so the computation is reproducible.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower bound in Theorem 1.2 is obtained from Proposition 3.6 plus Theorem 5.1, which asserts the existence of a 1/9-certificate for the SDP (20). The proof of Theorem 5.1 is completed in Section 9 by displaying a specific 15×15 matrix Qbar and stating: 'We have verified by computer software that the matrix Qbar is PD (positive definite) and that it satisfies ci - <Qbar, Abar_i> >= 1/9 for every 1 <= i <= 42.' No code, no machine-readable certificate, and no independent verification are provided. The displayed matrix contains algebraic entries involving sqrt(2), sqrt(3), and sqrt(6), so the verification is not a trivial visual check. Every step before Section 9—including the reduction to the projected SDP and the derivation of the sharp-graph equations—still leads to a concrete, finite certificate claim; the entire weight of Theorem 1.2 rests on that single unverified finite computation. This is not a conceptual flaw or an internal inconsistency, but it is precisely the kind of load-bearing computational assertion that needs independent confirmation before the theorem can be accepted as proved. If the displayed matrix passes the check, the argument is sound; if it fails, the main theorem is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that every n-vertex oriented graph G satisfies t(G)+i(G) ≥ 1/9 - o(1), and that the constant is tight, with equality approached by balanced cyclic blowups B_n. The proof is conducted in the flag algebra framework: after setting up the SDP (20) with k = 4, the authors reduce it to a projected SDP (29), derive necessary kernel vectors and sharp-graph equations, and then claim in Theorem 5.1 that a 1/9-certificate exists, witnessed by an explicit 15×15 matrix Qbar displayed in Section 9. Building on this certificate and additional arguments, the paper also proves a stability theorem (Theorem 1.4) and an exact structural theorem (Theorem 1.5) describing all sufficiently large extremal graphs. Much of the text is a self-contained exposition of the flag algebra workflow, including warm-up proofs of weaker bounds and of Goodman's theorem.","tokens_in":46254,"tokens_out":4941,"duration_ms":54140,"significance":"If the central computational certificate is independently verifiable, this is a substantial contribution: it settles a natural Goodman-type question for oriented graphs with the exact asymptotic constant 1/9, provides an explicit and tight extremal construction, and goes beyond the usual flag-algebra paper by proving stability and exact structure with quantitative error terms. The paper is also pedagogically valuable: the derivations of the kernel-vector restrictions (Section 6), the sharp-graph equations (Section 7), the projection argument (Section 8), and the stability/exactness proofs (Sections 10–11) are presented in unusual detail and are largely human-checkable. The main weakness is that the proof of Theorem 1.2 rests on unshipped computer verification of the certificate matrix in Section 9, and several auxiliary computational claims are similarly not accompanied by code or machine-readable data. The paper should be accepted only after those computations are made fully auditable.","major_comments":[{"comment":"The proof of Theorem 5.1, and hence of Theorem 1.2, rests on the sentence 'We have verified by computer software that the matrix Qbar is PD (positive definite) and that it satisfies ci - <Qbar, Abar_i> ≥ 1/9 for every 1 ≤ i ≤ 42.' No machine-readable certificate, no verification code, and no independent check are supplied. Because the entries of Qbar involve sqrt(2), sqrt(3), and sqrt(6), positive definiteness and the 42 inequalities are not a routine visual check. This is a load-bearing computational assertion: without it, the existence of a 1/9-certificate for SDP (20) is unproved. I request that the authors provide (a) a machine-readable version of Qbar and of the pulled-back Q = R Qbar R^T, (b) a verification script that checks positive definiteness and all 42 required inequalities with exact arithmetic or certified error bounds, and (c) the data defining the matrices A_i and the projection R, or a reproducible procedure that generates them.","section":"§9, certificate matrix Qbar (pp. 28–29)"},{"comment":"The statement 'Straightforward computer aided calculations reveal that dim W - dim tilde W = 9' is used to justify that the eleven sharp-graph equations reduce to exactly nine independent restrictions. That rank computation is essential for the construction of Qbar in Section 9, where the remaining nine coordinates are said to be determined by the sharp-graph equations. This is another unverified computational claim; the authors should supply the calculation, the matrix whose rank is being computed, or a reproducible script.","section":"§7, paragraph after Lemma 7.2 (p. 26)"},{"comment":"The proof of Lemma 10.1 depends on the assertion that eta_i = c_i - <Q, A_i> - 1/9 > 0 for i = 39, ..., 42, which is stated to be 'a straightforward albeit tedious calculation (which can be performed by computer software)'. Since Lemma 10.1 is the first step toward the stability theorem (Theorem 1.4) and hence toward the exact theorem (Theorem 1.5), this positivity check must be reproducible. Once a certified Qbar is supplied, this becomes a finite check, but at present it is unsupported in the manuscript.","section":"§10, Lemma 10.1 (p. 29)"},{"comment":"The description of how Qbar was obtained from the numerical SDP solution is not fully specified: the ordering of the 58 coordinates, the exact floating-point values used for the 49 coordinates retained from the rounded solution, and the linear equations defining the remaining nine entries are not given. This makes the construction non-reproducible even apart from the absence of the final certificate. If the authors ship the machine-readable matrix and a script that reconstructs it from the displayed data, this point becomes a documentation issue; as written, it is an obstacle to audit.","section":"§9, rounding procedure (p. 29)"}],"minor_comments":[{"comment":"There is a typo: 'orineted graph' should read 'oriented graph'.","section":"§10, proof of Proposition 10.6"},{"comment":"The notation p(F1, F2; G) and tilde-p(F1, F2; G) is introduced carefully, but the reader would benefit from a short intuitive gloss distinguishing the two before the formal definitions, especially because the difference between them is later used in Lemma 2.1.","section":"§2, p. 5"},{"comment":"The flags are depicted only by small drawings; since the coordinate order of the vectors in Lemma 6.3 is tied to these figures, the captions should state explicitly that the order is left-to-right and top-to-bottom as displayed, and the figures should be large enough that the orientation of each edge is unambiguous.","section":"Figures 8–10, §5"},{"comment":"The proof uses the graph removal lemma with a specific constant n(n-1)/1080; this is fine, but the reader should be warned that the constant 1/180 in the subsequent display relies on the fact that deleting an edge creates at most 6 independent triples, which is not stated at that point.","section":"§4, Proposition 4.6"},{"comment":"The notation f(k, l, n) and g(k, l, n) is defined and then used in 'g(3, 3) = 1/9 and f(3, 3) ≈ 3/16'; the meaning is clear, but a sentence explicitly matching the indices to the earlier theorems would improve readability.","section":"§12, Concluding remarks"}],"recommendation":"major_revision","confidential_remarks":"The main issue is reproducibility of the computational certificate. The manuscript is otherwise careful and appears technically sound, with the kernel, sharp-graph, and stability arguments presented in detail. I would ask the editor to require the authors to provide machine-readable certificates and verification scripts as supplementary material before publication. Without them, the central theorem rests on an unverifiable black-box assertion, even though the issue is local and fixable in scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the bottom line. The paper proves a genuine new result: tau = 1/9 for the sum of transitive-triangle and independent-triple densities in oriented graphs, with a stability theorem and a sharp uniqueness classification. The constant comes from the cyclic blow-up B_n, so the upper bound is explicit and non-circular. The lower bound is new; the old general bound was 1/10, and 1/9 was known only under t(G)=0. The exposition is unusually good for a flag-algebra paper; it actually explains the matrices, the SDP, and the rounding instead of treating the method as a black box.\n\nWhat I like: the paper goes out of its way to be self-contained, and it derives the kernel constraints from the extremal constructions, which makes the method much more transparent. The stability and exact results are substantial and do not follow from the earlier papers. The proofs in Sections 6 and 7 are careful.\n\nThe soft spot is the one you flagged. The lower bound rests on Theorem 5.1, whose proof in Section 9 is just the statement 'We have verified by computer software' that a specific 15x15 matrix is positive definite and satisfies the 42 inequalities. There is no code, no machine-readable certificate, and no independent check. The matrix has entries with sqrt(2), sqrt(3), sqrt(6), so this is not a visual inspection. This is load-bearing: without that check, Theorem 1.2 is unsupported. It is also slightly at odds with the paper's stated goal of being a comprehensible, self-contained case study. The fix is easy: ship the certificate in a parseable form and a short verification script (or at least give the leading principal minors and the 42 slacks). A referee can do the check, but they shouldn't have to re-type the matrix from the PDF.\n\nMinor comments: 'Straightforward computer aided calculations' for dim W - dim \\tilde W = 9 is also stated without details, though that's a small integer computation and less concerning. The stability proof uses the positive slacks for graphs 39-42, so it inherits the certificate issue as well.\n\nMy take: the mathematical architecture is coherent, and there's no evidence the certificate is wrong. But the paper as written is not fully auditable. I would send it to peer review, and I'd make acceptance conditional on providing a machine-checkable certificate. If the certificate passes, this is a strong paper.","headline":"A real new result in oriented graph extremal combinatorics with an unusually readable flag-algebra proof, but the main theorem currently rests on an unverifiable computer claim.","tokens_in":46812,"tokens_out":3403,"would_cite":true,"duration_ms":35641,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C35","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every oriented graph has at least 1/9 transitive or independent triples.","keywords":["oriented graphs","induced densities","flag algebras","transitive triangles","independent triples","semidefinite programming","stability","extremal construction"],"falsifier":"Independently verify in exact arithmetic the matrix displayed in Section 9: check positive definiteness and all 42 inequalities c_i - inner product(Q, A_i) >= 1/9. A single violated inequality, or a negative eigenvalue, would invalidate Theorem 1.2 as proved; alternatively, constructing an infinite sequence of oriented graphs with t(G)+i(G) < 1/9 - o(1) would refute the statement itself.","tokens_in":45809,"feed_emoji":"🔺","tokens_out":12396,"duration_ms":100557,"temperature":0.7,"pith_summary":"This paper proves the directed analogue of the classical triangle-plus-independent-triple bound: in every n-vertex oriented graph, the combined density of transitive triangles and independent triples is at least $1/9-o_n(1)$, and the constant $1/9$ is sharp. The extremal example is the balanced cyclic blow-up of a directed triangle, obtained by splitting the vertices into three roughly equal parts and directing all edges cyclically from part $i$ to part $i+1$. The authors also prove a stability theorem: any near-extremal graph is close to this blow-up, and an exact theorem: for all sufficiently large $n$, the only exact minimizers are obtained from the blow-up by deleting a union of three matchings. The proof is a self-contained flag-algebra case study that combines a semidefinite program with sharp-graph constraints and a rounding step.","feed_headline":"At least 1/9: transitive or independent triples in any oriented graph","feed_subtitle":"Tight bound with the cyclic blow-up of a triangle as the unique extremal shape for large graphs.","key_machinery":"The load-bearing mechanism is a 'flag-algebra certificate': a positive semidefinite matrix $Q$ indexed by flags (small oriented graphs with labeled vertices) whose inner products with the flag probability matrices $A_{G_i}$ satisfy $c_i-\\langle Q,A_{G_i}\\rangle\\ge 1/9$ for every 4-vertex oriented graph type $G_i$. Such a certificate turns the combinatorial lower bound into a semidefinite program: if it exists, then every large oriented graph has $t(G)+i(G)\\ge 1/9-o(1)$. The paper constructs $Q$ by projecting onto the complement of the kernel forced by the extremal construction, imposing linear equations from eleven 'sharp' 4-vertex graphs that appear at linear rate in the edge-deleted blow-up, solving the reduced semidefinite program numerically, and rounding the output to a rational matrix with entries in $\\mathbb{Q}[\\sqrt2,\\sqrt3]$.","core_discovery":"The paper's central discovery is that the asymptotic minimum is exactly $1/9$: every $n$-vertex oriented graph $G$ satisfies $t(G)+i(G)\\ge 1/9-o_n(1)$, where $t(G)$ is the probability that three random vertices form a transitive triangle and $i(G)$ the probability they are independent. The balanced cyclic blow-up $B_n$---three roughly equal parts with all edges directed from part $i$ to part $i+1$---shows the constant cannot be raised. The extremal structure is rigid: near-extremal graphs are $\\varepsilon$-close to $B_n$, and for sufficiently large $n$ every exact minimizer is obtained from $B_n$ by deleting a union of three matchings between the parts.","pith_inferences":["Editorial inference: the same certificate template could be used to prove other directed induced-density inequalities, such as the conjectural minimum $3/16$ for $t(G)$ among oriented graphs with $i(G)=0$, which the paper leaves as future work.","Editorial inference: since the final certificate has rational entries in a finite extension of $\\mathbb{Q}$, the central inequality could in principle be turned into a fully formal, machine-checkable proof; the paper itself relies on software for positive-definiteness verification without supplying that formal artifact.","Editorial inference: the 'phantom edge' random deletion variant $B_n^\\varepsilon$ suggests that near-extremal behavior may be richer than the exact extremal family, and a quantitative stability theorem with matching lower-order terms may be provable.","Editorial inference: if the unverified computational assertion is confirmed, the paper provides a reusable, transparent workflow for flag-algebra proofs, potentially lowering the barrier to applying the method to other three-vertex and four-vertex density problems."],"forward_implications":["The asymptotic value of the minimum of $t(G)+i(G)$ over oriented graphs is settled at $1/9$; no future construction can push the combined density below this.","Any oriented graph with $t(G)+i(G)\\le 1/9+\\delta$ must be close, in edit distance, to the balanced cyclic blow-up $B_n$; this is a stability statement with explicit quantitative form.","For all sufficiently large $n$, the exact extremal graphs are exactly the balanced cyclic blow-up with a union of three matchings deleted; this rigidity contrasts with the undirected case, where many extremal graphs exist.","In the special case of oriented graphs with no transitive triangles, the bound implies the independent-triple density is at least $1/9-o(1)$, recovering earlier results as a corollary."],"supporting_citations":[{"why":"supplies the flag-algebra PSD machinery that converts an asymptotic density inequality into a semidefinite programming certificate.","marker":"[11]"},{"why":"provides the computational workflow used to generate the semidefinite program and its approximate solution.","marker":"[13]"},{"why":"the semidefinite solver whose approximate certificate is rounded into the final 1/9-certificate.","marker":"[4]"},{"why":"states the undirected triangle-plus-independent-triple bound that motivates the directed analogue.","marker":"[8]"},{"why":"supplies the K4-free special case and the stability argument on which the exact result builds.","marker":"[5]"},{"why":"independently proves the special case for oriented graphs with no transitive triangles.","marker":"[10]"},{"why":"the graph removal lemma, used in the stability proof to pass from a low t+i value to a K4-free underlying graph.","marker":"[1]"},{"why":"a classical theorem relating chromatic number and minimum degree, used to conclude that near-extremal K4-free graphs are 3-partite.","marker":"[2]"}],"fun_headline_variants":["Triple chance at least 1/9 in every oriented graph","1/9 floor: transitive or independent triples always","Unique extremal shape: cyclic blow-up hits 1/9 bound","Flag algebras prove tight 1/9 bound for oriented graphs","No oriented graph beats 1/9 on triple probabilities"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof leans on a computer calculation, mentioned but not fully documented in the paper, that checks the key certificate matrix satisfies the required inequalities; if that check cannot be reproduced or contains an error, the proof of the 1/9 bound is incomplete.","fun_headline_variants_meta":{"raw":{"variants":["Triple chance at least 1/9 in every oriented graph","1/9 floor: transitive or independent triples always","Unique extremal shape: cyclic blow-up hits 1/9 bound","Flag algebras prove tight 1/9 bound for oriented graphs","No oriented graph beats 1/9 on triple probabilities"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000586,"raw_usage":{"total_tokens":2721,"prompt_tokens":882,"completion_tokens":1839,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":1752}},"tokens_in":498,"tokens_out":1839,"duration_ms":12793,"temperature":1.0,"reasoning_tokens":1752,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:44:18.748601+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Independently verify in exact arithmetic the matrix displayed in Section 9: check positive definiteness and all 42 inequalities c_i - inner product(Q, A_i) >= 1/9. A single violated inequality, or a negative eigenvalue, would invalidate Theorem 1.2 as proved; alternatively, constructing an infinite sequence of oriented graphs with t(G)+i(G) < 1/9 - o(1) would refute the statement itself.","supporting_citations":[{"cited_title":"Razborov, Flag algebras, Journal of Symbolic Logic, 72(4):1239–1282, 2007","cited_arxiv_id":null,"evidence_quote":"supplies the flag-algebra PSD machinery that converts an asymptotic density inequality into a semidefinite programming certificate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the computational workflow used to generate the semidefinite program and its approximate solution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"the semidefinite solver whose approximate certificate is rounded into the final 1/9-certificate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"states the undirected triangle-plus-independent-triple bound that motivates the directed analogue."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the K4-free special case and the stability argument on which the exact result builds."},{"cited_title":"Pikhurko and E","cited_arxiv_id":null,"evidence_quote":"independently proves the special case for oriented graphs with no transitive triangles."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"the graph removal lemma, used in the stability proof to pass from a low t+i value to a K4-free underlying graph."},{"cited_title":"Andrásfai, P","cited_arxiv_id":null,"evidence_quote":"a classical theorem relating chromatic number and minimum degree, used to conclude that near-extremal K4-free graphs are 3-partite."}],"review_version":1}