Orthogonal polarity graphs and Sidon sets

DOI10.1002/JGT.21890zbMATH Open1339.05201arXiv1403.4489OpenAlexW2591824444MaRDI QIDQ2811198FDOQ2811198

Authors: Michael Tait, Craig Timmons 

Publication date: 10 June 2016

Published in: Journal of Graph Theory (Search for Journal in Brave)

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 ErdH{o}s from 1938. One of the most important families of $C_4$-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.

Full work available at URL: https://arxiv.org/abs/1403.4489

Recommendations

• Sidon sets and graphs without 4-cycles
• Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size
• Extremal graphs without 4-cycles
• Some extremal results on 4-cycles
• Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

zbMATH Keywords

Cayley sum graphBose-Chowla Sidon set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

• Eigenvalue bounds for independent sets
• Über ein Problem von K. Zarankiewicz
• On Graphs that do not Contain a Thomsen Graph
• Theorems in the additive theory of numbers
• Diameters and Eigenvalues
• Combinatorial problems in finite fields and Sidon sets
• Graphs without quadrilaterals
• On the number of edges of quadrilateral-free graphs
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size
• A translate of Bose-Chowla \(B_2\)-sets
• Sidon sets and graphs without 4-cycles
• Graphs without four-cycles
• Extremal graphs without 4-cycles
• My Graph
• On the existence of a primitive quadratic of trace 1 over \(GF(p^ m)\)
• Well distribution of Sidon sets in residue classes
• Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

Cited In (1)

• The apparent structure of dense Sidon sets

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)