A note on regular Ramsey graphs |
| |
Authors: | Noga Alon Sonny Ben‐Shimon Michael Krivelevich |
| |
Institution: | 1. School of Computer Science and School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel;2. School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel;3. School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel |
| |
Abstract: | We prove that there is an absolute constant C>0 so that for every natural n there exists a triangle‐free regular graph with no independent set of size at least \({{C}}\sqrt{{{n}}\log{{n}}}\). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 244–249, 2010 |
| |
Keywords: | Ramsey theory regular graphs |
|
|