thecs
Jan11-11, 06:35 PM
Hello :smile: I need some help understanding the following paper by P. Erdős:
SOME REMARKS ON THE THEORY OF GRAPHS, 1947
http://www1.spms.ntu.edu.sg/~ymchee/MAS790_files/prob.pdf
In particular, how to prove (2):
0.5logn < A(n)
Where n is the size of the vertex set in a graph G, and A(n) is the largest integer such that either G or G' contains a complete subgraph of order A(n).
Also I'm more interested in the case where G is bipartite.
Any help would be great, thanks.
SOME REMARKS ON THE THEORY OF GRAPHS, 1947
http://www1.spms.ntu.edu.sg/~ymchee/MAS790_files/prob.pdf
In particular, how to prove (2):
0.5logn < A(n)
Where n is the size of the vertex set in a graph G, and A(n) is the largest integer such that either G or G' contains a complete subgraph of order A(n).
Also I'm more interested in the case where G is bipartite.
Any help would be great, thanks.