|
|
|
| |
|
|
|
 |
|
|
| KAIST Discrete Math Seminar |
|
|
|
|
|
|
|
 |
Title |
|
| |
Date |
2013-01-04 |
|
| |
Host |
|
|
| |
Place |
KAIST |
|
| |
File |
 |
|
|
|
| |
 Abstract : The cube graph Qn is the skeleton of the n-dimensional cube. It is an n-regular graph on 2n vertices. The Ramsey number r(Qn, Ks) is the minimum N such that every graph of order N contains the cube graph Qn or an independent set of order s. Burr and Erdős in 1983 asked whether the simple lower bound r(Qn, Ks) ≥ (s-1)(2n -1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound |
|
|
 |
|
|
|
.jpg)
