\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[hmargin=1in,vmargin=0.88in]{geometry} \usepackage{amsmath,amssymb} \usepackage{fancyvrb} \usepackage{xurl} \usepackage[hidelinks]{hyperref} \urlstyle{same} \setlength{\emergencystretch}{2em} \setcounter{secnumdepth}{0} \providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}} \title{A counterexample to the Erd\H{o}s triangle--four-cycle asymptotic} \author{Will Howe, Grant Huffman, Jensen Kohlmeyer, and Liam Kruer} \date{November 2026} \begin{document} \maketitle \begin{abstract} We construct an infinite family of finite simple graphs containing neither a triangle nor a four-cycle. Their edge counts exceed the conjectured leading asymptotic in Erd\H{o}s Problem 573 by a fixed positive factor. For every positive integer \(h\), put \(q=659^h\). The graph \(G_q\) has \[n_q=\frac{1307}{659}q^2-q, \qquad e_q=\frac{428875}{659^2}q^3-\frac{658}{659}q^2.\] Its limiting ratio to \((n_q/2)^{3/2}\) is \(1.0000452143352195\ldots\). The construction joins 47 affine three-part pieces along a common root part. A multiplicative partition of reciprocal field labels excludes four-cycles across the pieces, and an additive restriction retains enough internal edges while excluding triangles. \end{abstract} \section{1. Introduction}\label{introduction} Write \(\operatorname{ex}(n,\{C_3,C_4\})\) for the maximum number of edges of a simple graph on \(n\) vertices containing no subgraph isomorphic to either \(C_3\) or \(C_4\). Subgraphs throughout are ordinary subgraphs. Erd\H{o}s Problem 573 asks whether \[\operatorname{ex}(n,\{C_3,C_4\})\sim (n/2)^{3/2}.\] Theorem 1.1. For every positive integer \(h\), put \(q=659^h\). There is a finite simple \(\{C_3,C_4\}\)-free graph \(G_q\) with \[|V(G_q)|=\frac{1307}{659}q^2-q,\qquad e(G_q)=\frac{428875}{659^2}q^3-\frac{658}{659}q^2.\] Consequently, \[\limsup_{n\to\infty}\frac{\operatorname{ex}(n,\{C_3,C_4\})}{(n/2)^{3/2}} \ \geq\ L>1,\] where \[L=\frac{428875}{659^2}\left(\frac{1318}{1307}\right)^{3/2}.\] The original problem is recorded in {[}1{]}. Let \(z(n,C_4)\) denote the maximum number of edges in a bipartite \(C_4\)-free graph on \(n\) vertices. The relation \(z(n,C_4)\sim(n/2)^{3/2}\) makes the conjecture above equivalent to \(\operatorname{ex}(n,\{C_3,C_4\})/z(n,C_4)\to1\), the formulation in {[}3, Conjecture 1.1{]}. Theorem 1.1 disproves this limit. Determining the exact extremal function remains open. \section{2. Finite-field labels}\label{finite-field-labels} Set \(p=659\), a prime. Trial division by the primes at most \(\sqrt{659}<26\) suffices. For divisors \(2,3,5,7,11,13,17,19,23\), the respective remainders are \(1,2,4,1,10,9,13,13,15\). Let \(H\) be the subgroup of seventh powers in \(\mathbb F_p^\times\). Its order is \(94\), and it is the kernel of the map \(x\mapsto x^{94}\). It contains \(-1\). Put \[I=\{1,2,\ldots,7\},\qquad J=\{1,2,\ldots,10\}\subset\mathbb F_p.\] The values of \(i^{94}\) for \(i=1,\ldots,7\), reduced modulo \(659\), are \[1,\ 307,\ 144,\ 12,\ 389,\ 55,\ 410.\] They are distinct, so \(I\) represents the seven distinct cosets of \(H\). Choose a set \(M\) containing one representative from each pair \(\{\mu,-\mu\}\) in \(H\). Then \(|M|=47\), and every element of \(\mathbb F_p^\times\) has a unique representation \[\epsilon\mu i,\qquad \epsilon\in\{1,-1\},\quad \mu\in M,\quad i\in I.\] An explicit choice of \(M\) is recorded in Appendix A. Fix \(h\geq1\), put \(q=p^h\), and let \(F=\mathbb F_q\). The absolute trace is \[\tau(x)=x+x^p+\cdots+x^{p^{h-1}}.\] This is an \(\mathbb F_p\)-linear map from \(F\) to \(\mathbb F_p\). Its values lie in \(\mathbb F_p\) because \(\tau(x)^p=\tau(x)\). Its defining polynomial is nonzero and has degree \(p^{h-1}0.\] Equivalently, \[L^2=\frac{1471470125000}{1471337070937} =1+\frac{133054063}{1471337070937}>1.\] Therefore \(L=1.0000452143352195\ldots>1\). Lemmas 4.1 and 4.2 imply \(\operatorname{ex}(n_q,\{C_3,C_4\})\geq e_q\). Taking the limsup proves Theorem 1.1. \section{7. Relation to prior constructions}\label{relation-to-prior-constructions} Lv, Lu and Fang construct dense balanced three-partite graphs using affine matching equations {[}2, proof of Theorem 2, pp.~3-4{]}. For one of our leaf pairs, make the substitutions \[A=a/\mu,\quad B=-b,\quad C=c,\qquad X=x/\mu,\quad Y=y/\mu,\quad Z=z/\mu.\] The three edge equations become \[AB=X-Y,\qquad BC=Y-Z,\qquad CA=Z-X,\] which are the equations used in their construction. Their remark on page 4 extends the construction to prime powers by restricting a linear coordinate over the prime field. These affine equations and coordinate restrictions provide the local ingredients for the present construction. Here a single root part serves 47 leaf pairs. The multiplicative partition makes all leaf slope sets disjoint, and the reciprocal-label restrictions prevent the possible short cycles through the common root. Retaining 39 additive label pairs in each block gives the strict leading comparison in Section 6. Ma and Yang prove \(\operatorname{ex}(n,\{C_3,C_4\})\geq z(n,C_4)+c n^{5/4}\) for an absolute constant \(c>0\) and all \(n\geq7\) {[}3, Theorem 1.3{]}. Theorem 1.1 establishes a fixed multiplicative excess over the leading bipartite asymptotic along the orders \(n_q\). \section{Appendix A. Explicit finite certificate}\label{appendix-a.-explicit-finite-certificate} One explicit choice of the 47 multipliers is as follows. \[1,14,15,24,31,41,43,44,46,47,50,53\] \[57,63,73,80,83,85,91,108,118,128,136,139\] \[145,156,173,185,190,194,196,198,207,210,214,223\] \[225,232,262,274,286,296,299,302,304,323,325.\] Direct modular exponentiation gives \(\mu^{94}=1\) for each listed multiplier. They are distinct and all lie between 1 and 325, so no two are negatives modulo 659. They therefore select exactly one element from every sign pair in \(H\). \section{Acknowledgment of AI assistance}\label{acknowledgment-of-ai-assistance} OpenAI Codex assisted with the construction search, proof development, formalization, computational checks, and exposition. \section{References}\label{references} {[}1{]} Erd\H{o}s Problems, Problem 573. \url{https://www.erdosproblems.com/573}. Statement consulted November 12, 2026. {[}2{]} Zequn Lv, Mei Lu and Chunqiu Fang. Density of Balanced 3-Partite Graphs without 3-Cycles or 4-Cycles. The Electronic Journal of Combinatorics 29(4) (2022), P4.44. \url{https://doi.org/10.37236/10958}. {[}3{]} Jie Ma and Tianchi Yang. On extremal numbers of the triangle plus the four-cycle. Forum of Mathematics, Sigma 13 (2025), e154, 1-7. \url{https://doi.org/10.1017/fms.2025.10100}. See Conjecture 1.1. Will Howe. \href{mailto:howew@purdue.edu}{\nolinkurl{howew@purdue.edu}}. Grant Huffman (corresponding author). \href{mailto:huffma97@purdue.edu}{\nolinkurl{huffma97@purdue.edu}}. Jensen Kohlmeyer. \href{mailto:jenwin@purdue.edu}{\nolinkurl{jenwin@purdue.edu}}. Liam Kruer. \href{mailto:kruerl@purdue.edu}{\nolinkurl{kruerl@purdue.edu}}. \end{document}