The Library
Dense Hfree graphs are almost (Χ(H)1)partite
Tools
Allen, Peter. (2010) Dense Hfree graphs are almost (Χ(H)1)partite. Electronic Journal of Combinatorics, Vol.17 (No.1:R21). ISSN 10971440
PDF
WRAP_Allen_Dense_hFree_Graphs.pdf  Requires a PDF viewer. Download (199Kb) 
Official URL: http://www.combinatorics.org/index.html
Abstract
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently
extended the classical AndrasfaiErdosSos theorem to cover general graphs. We
prove, without using the Regularity Lemma, that the following stronger statement
is true.
Given any (r+1)partite graph H whose smallest part has t vertices, there exists
a constant C such that for any given ε>0 and sufficiently large n the following is
true. Whenever G is an nvertex graph with minimum degree
δ(G)≥(1 −
3/3r−1 + ε)n,
either G contains H, or we can delete f(n,H)≤Cn2−1/t edges from G to obtain an
rpartite graph. Further, we are able to determine the correct order of magnitude
of f(n,H) in terms of the Zarankiewicz extremal function.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Mathematics  
Library of Congress Subject Headings (LCSH):  Graph theory  
Journal or Publication Title:  Electronic Journal of Combinatorics  
Publisher:  Electronic Journal of Combinatorics  
ISSN:  10971440  
Official Date:  29 January 2010  
Dates: 


Volume:  Vol.17  
Number:  No.1:R21  
Status:  Peer Reviewed  
Access rights to Published version:  Open Access  
Funder:  Engineering and Physical Sciences Research Council (EPSRC)  
Grant number:  EP/D063191/1 (EPSRC)  
References:  [1] N. Alon and B. Sudakov, Hfree graphs of large minimum degree, Elec. J. Combin. 

URI:  http://wrap.warwick.ac.uk/id/eprint/3285 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year