
The Library
C4-free subgraphs with large average degree
Tools
Montgomery, Richard, Pokrovskiy, Alexey and Sudakov, Benny (2021) C4-free subgraphs with large average degree. Israel Journal of Mathematics, 246 (1). pp. 55-71. doi:10.1007/s11856-021-2236-8 ISSN 0021-2172.
|
PDF
WRAP-C4-free-subgraphs-with-large-average-degree-Montgomery-21.pdf - Accepted Version - Requires a PDF viewer. Download (450Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s11856-021-2236-8
Abstract
Motivated by a longstanding conjecture of Thomassen, we study how large the average degree of a graph needs to be to imply that it contains a C4-free subgraph with average degree at least t. Kühn and Osthus showed that an average degree bound which is double exponential in t is sufficient. We give a short proof of this bound, before reducing it to a single exponential. That is, we show that any graph G with average degree at least 2ct2log t (for some constant c > 0) contains a C4-free subgraph with average degree at least t. Finally, we give a construction which improves the lower bound for this problem, showing that this initial average degree must be at least t3−o(1).
Item Type: | Journal Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||
Library of Congress Subject Headings (LCSH): | Graph theory, Combinatorial analysis, Probabilities | ||||||||||
Journal or Publication Title: | Israel Journal of Mathematics | ||||||||||
Publisher: | Magnes Press | ||||||||||
ISSN: | 0021-2172 | ||||||||||
Official Date: | December 2021 | ||||||||||
Dates: |
|
||||||||||
Volume: | 246 | ||||||||||
Number: | 1 | ||||||||||
Page Range: | pp. 55-71 | ||||||||||
DOI: | 10.1007/s11856-021-2236-8 | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||
Date of first compliant deposit: | 21 June 2022 | ||||||||||
Date of first compliant Open Access: | 25 November 2022 | ||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year