Premium
On the independence number of graphs related to a polarity
Author(s) -
Mattheus Sam,
Pavese Francesco,
Storme Leo
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22442
Subject(s) - hypergraph , independence number , mathematics , combinatorics , discrete mathematics , independence (probability theory) , graph , statistics
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 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 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 [On the independence number of the ErdŐs‐RÉnyi and projective norm graphs and a related hypergraph, J. Graph Theory, 56 (2007), pp. 113‐127, Open Problem 3].