A reminder: This is today. Please also note a change in topic.
---------------------------------------
On 2022-11-20 16:27, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon lecture this Thursday, 24 November given by Pranshu Gupta. Please find the talk details below.
Best regards, Misha Tyomkyn.
Ramsey simplicity of random graphs Pranshu Gupta University of Passau November 24, 2022, 12:20 in S6
Abstract A graph $G$ is \emph{$q$-Ramsey} for another graph $H$ if in any $q$-edge-colouring of $G$ there is a monochromatic copy of $H$, and the classic Ramsey problem asks for the minimum number of vertices in such a graph. This was broadened in the seminal work of Burr, Erd\H{o}s, and Lov'asz to the investigation of other extremal parameters of Ramsey graphs, including the minimum degree.
It is not hard to see that if $G$ is minimally $q$-Ramsey for $H$ we must have $\delta(G) \ge q(\delta(H) - 1) + 1$, and we say that a graph $H$ is \emph{$q$-Ramsey simple} if this bound can be attained. Grinshpun showed that this is typical of rather sparse graphs, proving that the random graph $G(n,p)$ is almost surely $2$-Ramsey simple when $\frac{\log n}{n} \ll p \ll n^{-2/3}$. In this paper, we explore this question further, asking for which pairs $p = p(n)$ and $q = q(n,p)$ we can expect $G(n,p)$ to be $q$-Ramsey simple. We resolve the problem for a wide range of values of $p$ and $q$; in particular, we uncover some interesting behaviour when $n^{-2/3} \ll p \ll n^{-1/2}$.
This is a joint work with Simona Boyadzhiyska, Dennis Clemens, and Shagnik Das.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz