On the independence number of graphs related to a polarity

2017/04/03 by Sam Mattheus, Francesco Pavese, Mattheus, Sam +3
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Graph theory and applications #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1704.00487

Abstract

We investigate the independence number of two graphs constructed from a polarity of PG(2,q). For the first graph under consideration, the Erdős-Rényi graph ER_q, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper we consider the Erdős-Rényi hypergraph of triangles H_q. We determine the exact magnitude of the independence number of H_q, q even. This solves a problem posed by Mubayi and Williford.

Related

• Independent sets in polarity graphs
• Eigenvalue bounds for independent sets
• On the chromatic number of the Erdős-Rényi orthogonal polarity graph
• Triangle-free induced subgraphs of polarity graphs
• Orthogonal polarity graphs and Sidon sets