𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph

✍ Scribed by Dhruv Mubayi; Jason Williford

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
192 KB
Volume
56
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 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

📜 SIMILAR VOLUMES

A new upper bound for the independence n
A new upper bound for the independence number of edge chromatic critical graphs
✍ Rong Luo; Yue Zhao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 2 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) ≤ n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if ≥ 6. ᭧ 2010 Wiley

A lower bound on the independence number
A lower bound on the independence number of arbitrary hypergraphs
✍ Thiele, Torsten 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB 👁 3 views

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ v∈V f (d

Note on the reconstruction of infinite g
Note on the reconstruction of infinite graphs with a fixed finite number of components
✍ Thomas Andreae 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 1 views

For every positive integer c , we construct a pair G, , H, of infinite, nonisomorphic graphs both having exactly c components such that G, and H, are hypomorphic, i.e., G, and H, have the same families of vertex-deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G

A list version of Dirac's theorem on the
A list version of Dirac's theorem on the number of edges in colour-critical graphs
✍ Alexandr V. Kostochka; Michael Stiebitz 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 2 views

## Abstract One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 (1941) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension o

A. Christou and H. S. Rupprecht (eds). G
A. Christou and H. S. Rupprecht (eds). Gallium arsenide and related compounds 1987. Institute of Physics Conferences Series Number 91. Proceedings of the Fourteenth International Symposium on Gallium Arsenide and Related Compounds held in Heraklion, Crete 28. September—1. October 1987. Institute of Physics, Bristol and Philadelphia 1988, 834 Seiten, zahlreiche Abbildungen und Tabellen, Autorenindex, £ 55.00. ISBN 0–85498–182–9
✍ G. Kühn 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB