Distinct degrees and homogeneous sets II
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929509654069248 |
|---|---|
| author | Long, Eoin Ploscaru, Laurentiu |
| author_facet | Long, Eoin Ploscaru, Laurentiu |
| contents | Given an $n$-vertex graph $G$, let $\hom (G)$ denote the size of a largest homogeneous set in $G$ and let $f(G)$ denote the maximal number of distinct degrees appearing in an induced subgraph of $G$. The relationship between these parameters has been well studied by several researchers over the last 40 years, beginning with Erdős, Faudree and Sós in the Ramsey regime when $\hom (G) = O(\log n)$.
Our main result here proves that any $n$-vertex graph $G$ with $\hom (G) \leq n^{1/2}$ satisfies
\begin{align*}
f(G) \geq \sqrt[3]{\frac {n^2}{\hom (G)} } \cdot n^{-o(1)}.
\end{align*}
This confirms a conjecture of the authors from a previous work, in which we addressed the $\hom (G) \geq n^{1/2}$ regime. Together, these provide the complete extremal relationship between these parameters (asymptotically), showing that any $n$-vertex graph $G$ satisfies
\begin{align*}
\max \Big ( f(G) \cdot \hom (G), \sqrt {f(G) ^3 \cdot \hom (G) } \Big ) \geq n^{1-o(1)}.
\end{align*}
This relationship is tight (up to the $n^{-o(1)}$ term) for all possible values of $\hom (G)$, from $Ω(\log n )$ to $n$, as demonstrated by appropriately generated Erdős $-$ Renyi random graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14134 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distinct degrees and homogeneous sets II Long, Eoin Ploscaru, Laurentiu Combinatorics 05D40, 05C07 (Primary), 05D10, 05C69, 05C80 (Secondary) Given an $n$-vertex graph $G$, let $\hom (G)$ denote the size of a largest homogeneous set in $G$ and let $f(G)$ denote the maximal number of distinct degrees appearing in an induced subgraph of $G$. The relationship between these parameters has been well studied by several researchers over the last 40 years, beginning with Erdős, Faudree and Sós in the Ramsey regime when $\hom (G) = O(\log n)$. Our main result here proves that any $n$-vertex graph $G$ with $\hom (G) \leq n^{1/2}$ satisfies \begin{align*} f(G) \geq \sqrt[3]{\frac {n^2}{\hom (G)} } \cdot n^{-o(1)}. \end{align*} This confirms a conjecture of the authors from a previous work, in which we addressed the $\hom (G) \geq n^{1/2}$ regime. Together, these provide the complete extremal relationship between these parameters (asymptotically), showing that any $n$-vertex graph $G$ satisfies \begin{align*} \max \Big ( f(G) \cdot \hom (G), \sqrt {f(G) ^3 \cdot \hom (G) } \Big ) \geq n^{1-o(1)}. \end{align*} This relationship is tight (up to the $n^{-o(1)}$ term) for all possible values of $\hom (G)$, from $Ω(\log n )$ to $n$, as demonstrated by appropriately generated Erdős $-$ Renyi random graphs. |
| title | Distinct degrees and homogeneous sets II |
| topic | Combinatorics 05D40, 05C07 (Primary), 05D10, 05C69, 05C80 (Secondary) |
| url | https://arxiv.org/abs/2409.14134 |