 Author
 Year
 2015
 Title
 A Precise Threshold for QuasiRamsey Numbers
 Journal
 SIAM Journal on Discrete Mathematics
 Volume  Issue number
 29  3
 Pages (fromto)
 16701682
 Document type
 Article
 Faculty
 Faculty of Science (FNWI)
 Institute
 Kortewegde Vries Institute for Mathematics (KdVI)
 Abstract

We consider the variation of Ramsey numbers introduced by Erdös and Pach [J. Graph Theory, 7 (1983), pp. 137147], where instead of seeking complete or independent sets we only seek a $t$homogeneous set, a vertex subset that induces a subgraph of minimum degree at least $t$ or the complement of such a graph. For any $\nu > 0$ and positive integer $k$, we show that any graph $G$ or its complement contains as an induced subgraph some graph $H$ on $\ell \ge k$ vertices with minimum degree at least $\frac12(\ell1) + \nu$ provided that $G$ has at least $k^{\Omega(\nu^2)}$ vertices. We also show this to be the best possible in a sense. This may be viewed as correction to a result claimed in [P. Erdös and J. Pach, J. Graph Theory, 7 (1983), pp. 137147]. For the above result, we permit $H$ to have order at least $k$. In the harder problem, where we insist that $H$ have exactly $k$ vertices, we do not obtain sharp results, although we show a way to translate results of one form of the problem to the other.
© 2015, Society for Industrial and Applied Mathematics
Read More: http://epubs.siam.org/doi/10.1137/14097313X  URL
 go to publisher's site
 Language
 English
 Permalink
 http://hdl.handle.net/11245/1.501366
 Downloads
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.