Montgomery, R;
Pokrovskiy, A;
Sudakov, B;
(2021)
C4-free subgraphs with large average degree.
Israel Journal of Mathematics
, 246
pp. 55-71.
10.1007/s11856-021-2236-8.
Preview |
Text
C4_free.pdf - Accepted Version Download (332kB) | Preview |
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).
| Type: | Article |
|---|---|
| Title: | C4-free subgraphs with large average degree |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s11856-021-2236-8 |
| Publisher version: | https://doi.org/10.1007/s11856-021-2236-8 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Science & Technology, Physical Sciences, Mathematics |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10142090 |
Archive Staff Only
 |
View Item |
