On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph |
| |
Authors: | Dhruv Mubayi Jason Williford |
| |
Institution: | 1. Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, Illinois 60607;2. Department of Mathematics and Computer Science, Albion College, Albion Michigan 49224 |
| |
Abstract: | 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 q3/2. We also prove that every subset of vertices of size greater than q2/2 + q3/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 |
| |
Keywords: | eigenvalues independence number finite projective planes polarity graphs |
|
|