Abstract: Determining the maximum number of edges in an -vertex -free graph is a well-studied problem that dates back to a paper of ErdH{o}s from 1938. One of the most important families of -free graphs are the ErdH{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 ErdH{o}s-R'enyi orthogonal polarity graph. Using this isomorphism we prove that the Petersen graph is a subgraph of every sufficiently large ErdH{o}s-R'enyi orthogonal polarity graph.
Recommendations
Cites work
- A translate of Bose-Chowla B₂-sets
- Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size
- Combinatorial problems in finite fields and Sidon sets
- Diameters and Eigenvalues
- Eigenvalue bounds for independent sets
- Extremal graphs without 4-cycles
- Graphs without four-cycles
- Graphs without quadrilaterals
- My Graph
- On Graphs that do not Contain a Thomsen Graph
- On the existence of a primitive quadratic of trace 1 over \(GF(p^ m)\)
- On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
- On the number of edges of quadrilateral-free graphs
- Sidon sets and graphs without 4-cycles
- Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle
- Theorems in the additive theory of numbers
- Well distribution of Sidon sets in residue classes
- Über ein Problem von K. Zarankiewicz
Cited in
(3)
This page was built for publication: Orthogonal polarity graphs and Sidon sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811198)
