Densest graphs without triangles or 4-cycles on 54 or more vertices

Find a 54-vertex graph with no triangles or 4-cycles and more than 185 edges, or prove 185 is the maximum.

shoal State the problem, from CSPLib 71a8d70 · 2周前历史

34 行 · 3.3 KB 原始文件永久链接历史

1	# Densest graphs without triangles or 4-cycles on 54 or more vertices
2
3	How many edges can a graph on $n$ vertices have if it contains no cycle of length 3 or 4? The exact answer is known for every $n \le 53$, after computer searches by Brendan McKay in 2022 and 2023, and the first open case is $n = 54$.
4
5	## Problem
6
7	The girth of a graph is the length of its shortest cycle. Let $f(n)$ be the largest number of edges in a simple graph on $n$ vertices with girth at least 5, that is, with no triangle and no 4-cycle (OEIS A006856). Determine $f(54)$, and more generally $f(n)$ for $n \ge 54$. CSPLib also asks for the number of non-isomorphic graphs attaining $f(n)$, and for the analogous values with larger forbidden girth.
8
9	## Background
10
11	The question is CSPLib problem 52, proposed by Michael Codish, Alice Miller, Patrick Prosser and Peter Stuckey. Garnick, Kwong and Lazebnik (1993) determined $f(n)$ for $n \le 24$ and gave constructive lower bounds up to $n = 200$; later searches pushed the exact values to $n = 32$. The extremal graphs include famous objects: the unique graph attaining $f(50) = 175$ is the Hoffman–Singleton graph. The growth of $f(n)$ for large $n$, whether $f(n) \sim (n/2)^{3/2}$, is Erdős Problem #573 and is a different, asymptotic question from the exact values asked here.
12
13	## What is known
14
15	- Values for $n = 1, \dots, 53$ are listed in the OEIS; for example $f(32) = 85$, $f(50) = 175$, $f(52) = 178$ and $f(53) = 181$.
16	- Brendan McKay computed $f(33), \dots, f(52)$ in March 2022 and $f(53)$ in January 2023.
17	- McKay also reported the lower bounds $f(54) \ge 185$, $f(55) \ge 189$ and $f(56) \ge 193$ (January 2023), so the open question for $n = 54$ is whether some graph of girth at least 5 has 186 or more edges.
18	- Mehrabian et al. (2024) ran AlphaZero and tabu search on this problem and improved the lower bounds for most sizes between 64 and 190, but for $n = 54$, 55 and 56 their best graphs only match McKay's bounds.
19
20	## What would count as progress
21
22	- A graph on 54 vertices with girth at least 5 and at least 186 edges (or a similar improvement for a larger $n$), given as an edge list. A script checks the edge count and the absence of 3- and 4-cycles in milliseconds.
23	- A proof that $f(54) = 185$, for example an exhaustive search with symmetry breaking whose code and logs can be rerun, together with the number of extremal graphs. This is a separate and harder kind of progress than a construction.
24
25	## References
26
27	1. D. K. Garnick, Y. H. H. Kwong and F. Lazebnik (1993). Extremal graphs without three-cycles or four-cycles. Journal of Graph Theory 17, 633–645. https://doi.org/10.1002/jgt.3190170511
28	2. A. Mehrabian, A. Anand, H. Kim et al. (2024). Finding increasingly large extremal graphs with AlphaZero and tabu search. IJCAI 2024; arXiv:2311.03583. https://arxiv.org/abs/2311.03583
29	3. OEIS A006856, Maximal number of edges in n-node graph of girth at least 5, with values and bounds by B. D. McKay (2022, 2023). https://oeis.org/A006856
30	4. Erdős Problem #573, on the asymptotic growth of these numbers. https://www.erdosproblems.com/573
31
32	## Source
33
34	Imported from [CSPLib prob052](https://www.csplib.org/Problems/prob052/), curated by CSPLib editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.