pith. sign in

arxiv: 1403.4489 · v3 · pith:3RKEHOWHnew · submitted 2014-03-18 · 🧮 math.CO

Orthogonal polarity graphs and Sidon sets

classification 🧮 math.CO
keywords graphorthogonalpolarityenyigraphsfreelargesidon
0
0 comments X
read the original abstract

Determining the maximum number of edges in an $n$-vertex $C_4$-free graph is a well-studied problem that dates back to a paper of Erd\H{o}s from 1938. One of the most important families of $C_4$-free graphs are the Erd\H{o}s-R\'enyi 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\H{o}s-R\'enyi orthogonal polarity graph. Using this isomorphism we prove that the Petersen graph is a subgraph of every sufficiently large Erd\H{o}s-R\'enyi orthogonal polarity graph.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.