C 4 C_{4} -free subgraphs of high degree with geometric applications

Zach Hunter, Aleksa Milojević, Benny Sudakov, István Tomon · 2025

Read C 4 C_{4} -free subgraphs of high degree with geometric applications by Zach Hunter, Aleksa Milojević, Benny Sudakov, István Tomon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-23942.txt.

Introduction

Zach Hunter, Aleksa Milojevic, Benny Sudakov, and Istvan Tomon prove a new structural result about graphs that avoid four-cycles. Their paper came out in 2025. A graph is a set of points joined by lines, and a four-cycle is a loop of four points.

They show that any graph with a given average degree holds one of two things. It either holds a large part with no four-cycles and still high degree, or a dense part with very many lines. They then use that split to settle many geometry problems of the same family. In each case their bounds are the best possible.

Catalog record

CREATORZach Hunter, Aleksa Milojević, Benny Sudakov, István Tomon
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE149 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-23942

Browse the full library · About the Tower of Babel