Sam Mattheus, Francesco Pavese, Leo Storme
Published 2017-04-03Version 1
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\H{o}s-R\'enyi 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\H{o}s-R\'enyi 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.
On the $k$-independence number of graphs
A new class of polynomials from to the spectrum of a graph, and its application to bound the $k$-independence number
Relation between the skew-rank of an oriented graph and the independence number of its underlying graph
![QR code for arXiv:1704.00487 [math.CO]](http://oss.arxitics.com/images/favicon.svg)