The Library
C4-free subgraphs with large average degree
Tools
Tools
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
