Premium
On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
Author(s) -
Mubayi Dhruv,
Williford Jason
Publication year - 2007
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.20251
Subject(s) - mathematics , combinatorics , hypergraph , discrete mathematics , strongly regular graph , upper and lower bounds , graph , line graph , pathwidth , mathematical analysis
The Erdős‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that in many cases, this upper bound is sharp in the order of magnitude. Our result for the Erdős‐Rényi graph has the following reformulation: the maximum size of a family of mutually non‐orthogonal lines in a vector space of dimension three over the finite field of order q is of order q 3/2 . We also prove that every subset of vertices of size greater than q 2/2 + q 3/2 + O ( q ) in the Erdős‐Rényi graph contains a triangle. This shows that an old construction of Parsons is asymptotically sharp. Several related results and open problems are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 113–127, 2007