Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Allen, Peter (2010)
Publisher: Electronic Journal of Combinatorics
Languages: English
Types: Article
Subjects: QA
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently\ud extended the classical Andrasfai-Erdos-Sos theorem to cover general graphs. We\ud prove, without using the Regularity Lemma, that the following stronger statement\ud is true.\ud Given any (r+1)-partite graph H whose smallest part has t vertices, there exists\ud a constant C such that for any given ε>0 and sufficiently large n the following is\ud true. Whenever G is an n-vertex graph with minimum degree\ud δ(G)≥(1 −\ud 3/3r−1 + ε)n,\ud either G contains H, or we can delete f(n,H)≤Cn2−1/t edges from G to obtain an\ud r-partite graph. Further, we are able to determine the correct order of magnitude\ud of f(n,H) in terms of the Zarankiewicz extremal function.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] N. Alon and B. Sudakov, H-free graphs of large minimum degree, Elec. J. Combin. 13 (2006), R19.
    • [2] B. Andr´asfai, P. Erd˝os, and V. T. S´os, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205-218.
    • [3] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281-285.
    • [4] P. Erd˝os, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183-190.
    • [5] P. Erd˝os and M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973), 323-334.
    • [6] P. Erd˝os and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087-1091.
    • [7] J. Koll´ar, L. R´onyai, and T. Szabo, Norm-graphs and bipartite Tur´an numbers, Combinatorica 16 (1996), 399-406.
    • [8] T. K¨ov´ari, V. T. S´os, and P. Tur´an, On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50-57.
    • [9] I. Reiman, U¨ber ein problem von K. Zarankiewicz, Acta. Math. Acad. Sci. Hungar. 9 (1958), 269-279.
    • [10] E. Szemer´edi, Regular partitions of graphs, Probl`emes combinatoires et th´eorie des graphes (Orsay, 1976), Colloques Internationaux CNRS, vol. 260, CNRS, 1978, pp. 399-401.
    • [11] P. Tur´an, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436-452.
    • [12] K. Zarankiewicz, Sur les relations sym´etriques dans l'ensemble fini, Colloq. Math. 1 (1947), 10-14.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article