Can I read Ramsey Number Counterexample Checking and One Vertex Extension Linearly Bound by $s$ and $t$ on EtoBox?

Ramsey Number Counterexample Checking and One Vertex Extension Linearly Bound by $s$ and $t$ by Lehavi, Adam M. is a scholarly article available to read on EtoBox.

What is Ramsey Number Counterexample Checking and One Vertex Extension Linearly Bound by $s$ and $t$ about?

The Ramsey number $R(s,t)$ is the smallest integer $n$ such that all graphs of size $n$ contain a clique of size $s$ or an independent set of size $t$. $\mathcal{R}(s,t,n)$ is the set of all counterexample graphs without this property for a given $n$. We prove that if a graph $G_{n+1}$ of size $n+1$ has $\max\{s,t\}+1$ subgraphs in $\mathcal{R}(s,t,n)$, then $G_{n+1}$ is in $\mathcal{R}(s,t,n+1)$. Based on this, we introduce algorithms for one-vertex extension and counterexample checking with runtime linearly bound by $s$ and $t$. We prove the utility of these algorithms by verifying $\mathcal{R}(4,6,36)$ and $\mathcal{R}(5,5,43)$ are empty given current sets $\mathcal{R}(4,6,35)$ and $\mathcal{R}(5,5,42)$.

Author

Lehavi, Adam M.

Published

2024

Language

EN