What is the lower bound of $k$ such that any $k$-regular graph $G$ on $n$ vertices contains a $t$-clique? This is a Ramsey Theory problem I've been playing around with for a few days. It's possible there is a really obvious solution I haven't seen yet.
I am trying to find a lower bound $s$ such that $k > s$ implies any $k$-regular graph $G$ on $n$ vertices is guaranteed to have a $t$-clique. I denote the lower bound $s$ as $s(t)$.
It is not difficult to show that $s(3)=\frac{n}{2}$. So $k>s(3)=\frac{n}{2}$ implies all $k$-regular graphs on $n$ vertices contain a 3-clique. I conjecture that $\frac{n}{2}+1\leq s(4)\leq \frac{2n}{3}$. Clearly $s(t) \leq n-1$ for any $t$. Note that I am only focusing sufficiently large $n$ to avoid any errors, such as $n \geq t$.
 A: Without any restrictions on the structure of the graph, the graph with the most edges that avoids a $t$-clique is the Turán graph, which is a complete $(t-1)$-partite graph whose parts are as equal as possible.
In particular, if $n$ is divisible by $t-1$, we can have a complete $(t-1)$-partite graph with $t-1$ parts of size $\frac{n}{t-1}$, which is regular of degree $(1 - \frac1{t-1})n$. So in this case, we have $s(t) = (1 - \frac1{t-1})n$: any regular graph with higher degree will have more edges than the Turán graph, so it will contain a $t$-clique.
That's the easy answer. When $n$ is not divisible by $t-1$, this is still an upper bound on $s(t)$, but things can get messier...

Even $s(3)$ is interesting for odd $n$: it is not just $\frac{n-1}{2}$. I can prove that for odd $n$, $s(3) \le \frac25n$, which is achievable for multiples of $5$: just take a blow-up of the $5$-cycle. I don't know what happens when $n$ is odd and not divisible by $5$.
Pick a vertex $u$ in an $s$-regular triangle-free graph $G$. Its neighborhood $N(u)$ must be an independent set of size $s$. If $v \in N(u)$, then its neighborhood $N(v)$ is another, disjoint independent set of size $s$. Greedily extend $N(u)$ and $N(v)$ to a maximal pair of two disjoint independent sets $S, T$ with $|S|, |T| \ge s$: every vertex outside $S \cup T$ should have neighbors in both $S$ and $T$.
Because $n$ is odd and $G$ is regular, it cannot be bipartite, but $G[S \cup T]$ certainly is bipartite. So there must be some vertex $w \notin S \cup T$, with neighbors both in $S$ and in $T$.
Since $|N(w) \cap S| + |N(w) \cap T| \le |N(w)| = s$, without loss of generality $|N(w) \cap S| \le \frac s2$. Now to finish, let $x \in N(w) \cap S$.
The two sets $N(w)$ and $N(x)$ are disjoint (or else we'd get a triangle) and each has size $s$. Moreover, $N(w)$ misses at least $\frac s2$ vertices of $S$, and none of those can be in $N(x)$ either (since $S$ is an independent set and $x \in S$). So altogether $n \ge |N(w)| + |N(x)| + |S - N(w)| \ge \frac52s$, or $s \le \frac25n$.

Actually, this paper shows that for $t \ge 4$, $s(t) = (1 - \frac1{t-1})n - \Theta(1)$ no matter the value of $n$: we're off from the optimal result by only a constant error. Moreover, $s(3) = \frac 25n - \Theta(1)$ for all odd $n$, so nothing worse that usual happens when $n$ is not divisible by $5$.
In general, if we replace the $3$-clique by other graphs with chromatic number $3$, and we look at the corresponding problem, it is still hard for odd $n$.
An apparently well-known result, Andrásfai's theorem, generalizes my argument for $s(3)$ by showing that if $G$ is a triangle-free graph with minimum degree $\delta(G) > \frac{2n}{5}$, then $G$ is bipartite. So of course, if $n$ is odd and $G$ is $s$-regular, since $G$ cannot be bipartite, we must have $s \le \frac{2n}{5}$.
