Distinct degrees and homogeneous sets

DOI10.1016/J.JCTB.2022.11.004arXiv2204.05932MaRDI QIDQ6396342FDOQ6396342

Laurenţiu Ploscaru, Eoin Long

Publication date: 12 April 2022

Abstract: In this paper we investigate the extremal relationship between two well-studied graph parameters: the order of the largest homogeneous set in a graph $G$ and the maximal number of distinct degrees appearing in an induced subgraph of $G$, denoted respectively by $hom(G)$ and $f(G)$. Our main theorem improves estimates due to several earlier researchers and shows that if $G$ is an $n$-vertex graph with $hom(G)geq{n}^{1/2}$ then $$. The bound here is sharp up to the $o(1)$-term, and asymptotically solves a conjecture of Narayanan and Tomon. In particular, this implies that $maxhom(G),f(G)geq{n}^{1/2-o(1)}$ for any $n$-vertex graph $G$,which is also sharp. The above relationship between $hom(G)$ and $f(G)$ breaks down in the regime where $hom(G)<n^{1/2}$. Our second result provides a sharp bound for distinct degrees in biased random graphs, i.e. on $$. We believe that the behaviour here determines the extremal relationship between $hom(G)$ and $f(G)$ in this second regime. Our approach to lower bounding $f(G)$ proceeds via a translation into an (almost) equivalent probabilistic problem, and it can be shown to be effective for arbitrary graphs. It may be of independent interest.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

This page was built for publication: Distinct degrees and homogeneous sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6396342)