Bipartite Tur\'an problems for ordered graphs

Abhishek Methuku; Istv\'an Tomon

REVIEW 3 major objections 4 minor 20 references

Bipartite Tur\'an problems for ordered graphs

T0 review · 3 major / 4 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 Column-t-partite zero-one matrices have extremal number at most $n^{2-1/t+1/(2t^2)+o(1)}$, and t×t-partite matrices reach the conjectured exponent $n^{2-1/t+o(1)}$.

desk verdict A solid, genuinely useful paper whose main new exponent for column-t-partite matrices rests on a repairable constant mismatch in the recursion; Theorem 2 and the method itself hold up. read the letter →

arxiv 1908.03189 v1 pith:6OGYMJDE submitted 2019-08-08 math.CO

Abhishek Methuku , István Tomon This is my paper · ORCID

classification math.CO MSC 05C3505D40

keywords zero-onematricesextremalnumbersorderedgraphsTuráncolumn-t-partitedependentrandomchoicedensityincrementbipartite

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

The paper proves upper bounds on the maximum number of 1-entries in an $n\times n$ zero-one matrix that avoids a fixed pattern $A$. For any column-$t$-partite pattern—one that splits into $t$ column bands with at most one 1 per row in each band—the extremal number is below $n^{2-1/t+1/(2t^2)+o(1)}$. For patterns that are $t$-partite in both directions, the stronger bound $n^{2-1/t+o(1)}$ holds, matching the exponent conjectured for the one-sided case. These are ordered analogues of classical Turán-type results for bipartite graphs with bounded degree in one class, and the proofs combine a density-increment recursion with dependent random choice.

What carries the argument

The central mechanism is a density-increment lemma (Lemma 6) that counts copies of $K_{u,t}$ in an $m\times n$ matrix avoiding $A$. If many such copies exist, then one of $k$ horizontal blocks contains a density of $K_{u,t}$ copies amplified by a constant factor; the proof uses a dependent random choice-style double counting of 'light' $K_{u,t}$ copies split by the horizontal blocks that witness them, together with a hypergraph lemma (Lemma 5) that bounds the number of edges in an interval $t$-partite hypergraph with no complete $t$-partite subhypergraph. Lemma 10 amplifies $K_{u,t}$ counts to $K_{u+1,t}$ counts, and Claim 11 verifies that throughout the recursion the count stays large enough for Lemma 6 to apply. In the $t\times t$-partite case, Lemma 9 applies the same block restriction in both dimensions, producing a $k^2$-block density increment.

What would settle it

Take a small column-2-partite matrix $A$ that is not row-2-partite, such as the $4\times4$ example in Figure 1, and compute $\mathrm{ex}(n,A)$ for $n = 5,\dots,15$ by integer programming. If for some fixed $\varepsilon>0$ any value reaches $n^{13/8+\varepsilon}$, Theorem 1 as stated is false; if the values stay near $n^{3/2}$ or below, they are consistent with the theorem and with the conjecture that the $+1/(2t^2)$ slack is unnecessary.

Watch

Extended reading notes

Core claim

The central discovery is that the extremal number of a forbidden zero-one matrix is controlled by its partiteness in the column direction, and that restricting to submatrices that are $t$-partite in both directions yields the conjectured exponent. Concretely, Theorem 1 states $\mathrm{ex}(n,A) < n^{2-1/t+1/(2t^2)+o(1)}$ for every column-$t$-partite $A$, and Theorem 2 states $\mathrm{ex}(n,A) < n^{2-1/t+o(1)}$ for every $t\times t$-partite $A$. The proof constructs a nested sequence of submatrices, each a horizontal (or vertical) block of the previous one, and forces the density of complete bipartite patterns $K_{u,t}$ to grow geometrically while the matrix shrinks; the contradiction is that a $1\times n$ or $1\times 1$ matrix cannot hold the mandated number of such patterns. Theorem 13 adds that every $x$-monotone cycle matrix has extremal number $O(n^{3/2})$.

Load-bearing premise

The recursion collapses unless at every step the chosen submatrix contains at least $C\max\{(n/k^i)^u, n^t\}$ copies of the complete bipartite pattern $K_{u,t}$; this retention bound, verified as Claim 11, is the load-bearing premise.

Editorial extensions

If this is right

For every column-$t$-partite matrix $A$, $\mathrm{ex}(n,A) < n^{2-1/t+1/(2t^2)+o(1)}$; in particular, for $t=2$ this is $n^{13/8+o(1)}$.
For every $t\times t$-partite matrix $A$, $\mathrm{ex}(n,A) < n^{2-1/t+o(1)}$, which is sharp up to the $o(1)$ term provided the lower bound $\mathrm{ex}(n,K_{t,t})=\Theta(n^{2-1/t})$ holds.
The $t\times t$ case covers all $2\times2$-partite matrices, so patterns corresponding to disjoint unions of cycles have extremal number at most $n^{3/2+o(1)}$.
Every $x$-monotone cycle matrix $A$ satisfies the stronger bound $\mathrm{ex}(n,A)=O(n^{3/2})$ (Theorem 13), complementing the $t=2$ case of Theorem 2.
Because ordered bipartite graphs correspond to zero-one matrices, these bounds carry over to ordered Turán numbers: an ordered bipartite graph whose bi-adjacency matrix is column-$t$-partite has ordered extremal number at most $n^{2-1/t+1/(2t^2)+o(1)}\log n$.

Reading between the lines

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

The slack $1/(2t^2)$ in Theorem 1 is likely an artifact of the copy-count amplification (Lemma 10); replacing it with a lossless count of $K_{u,t}$ copies would remove the slack and prove the conjectured exponent for column-$t$-partite matrices.
The $u$-varying recursion of Section 4—where the tracked parameter $u$ rises as the matrix shrinks—should extend to matrices with at most $t$ ones per row, which is exactly the open Conjecture 16; the authors note their method works for a large class but not all such matrices.
For ordered cycles, Theorem 13 suggests the extremal number is governed by geometric $x$-monotonicity rather than cycle length; if true, non-monotone cycles would be the natural candidates for larger extremal numbers, and settling the $\Theta(n^{4/3})$ conjecture for all 6-cycles would require breaking this geometric constraint.
The telescoping identity used to define the decreasing exponent sequence $\lambda_u$ is a purely algebraic device; the same recursion style could set exponents for other extremal problems on ordered structures with a layered partiteness condition.

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.

Desk Editor's Note

read the letter

Methuku–Tomon is a real contribution, but I want you to know about a gap in the proof of Theorem 1 before citing it as-is. The paper proves new upper bounds for extremal numbers of ordered bipartite graphs, and the proof technique—layering a density-increment argument on dependent random choice—is the most interesting part. Theorem 2, giving ex(n,A) < n^{2 - 1/t + o(1)} for t x t-partite A, looks correct and essentially settles the exponent for that family. Theorem 13, the O(n^{3/2}) bound for x-monotone cycles, is also new and appears sound. The counting arguments in Sections 2 and 3 are detailed, and I verified the main steps without finding issues.

The soft spot is Section 4. Lemma 6 is stated and proved with a factor u!/(4 r^{u-1} u^u) per block. But when the proof of Theorem 1 applies the lemma, it writes the factor as u!/(4 r^{u-1} u^{u-1}). The chosen k satisfies k^delta = 4 r^{U-1} U^{U-1}/U!, which would be fine for the stronger factor u^{u-1} but is not enough for what Lemma 6 actually gives. With the lemma as written, each step of the recursion loses an extra factor U, and that propagates through z steps, so the lower bound in Claim 11 is not established. This is exactly the kind of constant slip a referee should catch, and it is fixable—set k^delta = 4 r^{U-1} U^U/U! and the argument goes through. But as written, the proof of Theorem 1 is incomplete. Theorems 2 and 13 are not affected by this.

Minor issues: the vertical block definition uses m instead of n, and the acknowledgment mentions a master thesis but gives no citation. Both are small.

This paper deserves a serious referee. The reader's ACCEPT is close to my own view, except that I would make acceptance conditional on repairing the Section 4 constants. It should be a major revision, not a rejection, because the core ideas are sound and the gap is technical. I would cite this paper, but only after the fix.

Referee Report

3 major / 4 minor

Summary. The paper studies extremal numbers of zero-one matrices (equivalently, bipartite ordered graphs) under the containment relation of deleting rows/columns and turning 1s to 0s. The main results are Theorem 1, which asserts that every column-t-partite matrix A satisfies ex(n,A) < n^{2-1/t+1/(2t^2)+o(1)}, and Theorem 2, which improves this to ex(n,A) < n^{2-1/t+o(1)} when A is both row- and column-t-partite. The proofs use a density-increment recursion over horizontal (and, in Theorem 2, vertical) blocks, combined with dependent-random-choice-type counting of K_{u,t} copies. Section 3 proves Theorem 2 via an extension of the block lemma, Section 4 proves Theorem 1 by counting K_{u,t} with a varying u and handling jumps with a copy-amplification lemma, and Section 5 proves ex(n,A)=O(n^{3/2}) for x-monotone cycles. The paper ends with open problems, including a conjecture for matrices with at most t ones per row.

Significance. If correct, Theorem 2 gives the conjectured exponent 2-1/t for the t-by-t-partite case, and Theorem 1 gives the first general upper bound for column-t-partite matrices that is within an additive 1/(2t^2) of the conjectured value; these are natural ordered analogues of the Furedi/Alon-Krivelevich-Sudakov bounds for bipartite graphs of bounded degree in one class. The proof method, a block-based density increment with a K_{u,t} counting lemma and a jump step, is original and the constants are explicit and not fitted to the conclusion. The paper is largely self-contained and includes a clean proof of the ordered-hypergraph lemma (Lemma 5). However, as written, several constant-level errors in Sections 3 and 4 are load-bearing for the main theorems, so the paper needs a substantive revision before the results can be considered established.

major comments (3)

[Section 4, definition of k and application of Lemma 6] The printed definition k = ceil((U!/(4 r^{U-1} U^{U-1}))^{1/delta}) gives k^delta = U!/(4 r^{U-1} U^{U-1}), which is smaller than 1 for every allowed U and r, so after the ceiling one obtains k=1 and the recursive shrinking of Mi fails. What the proof needs is the reciprocal value: after Lemma 6, the factor gained per step is at least u!/(4 r^{u-1} u^u k), so to conclude N_{u,i+1} >= N_{u,i}/k^{1+delta} one requires k^delta >= 4 r^{u-1} u^u / u! for every u <= U, with the worst case u=U. Additionally, the text uses the factor u!/(4 r^{u-1} u^{u-1}) instead of the u^u factor that Lemma 6 actually proves; with the corrected Lemma 6 constant the correct requirement is k^delta >= 4 r^{U-1} U^U / U!. Since Claim 11 is the premise for every application of Lemma 6 in the recursion, this is a load-bearing error: choosing the correct k repairs the proof, but the current text does not.
[Section 4, jump-case exponent after Lemma 10] In the jump handling for t+1 <= u <= U, the paper claims the identity u*lambda_u + eps - (1+delta)(lambda_u - lambda_{u+1}) = u*lambda_{u+1} - t/(u+1) + eps - delta. Substituting lambda_u - lambda_{u+1} = t/((u-1)(u+1)) gives (u-1)lambda_u + lambda_{u+1} = u*lambda_{u+1} + t/(u+1), not minus t/(u+1). With the printed minus sign, after applying Lemma 10 the exponent is smaller than the claimed (u+1)lambda_{u+1} + (2u+1)/(2u)*eps by 2t/u, a constant deficit in the exponent that cannot be absorbed by the factor 1/2. Thus the lower bound N_{u+1,i+1} >= n^{(u+1)lambda_{u+1}+eps} does not follow as written. The sign should be plus, after which the jump argument goes through; but this correction must be made explicitly.
[Section 3, Lemma 9 constants] The proof of Lemma 9 sets C = 4 s^{t-1} t^t k / t! * C' with C' = max{C(t,t,r,s,k), C(t,t,s,r,k)}. After the first application of Lemma 6 to the horizontal blocks, the block M' contains N' >= t!/(4 r^{t-1} t^t k) * N copies, so with N >= C n^t one gets N' >= (s/r)^{t-1} C' n^t. If r > s, this is smaller than the C' n^t threshold needed to apply the symmetric Lemma 6 a second time. This can be repaired by taking C = 4 max(r,s)^{t-1} t^t k / t! * C' (or by applying the two block directions in the opposite order), but as written the proof of Theorem 2 has a gap whenever A has more rows than columns.

minor comments (4)

[Definition 2] The definition of vertical block uses the column indices (p-1)m/k+1, ..., pm/k; since the matrix is m x n and columns are indexed up to n, this should use n rather than m.
[Lemma 6, Claim 7] In the statement of Claim 7, the set N(i1,i2,...,it) should be N(i1,i2,...,iu); the subscript t appears to be a typo.
[Lemma 15, Case 1] In Case 1 of Lemma 15, the pigeonhole step says 'there exists i in [r]' but the summation is over the k horizontal blocks; this should be i in [k].
[Lemma 9 proof] In the second application of Lemma 6, the matrix M'' is a vertical block of M' (hence a block of the original partition), not a horizontal block of M'; the wording 'horizontal block M''' is a slip.

Circularity Check

0 steps flagged · score 1.0 of 10

No load-bearing circularity: the main theorems are proved by self-contained density increments, with self-citations confined to context and provenance.

full rationale

Walking the derivation chain, Theorem 1 is proved by assuming ex(n,A) >= n^{2-1/t+1/(2t^2)+epsilon}, fixing k, delta, and lambda_u, and recursively constructing submatrices M_i whose K_{u,t}-counts satisfy explicit lower bounds. The lower bounds in Claim 11 are derived from the weight hypothesis and the induction invariants, not from the theorem's conclusion. Lemma 6, the engine of the recursion, is proved by counting light copies of K_{u,t} and invoking Lemma 5, whose proof uses Erdős's hypergraph result; none of these ingredients asserts the target bound. Theorem 2 and Theorem 13 follow the same pattern: repeated density amplification yields a matrix too small to contain the required number of complete bipartite subgraphs, so the contradiction is produced internally rather than imported from the desired conclusion. The self-citations present in the paper, such as the reference to Kórádi--Tardos--Tomon--Weidert for acyclic matrices and to Győri--Korándi--Methuku--Tomon--Tompkins--Vizer for ordered cycles, are motivational or contextual and are not used to justify the new bounds. The acknowledgment that Section 5 originates from a master thesis supervised by the second author is a provenance statement; the section gives a full proof, so it does not substitute a citation for an argument. The skeptical concern about the u^{u-1} factor in Section 4 is a possible arithmetic correctness issue, not a circularity, because even if the factor is wrong, the argument is not assuming what it is trying to prove. No parameter is fitted to the target exponent, no uniqueness theorem from the authors' prior work is invoked, and no known result is merely renamed. Accordingly, there is no significant circularity, and the score reflects only de minimis, non-load-bearing self-citation and provenance overlap.

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

No empirical or fitted parameters appear in this paper. Constants such as epsilon, k, delta, and C are pure proof parameters that are absorbed into the o(1) term. The proofs rest on standard convexity facts, Erdos's hypergraph theorem, and the Pach-Tardos translation framework. There are no invented physical or combinatorial entities.

assumptions (3)

standard math Standard convexity and bounds for generalized binomial coefficients.
Section 1.1 states the binomial coefficient properties used in the counting arguments of Lemmas 4, 10, and 14.
standard math Erdos's theorem that a t-partite t-uniform hypergraph with more than n^{t - 1/s^{t-1}} edges contains a complete t-partite subhypergraph with parts of size s.
Invoked in Lemma 5 to force the interval-ordered complete t-partite hypergraph that contradicts A-freeness; cited as reference [7].
standard math The Pach-Tardos translation between ordered graph extremal numbers and zero-one matrix extremal numbers.
Used in Section 1 to justify working in matrix language; it frames the problem but is not used to prove the matrix upper bounds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Bipartite Tur\'an problems for ordered graphs." pith.science (2026). https://pith.science/paper/6OGYMJDE

@misc{pith2026190803189,
  author       = {Pith},
  title        = {Pith review of: Bipartite Tur\'an problems for ordered graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6OGYMJDE}},
  note         = {Machine review of arXiv:1908.03189}
}

abstract

A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete some rows and columns of $M$, and turn some 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $n\times n$ sized matrix $M$ that does not contain $A$. A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $ex(n,A)<n^{2-\frac{1}{t}+\frac{1}{2t^{2}}+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $ex(n,A)<n^{2-\frac{1}{t}+o(1)}$. Our proof combines a novel density-increment-type argument with the celebrated dependent random choice method. Results about the extremal numbers of zero-one matrices translate into results about the Tur\'an numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most $t$ 1-entries in each row corresponds to a bipartite ordered graph with maximum degree $t$ in one of its vertex classes. Our results are partially motivated by a well known result of F\"uredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes, then $ex(n,H)=O(n^{2-\frac{1}{t}})$. The aim of the present paper is to establish similar general results about the extremal numbers of ordered graphs.

Figures

Figures reproduced from arXiv: 1908.03189 by the authors.

**Figure 2.** Decomposing A into a copy of K2,2 and an x-monotone cycle of shorter length. Now let s ≥ 3. Let a, b ∈ [k] be the two indices such that A(a, 1) = A(b, 1) = 1. As A is x-monotone, either A(a, 2) = 1 or A(b, 2) = 1, otherwise the vertical line between the second and third columns intersects more than two horizontal lines in the drawing of A. Without loss of generality, let A(a, 2) = 1. Let A′ be the r ×(s−1) sized mat… view at source ↗

**Figure 3.** The six matrices corresponding to cycles of length [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 18 canonical work pages

[1]

N. Alon, M. Krivelevich, B. Sudakov, Tur´ an numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput., 12 (2003): 477–494

work page 2003
[2]

N. Alon, L. R´ onyai, T. Szab´ o, Norm-graphs: variations and applications, Journal of Combinatorial Theory, Series B, 76 (2) (1999): 280–290

work page 1999
[3]

C. T. Benson, Minimal Regular Graphs of Girths Eight and Twelve, Canadian Journal of Mathematics, 18 (1966): 1091–1094

work page 1966
[4]

J. A. Bondy, M. Simonovits, Cycles of even length in graphs, Journal of Combinatorial Theory, Series B, 16 (1974): 97–105

work page 1974
[5]

Conlon, J

D. Conlon, J. Lee, On the extremal number of subdivisions. arXiv preprint (2018), arXiv:1807.05008

arXiv 2018
[6]

Davenport, A

H. Davenport, A. Schinzel, A combinatorial problem connected with diﬀerential equati ons, American Journal of Mathematics, The Johns Hopkins Univers ity Press, 87 (3) (1965): 684–694

work page 1965
[7]

Erd˝ os, On extremal problems of graphs and generalized graphs, Israel J

P. Erd˝ os, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964): 183–190

work page 1964
[8]

Erd˝ os, A

P. Erd˝ os, A. H. Stone, On the structure of linear graphs. Bull. Amer. Math. Soc. 52 (1946): 1087–1091

work page 1946

Show all 20 references

[9]

F¨ uredi,On a Tur´ an type problem of Erd˝ os.Combinatorica, 11 (1) (1991): 75–79

Z. F¨ uredi,On a Tur´ an type problem of Erd˝ os.Combinatorica, 11 (1) (1991): 75–79

1991
[10]

F¨ uredi, P

Z. F¨ uredi, P. Hajnal, Davenport-Schinzel theory of matrices, Discrete Mathematics 103 (1992): 233–251

1992
[11]

F¨ uredi, T

Z. F¨ uredi, T. Jiang, A. Kostochka, D. Mubayi, J. Verstr a¨ ete,A splitting theorem for ordered hypergraphs, arXiv preprint, arXiv:1906.03342

1906 arXiv
[12]

Grzesik, O

A. Grzesik, O. Janzer, Z. L. Nagy, The Tur´ an number of blow-ups of tree, arXiv preprint (2019), arXiv:1904.07219v1

2019 arXiv
[13]

Gy˝ ori, D

E. Gy˝ ori, D. Kor´ andi, A. Methuku, I. Tomon, C. Tompkins, M. Vizer, On the Tur´ an number of some ordered even cycles, European Journal of Combinatorics 73 (2018): 81–88

2018
[14]

Janzer, Improved bounds for the extremal number of subdivisions, arXiv preprint (2018), arXiv:1809.00468

O. Janzer, Improved bounds for the extremal number of subdivisions, arXiv preprint (2018), arXiv:1809.00468

2018 arXiv
[15]

Kor´ andi, G

D. Kor´ andi, G. Tardos, I. Tomon, C. Weidert.On the Tur´ an number of ordered forests,Journal of Combinatorial Theory, Series A 165 (2019): 32–43

2019
[16]

J. Pach, G. Tardos, Forbidden paths and cycles in ordered graphs and matrices, Israel Journal of Mathematics 155 (2006): 359–380

2006
[17]

K˝ ov´ ari, V

T. K˝ ov´ ari, V. S´ os, P. Tur´ an,On a problem of K. Zarankiewicz, Colloquium Math. (1954): 50–57. 20

1954
[18]

Marcus, G

A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjec ture, Journal of Combinatorial Theory, Ser. A 107 (2004): 153–160

2004
[19]

Pettie, Degrees of nonlinearity in forbidden 0-1 matrix problems, Discrete Mathematics 311 (2011): 2396-2410

S. Pettie, Degrees of nonlinearity in forbidden 0-1 matrix problems, Discrete Mathematics 311 (2011): 2396-2410

2011
[20]

Tardos, On 0-1 matrices and small excluded submatrices, Journal of Combinatorial Theory, Ser

G. Tardos, On 0-1 matrices and small excluded submatrices, Journal of Combinatorial Theory, Ser. A 111 (2005): 266-288. 21

2005

Pith tools

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

[1] [1]

N. Alon, M. Krivelevich, B. Sudakov, Tur´ an numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput., 12 (2003): 477–494

work page 2003

[2] [2]

N. Alon, L. R´ onyai, T. Szab´ o, Norm-graphs: variations and applications, Journal of Combinatorial Theory, Series B, 76 (2) (1999): 280–290

work page 1999

[3] [3]

C. T. Benson, Minimal Regular Graphs of Girths Eight and Twelve, Canadian Journal of Mathematics, 18 (1966): 1091–1094

work page 1966

[4] [4]

J. A. Bondy, M. Simonovits, Cycles of even length in graphs, Journal of Combinatorial Theory, Series B, 16 (1974): 97–105

work page 1974

[5] [5]

Conlon, J

D. Conlon, J. Lee, On the extremal number of subdivisions. arXiv preprint (2018), arXiv:1807.05008

arXiv 2018

[6] [6]

Davenport, A

H. Davenport, A. Schinzel, A combinatorial problem connected with diﬀerential equati ons, American Journal of Mathematics, The Johns Hopkins Univers ity Press, 87 (3) (1965): 684–694

work page 1965

[7] [7]

Erd˝ os, On extremal problems of graphs and generalized graphs, Israel J

P. Erd˝ os, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964): 183–190

work page 1964

[8] [8]

Erd˝ os, A

P. Erd˝ os, A. H. Stone, On the structure of linear graphs. Bull. Amer. Math. Soc. 52 (1946): 1087–1091

work page 1946