𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Erdős and Rényi Conjecture

✍ Scribed by Saharon Shelah

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
178 KB
Volume
82
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

Affirming a conjecture of Erdo s and Re nyi we prove that for any (real number) c 1 >0 for some c 2 >0, if a graph G has no c 1 (log n) nodes on which the graph is complete or edgeless (i.e., G exemplifies |G | Ä % (c 1 log n) 2

2 ), then G has at least 2 c 2 n non-isomorphic (induced) subgraphs. 1998 Academic Press 0. INTRODUCTION Erdo s and Re nyi [ER] conjectured (letting I(G) denote the number of (induced) subgraphs of G up to isomorphism and Rm(G) be the maximal number of nodes on which G is complete or edgeless):

(V) for every c 1 >0 for some c 2 >0 for n large enough for every graph G n with n points,

They succeeded in proving a parallel theorem which replaces Rm(G) with the bipartite version:

It is well known that Rm(G n ) 1 2 log n. On the other hand, Erdo s [Er7] proved that for every n for some graph G n , Rm(G n ) 2 log n. In his construction G n is quite a random graph; it seems reasonable that any Article No. TA972845

📜 SIMILAR VOLUMES

A Note on a Conjecture of Erdős
A Note on a Conjecture of Erdős and Rosenfeld
✍ Jorge Jiménez-Urroz 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 78 KB

We prove a special case of a conjecture of Erdo s and Rosenfeld regarding factor difference sets of integers.

Erdős–Turán Type Theorems on Qua
Erdős–Turán Type Theorems on Quasiconformal Curves and Arcs
✍ Vladimir Andrievskii; Hans-Peter Blatt 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 210 KB

The theorems of Erdo s and Tura n mentioned in the title are concerned with the distribution of zeros of a monic polynomial with known uniform norm along the unit interval or the unit disk. Recently, Blatt and Grothmann (Const. Approx. 7 (1991), 19 47), Grothmann (``Interpolation Points and Zeros of

On Four Colored Sets with Nondecreasing
On Four Colored Sets with Nondecreasing Diameter and the Erdős–Ginzburg–Ziv Theorem
✍ David J. Grynkiewicz 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 197 KB

A set X; with a coloring D: X ! Z m ; is zero-sum if P x2X DðxÞ ¼ 0: Let f ðm; rÞ (let f zs ðm; 2rÞ) be the least N such that for every coloring of 1; . . . ; N with r colors (with elements from r disjoint copies of Z m ) there exist monochromatic (zero-sum) m-element subsets B 1 and B 2 ; not neces