2014/03/18 by Michael Tait, Tait, Michael, Craig Timmons +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1403.4489
The authors would like to thank Jason Williford for noticing an error in the proof of Theorem 1.2 in the previous version. This error has now been corrected
arxiv created 2014/08/10 · arxiv updated 2014/08/12
Determining the maximum number of edges in an n-vertex C4-free graph is a well-studied problem that dates back to a paper of Erdős from 1938. One of the most important families of C4-free graphs are the Erdős-Rényi orthogonal polarity graphs. We show that the Cayley sum graph constructed using a Bose-Chowla Sidon set is isomorphic to a large induced subgraph of the Erdős-Rényi orthogonal polarity graph. Using this isomorphism we prove that the Petersen graph is a subgraph of every sufficiently large Erdős-Rényi orthogonal polarity graph.