Geodesic
Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\)
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A conjecture of Loebl, also known as the $(n/2 - n/2 - n/2)$ Conjecture, states that if $G$ is an $n$-vertex graph in which at least $n/2$ of the vertices have degree at least $n/2$, then $G$ contains all trees with at most $n/2$ edges as subgraphs. Applying the Regularity Lemma, Ajtai, Komlós and Szemerédi proved an approximate version of this conjecture. We prove it exactly for sufficiently large $n$. This immediately gives a tight upper bound for the Ramsey number of trees, and partially confirms a conjecture of Burr and Erdős.
DOI : 10.37236/514
Classification : 05C35, 05C55, 05C05, 05D10
Mots-clés : graphs, Loebl conjecture, subtrees 
@article{10_37236_514,
     author = {Yi Zhao},
     title = {Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\)},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/514},
     zbl = {1231.05142},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/514/}
}
TY  - JOUR
AU  - Yi Zhao
TI  - Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\)
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/514/
DO  - 10.37236/514
ID  - 10_37236_514
ER  - 
%0 Journal Article
%A Yi Zhao
%T Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\)
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/514/
%R 10.37236/514
%F 10_37236_514
Yi Zhao. Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\). The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/514

Cité par Sources :