The \( (n/2n/2n/2) \) conjecture
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
The (\(n/2\)\(n/2\)\(n/2\)) conjecture (proposed by Erdös, Füredi, Loebl and Sós [2])
Let \(G\) be a graph with \(n\) vertices and suppose at least \(n/2\) vertices have degree at least \(n/2\). Then \(G\) contains any tree on at most \(n/2\) vertices.Ajtai, Komlós and Szemerédi [1] proved the following asymptotic version: If \( G\) has \( n\) vertices and at least \( (1+ \epsilon) n/2\) vertices have degree at least \( (1+ \epsilon) n/2\), then \( G\) contains any tree on at most \( n/2\) vertices if \( n\) is large enough (depending on \( \epsilon\)).
Komlós and Sós[2] conjectured the following generalization:
Let \( G\) be a graph with \( n\) vertices and suppose at least \( n/2\) vertices have degree at least \( k\). Then \( G\) contains any tree with \( k\) vertices.
Bibliography  

1  M. Ajtai, J. Komlós and E. Szemerédi,
On a conjecture of Loebl,
Proc. of the 7th International Conference on Graph Theory, Combinatorics, and Algorithms,
(Kalamazoo, Michigan, 1992), 11351146, Wiley, New York, 1995.

2 
P. Erdös, Z. Füredi, M. Loebl and V. T. Sós,
Discrepancy of trees,
Combinatorics and its Applications to Regularity
and Irregularity of Structures, (W. A. Deuber and V. T. Sós, eds),
Studia Sci. Math. Hungar. 30 (1995), 4757.
