Scholarlink

<p>We obtain assumption-free, non-asymptotic, uniform bounds on the product of the height and the width of uniformly random trees with a given degree sequence, conditioned Bienaymé trees and simply generated trees. We show that for a tree of size <i>n</i>, this product is <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n\log n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in probability, answering a question by Addario-Berry [<CitationRef CitationID="CR2">2</CitationRef>]. The order of this bound is tight in this generality.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Tight universal bounds on the height times the width of random trees

  • 期刊论文

  • 发表日期：

    2026年1月8日

查看全文
  • Serte Donderwinkel,
  • Robin Khanfir

摘要

We obtain assumption-free, non-asymptotic, uniform bounds on the product of the height and the width of uniformly random trees with a given degree sequence, conditioned Bienaymé trees and simply generated trees. We show that for a tree of size n, this product is \(O(n\log n)\) O ( n log n ) in probability, answering a question by Addario-Berry [2]. The order of this bound is tight in this generality.