Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-12-01T09:02:17.776Z Has data issue: false hasContentIssue false
  • English
  • Français

Problem Collection of the DIMANET Mátraháza Workshop, 22–28 October 1995

Published online by Cambridge University Press:  01 January 1999

Get access Rights & Permissions [Opens in a new window]

Abstract

1. Noga Alon

Paul Erdős [2] conjectured in 1979 that, if in a graph on n vertices any set of [lfloor ]√n[rfloor ] vertices contains at least one edge, then there is a set of [lfloor ]√n[rfloor ] vertices that contains Ω(√n log n) edges. As observed by Erdős, this result, if true, is tight. During the workshop, and after discussions with various participants including Cameron, Erdős, Gunderson and Krivelevich, we found a proof of this conjecture, combining some probabilistic arguments with the main result of [1] (see also [3]). Hopefully this will appear in a forthcoming paper, where we also plan to include a simple proof of an extension of the main result of [1].

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 8 , Issue 1-2 , January 1999 , pp. 185 - 192
Copyright
© 1999 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)