Speaker
Description
We describe an explicit geometric construction of a vast parametrized family of graphs without $k$-cliques with bounded independence number generalizing triangle-free Ramsey graphs described by Codenotti, Pudlák and Resta and provide a new combinatorial proof for the upper bound on the independence number of the latter. We focus on triangle-free graphs and describe some families of such graphs with $n$ vertices and independence number $O(n^{\frac{2}{3}})$ which give us a constructive asymptotic lower bound $\Omega(t^{\frac{3}{2}})$ for Ramsey numbers $R(3, t)$ which achieves the best known constructive lower bound. We describe an additional family of graphs that don't match the best known bound but still have a polynomial independence number with regards to the number of vertices and are based on Euclidean geometry. We determine a necessary condition for parameters for which this family of graphs could yield better constructive asymptotic lower bounds on $R(s, t)$ than those currently known, again focusing on $R(3, t)$. We also present a linear approximation algorithm for finding the largest independent set in this parametrized family of graphs which is a $\frac{1}{2}$-approximation algorithm for a significant subfamily.
