Large independent sets in all large subgraphs of a random graph
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
Problem (proposed by Erdös and Bollobás)
In a random graph (with edge probability \( \frac{1}{2}\), find the best
possible \(c \) such that
every subgraph on \( n^{\alpha} \) vertices will almost surely
contain an independent set of size \( c \log n \)
(where \( c \) depends on \(\alpha\) ).
Bibliography | |
---|---|
1 |
N. Alon, J. H. Spencer and P. Erdös,
The Probabilistic Method, Wiley and Sons, New York, 1992. (Link To sample sections.)
|