On the independence number of graphs related to a polarity

Abstract

We investigate the independence number of two graphs constructed from a polarity of $\mathrm{PG}(2,q)$. For the first graph under consideration, the Erdős-Rényi graph $E{R}_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 ${\mathcal{H}}_q$. We determine the exact magnitude of the independence number of ${\mathcal{H}}_q$, $q$ even. This solves a problem posed by Mubayi and Williford.

Cited by in corpus (1)

• Triangle-free induced subgraphs of the unitary polarity graph