论文标题
独特的程度和均匀套件
Distinct degrees and homogeneous sets
论文作者
论文摘要
在本文中，我们研究了两个经过良好的图形参数之间的极端关系：图$ g $中最大的均质集的顺序和在诱导的$ g $中出现的最大程度的最大程度，分别由$ \ hom（g）$（g）$和$ f（g）$表示。我们的主要定理改进了由于较早的研究人员而提高的估计，并表明，如果$ n $ v $是$ \ hom（g）\ geq n^{1/2} $，则$ f（g）\ geq \ geq \ geq \ big（{n}/{n}/{\ hom（g）} \ big）此处的界限急切到$ O（1）$ - 术语，渐近地解决了Narayanan和Tomon的猜想。特别是，这意味着对于任何$ n $ -n $ -vertex Graph $ g $，$ \ max \ {\ hom（g），f（g）\ geq n^{1/2 -o（1）} $，这也很敏锐。 $ \ hom（g）$和$ f（g）$之间的上述关系在$ \ hom（g）<n^{1/2} $中分解。我们的第二个结果为有偏见的随机图，即$ f \ big（g（n，p）\ big）$提供了明显的界限。我们认为，这里的行为决定了第二个制度中$ \ hom（g）$和$ f（g）$之间的极端关系。我们的下限$ f（g）$的方法通过翻译成（几乎）等效的概率问题进行了进行，并且可以证明它对任意图有效。它可能具有独立的利益。
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 $f(G) \geq \big ( {n}/{\hom (G)} \big )^{1 - o(1)}$. 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 $\max \{ \hom (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 $f\big (G(n,p) \big )$. 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.
