We investigate the independence number of two graphs constructed from a polarity of (Formula presented.). For the first graph under consideration, the Erdős-Rényi graph (Formula presented.), 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 (Formula presented.). We determine the exact magnitude of the independence number of (Formula presented.), (Formula presented.) 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].
On the independence number of graphs related to a polarity / Mattheus, Sam; Pavese, Francesco; Storme, Leo. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - STAMPA. - 92:2(2019), pp. 96-110. [10.1002/jgt.22442]
On the independence number of graphs related to a polarity
Francesco Pavese;
2019-01-01
Abstract
We investigate the independence number of two graphs constructed from a polarity of (Formula presented.). For the first graph under consideration, the Erdős-Rényi graph (Formula presented.), 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 (Formula presented.). We determine the exact magnitude of the independence number of (Formula presented.), (Formula presented.) 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].I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
