Description
Kedves Kombinatorikusok!
A december 12-i Kombinatorika szemináriumon (14:15, Nagyterem)
Laurentiu Ploscaru (Rényi Intézet)
ad elő
Distinct Degrees and Homogeneous Sets in Graphs
címmel.
Abstract: In this talk we investigate the extremal relationship between two well-known graph parameters: the order of a largest
homogeneous set in a graph $G$ and the maximal number of distinct degrees that appear in an induced
subgraph of $G$, denoted by $\hom (G)$ and $f(G)$ respectively. This topic has been well studied by several researchers over the last 40 years, beginning with Erd\H{o}s, Faudree and S\'os in the regime when $\hom (G) = O\big(\log |G|\big)$.
Our main theorem asymptotically settles this question, improving on multiple earlier estimates. More precisely, we show that any $n$-vertex graph $G$ satisfies:
\begin{align*}
f(G) \geq \min\left(\sqrt[3]{\frac {n^2}{\hom (G)} }\ ,\ \frac{n}{\hom(G)}\right) \cdot n^{-o(1)}.
\end{align*}
\indent This relationship is tight (up to the $n^{o(1)}$ term) for all possible values of $\hom (G)$, as demonstrated by appropriately generated Erd\H{o}s$-$Renyi random graphs. Our approach to lower bounding $f(G)$ proceeds via a translation into an (almost) equivalent probabilistic problem, which is effective for arbitrary graphs. Joint work with Eoin Long.
Mindenkit szeretettel várunk