Pith. sign in

REVIEW 4 major objections 5 minor 13 references

On the local structure of oriented graphs -- a case study in flag algebras

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every oriented graph has at least 1/9 transitive or independent triples.

desk verdict 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. read the letter →

arxiv 1908.06480 v2 pith:KYK54YYT submitted 2019-08-18 math.CO

Shoni Gilboa , Roman Glebov , Dan Hefetz , Nati Linial , Avraham Morgenstern This is my paper · ORCID
classification math.CO MSC 05C2005C3590C22
keywords orientedgraphsinduceddensitiesflagalgebrastransitivetrianglesindependenttriplessemidefiniteprogrammingstabilityextremalconstruction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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]$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [§9, certificate matrix Qbar (pp. 28–29)] 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.
  2. [§7, paragraph after Lemma 7.2 (p. 26)] 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.
  3. [§10, Lemma 10.1 (p. 29)] 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.
  4. [§9, rounding procedure (p. 29)] 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.
minor comments (5)
  1. [§10, proof of Proposition 10.6] There is a typo: 'orineted graph' should read 'oriented graph'.
  2. [§2, p. 5] 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.
  3. [Figures 8–10, §5] 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.
  4. [§4, Proposition 4.6] 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.
  5. [§12, Concluding remarks] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 1/9-certificate is an explicit finite object and the lower bound does not reduce to the extremal construction.

full rationale

The paper's derivation chain is self-contained and non-circular. The upper bound tau <= 1/9 comes from the explicit cyclic blow-up B_n in Observation 1.3, and the lower bound is obtained by constructing a 1/9-certificate for the SDP (20): Theorem 3.3 and Proposition 3.6 show that any such certificate yields tau >= 1/9, while Section 9 displays an explicit 15x15 matrix Qbar with algebraic entries. The certificate inequalities c_i - <Qbar, Abar_i> >= 1/9 are finite algebraic conditions, not consequences of assuming the theorem. The kernel vectors and sharp-graph equations in Sections 6 and 7 are derived as necessary conditions on any certificate, using only B_n and B_epsilon_n as test graphs; Remark 6.2 explicitly states that this is conditional reasoning. The extremal constructions are used to constrain a certificate, but the validity of the displayed certificate is an independent finite check. Lemma 2.1 is attributed in passing to [9], which shares an author, but it is fully proved in the text, so that citation is not load-bearing. External results such as Theorem 10.2 from [5] are used for stability, not for the main asymptotic bound. The unverified 'We have verified by computer software' assertion in Section 9 is a real auditability concern, but it is not circularity: the displayed matrix is an explicit mathematical object whose positive definiteness and inequalities can in principle be checked directly, and no fitted parameter is relabeled as a prediction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data. The value 1/9 is fixed by the explicit cyclic blow-up example, not by fitting the certificate. The proof relies on the standard flag algebra framework, on external black-box results about K4-free graphs, and on unshipped computer calculations that verify the final certificate.

assumptions (5)
  • standard math Flag algebra PSD machinery: Theorems 3.3 and Proposition 3.6 convert a PSD certificate into the lower bound tau >= 1/9.
    This framework is developed in the paper from Razborov's flag algebra calculus and is used throughout to justify the SDP formulation.
  • domain assumption The list G1,...,G42 exhausts the 4-vertex oriented graphs up to isomorphism.
    Section 5 uses this finite enumeration to set up SDP (20); the paper does not prove exhaustiveness, though it is a finite combinatorial fact.
  • domain assumption Theorem 10.2 of [5] gives a quantitative lower bound on independent triples in K4-free undirected graphs.
    Imported in Section 10 and used in Corollary 10.4 to derive the structural stability statement that underlies Theorem 1.4.
  • domain assumption Graph removal lemma from [1] and the Andrasfai-Erdos-Sos theorem from [2].
    Used in Sections 4, 10, and 11 to pass from near-minimal t+i to K4-freeness and then to 3-partiteness.
  • ad hoc to paper The computer calculations (flagmatic, csdp, Mathematica) and the verification of the displayed certificate matrix are correct.
    The paper provides no code or reproducible pipeline; Sections 5, 7, and 9 depend on these unshipped computations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the local structure of oriented graphs -- a case study in flag algebras." pith.science (2026). https://pith.science/paper/KYK54YYT

@misc{pith2026190806480,
  author       = {Pith},
  title        = {Pith review of: On the local structure of oriented graphs -- a case study in flag algebras},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KYK54YYT}},
  note         = {Machine review of arXiv:1908.06480}
}
abstract

Let $G$ be an $n$-vertex oriented graph. Let $t(G)$ (respectively $i(G)$) be the probability that a random set of $3$ vertices of $G$ spans a transitive triangle (respectively an independent set). We prove that $t(G) + i(G) \geq \frac{1}{9}-o_n(1)$. Our proof uses the method of flag algebras that we supplement with several steps that make it more easily comprehensible. We also prove a stability result and an exact result. Namely, we describe an extremal construction, prove that it is essentially unique, and prove that if $H$ is sufficiently far from that construction, then $t(H) + i(H)$ is significantly larger than $\frac{1}{9}$. We go to greater technical detail than is usually done in papers that rely on flag algebras. Our hope is that as a result this text can serve others as a useful introduction to this powerful and beautiful method.

Figures

Figures reproduced from arXiv: 1908.06480 by the authors.

Figure 1
Figure 1. An example of (left to right) a type σ, two flags F1, F2 over σ and a graph G. dimension. In Section 9 we complete the proof of Theorem 1.2 by finding an approximate certificate for the projected problem with the aid of the computer, rounding it, and pulling it back to a certificate for the original problem. In Section 10 we prove Theorem 1.4. In Section 11 we use Theorem 1.4 to prove Theorem 1.5. Finally, in Sectio… view at source ↗
Figure 2
Figure 2. An example of a rooting of G over σ, and the three flags over σ with one petal which appear with a positive probability in that rooting [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. The three 2-vertex flags over the 1-vertex type. 2.1 The flag probability matrix Let Σ be a finite set of types and let F be a finite set of flags over types in Σ. For a graph G we define the matrix AG (which depends on Σ and F as well) as follows. It is an ∣F∣ × ∣F∣ matrix whose (F1, F2) entry is p(F1, F2;G). It readily follows from the definition of p(F1, F2;G) that the entries of AG are rational numbers and that … view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: The four 3-vertex undirected graphs. Proposition 3.6. If SDP (2) has an α-certificate, then its optimum is at least α, whence τ ≥ α by Theorem 3.3. Proof. Let Q be an α-certificate for (2). Suppose that the matrix ∑ m i=1 piAGi is PSD, where p1, . . . , pm ≥ 0 and ∑ m …
Figure 5
Figure 5. Figure 5: The 1-vertex type, and the two 2-vertex flags over it. [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: The 7 isomorphism types of oriented graphs of order 3. First proof. As in the first proof of Goodman’s inequality, we denote the number of edges in G by m. Also, let c(G) denote the probability that a randomly chosen set of 3 vertices of G induces a cyclic triangle. It…
Figure 7
Figure 7. Figure 7: The 42 isomorphism types of oriented graphs of order 4. Therefore, by the graph removal lemma, there is an undirected K4-free graph G (1) n , obtained from G (0) n by deleting at most n(n−1) 1080 edges. Therefore i(G (1) n ) ≤ i(G (0) n ) + 6 1 1080 = i(Gn) + 1 180 ≤ t…
Figure 8
Figure 8. Figure 8: Flags over the empty type [PITH_FULL_IMAGE:figures/full_fig_p019_8.png]
Figure 10
Figure 10. Figure 10: Flags over the edge type. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_10.png]
Figure 11
Figure 11. Figure 11: The sharp graphs. The graphs in the first row are abundant in [PITH_FULL_IMAGE:figures/full_fig_p025_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    N. Alon, R. A. Duke, H. Lefmann, V. Rödl and R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), 80–109

    work page 1994

  2. [2]

    Andrásfai, P

    B. Andrásfai, P. Erdős, V. Sós, On the connection between chromatic number, maxi- mal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218

    work page 1974

  3. [3]

    Conlon and J

    D. Conlon and J. Fox, Graph removal lemmas, Surveys in Combinatorics, Cambridge University Press, 2013, 1–50

    work page 2013

  4. [4]

    CSDP, A C Library for Semidefinite Programming, https://projects.coin-or.org/Csdp

    work page

  5. [5]

    S. Das, H. Huang, J. Ma, H. Naves and B. Sudakov, A problem of Erdős on the minimum number of k-cliques, J. Combinatorial Theory Ser. B 103 (2013), 344–373

    work page 2013

  6. [6]

    Erdős and L

    P. Erdős and L. Moser, On the representation of directed graphs as unions of orderings, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964), 125–132. 43

    work page 1964

  7. [7]

    On applications of Razborov's flag algebra calculus to extremal 3-graph theory

    V. Falgas-Ravry, E. R. Vaughan, On applications of Razborov’s flag algebra calculus to extremal 3-graph theory. arXiv:1110.1623 (2011)

    work page Pith review arXiv 2011

  8. [8]

    A. W. Goodman, On sets of acquaintances and strangers at any party, Am. Math Mon 66 (1959), 778–783

    work page 1959

Show all 13 references
  1. [9]

    Huang, N

    H. Huang, N. Linial, H. Naves, Y. Peled, and B. Sudakov, On the 3-local profiles of graphs, Journal of Graph Theory, 76, (2014), 236–248

    2014

  2. [10]

    Pikhurko and E

    O. Pikhurko and E. R. Vaughan, Minimum Number of k-Cliques in Graphs with Bounded Independence Number, Combinatorics Probability and Computing, 22 (2013), 910–934

    2013

  3. [11]

    Razborov, Flag algebras, Journal of Symbolic Logic, 72(4):1239–1282, 2007

    A. Razborov, Flag algebras, Journal of Symbolic Logic, 72(4):1239–1282, 2007

    2007

  4. [12]

    Stearns, The voting problem, Amer

    R. Stearns, The voting problem, Amer. Math. Monthly 66 (1959), 761–763

    1959

  5. [13]

    E. R. Vaughan, Flagmatic software, A tool for researchers in extremal graph theory. http://www.maths.qmul.ac.uk/ ev/flagmatic/ 44

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.