Upper bounds on the extremal number of the 4-cycle

• DOI: 10.48550/arxiv.2107.11601
• Publication Date: 2023-02-17
• Authors: Ma, Jie; Yang, Tianchi
• Keywords: FOS: Mathematics; Mathematics - Combinatorics; Combinatorics (math.CO); 0102 computer and information sciences; 01 natural sciences

AbstractWe obtain some new upper bounds on the maximum number of edges in ‐vertex graphs without containing cycles of length four. This leads to an asymptotically optimal bound on for a broad range of integers as well as a disproof of a conjecture of Erdős from 1970s which asserts that .