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. 1
A Note on a Conjecture of Erdős and Rosenfeld
✍ Scribed by Jorge Jiménez-Urroz
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 78 KB
- Volume
- 78
- Category
- Article
- ISSN
- 0022-314X
No coin nor oath required. For personal study only.
✦ Synopsis
We prove a special case of a conjecture of Erdo s and Rosenfeld regarding factor difference sets of integers.
📜 SIMILAR VOLUMES
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
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