Session I.3 - Graph Theory and Combinatorics
Tuesday, June 13, 15:00 ~ 15:30
6th diagonal Ramsey number is at most 147
Jan Volec
Czech Technical University in Prague, Czeh Republic - This email address is being protected from spambots. You need JavaScript enabled to view it.
The diagonal Ramsey number $R(k)$ is the smallest order of a complete graph such that any $2$-coloring of its edges contain a monchromatic complete subgraph of order $k$. It is well known that \[a \cdot k 2^{k/2} \lt R(k) \lt (4-b)^k\] for some absolute constants $a \gt 0$ and $b \gt 0$. On the other extreme, we know that $R(3)=6$ and $R(4)=18$, but already the exact value of $R(5)$ is not known. Determining the exact value of $R(k)$ for small values of $k\ge5$ is a challenging problem, and a well known quote of Erdős says that if aliens invade the Earth and demand within a year the exact value of $R(6)$, then we should rather attempt to destroy the aliens than determine $R(6)$. In this talk, we use the flag algebra method to show $R(6)$ is at most $147$ improving on the previous upper bound $R(6) \le 161$.
Joint work with Sergey Norin (McGill University) and Jeremie Turcotte (McGill University).