# Expected number of induced subtrees shared by two independent copies of a
random tree

Boris Pittel  Department of Mathematics, The Ohio State University, Columbus,
Ohio 43210, USA<EMAIL_ADDRESS>
###### Abstract.

Consider a rooted tree $T$ with leaf-set $[n]$, and with all non-leaf vertices
having out-degree $2$, at least. A rooted tree $\mathcal{T}$ with leaf-set
$S\subset[n]$ is induced by $S$ in $T$ if $\mathcal{T}$ is the lowest common
ancestor subtree for $S$, with all its degree-2 vertices suppressed. A
“maximum agreement subtree” (MAST) for a pair of two trees $T^{\prime}$ and
$T^{\prime\prime}$ is a tree $\mathcal{T}$ with a largest leaf-set
$S\subset[n]$ such that $\mathcal{T}$ is induced by $S$ both in $T^{\prime}$
and $T^{\prime\prime}$. Bryant et al. [8] and Bernstein et al. [6] proved,
among other results, that for $T^{\prime}$ and $T^{\prime\prime}$ being two
independent copies of a random binary (uniform or Yule-Harding distributed)
tree $T$, the likely magnitude order of
$\text{MAST}(T^{\prime},T^{\prime\prime})$ is $O(n^{1/2})$. We prove this
bound for a wide class of random rooted trees : $T$ is a terminal tree of a
branching, Galton–Watson, process with an ordered-offspring distribution of
mean $1$, conditioned on “total number of leaves is $n$”.

###### Key words and phrases:

Random, terminal tree, asymptotics

###### 2010 Mathematics Subject Classification:

05C30, 05C80, 05C05, 34E05, 60C05

##  1\. Introduction, results

Consider a rooted binary tree $T$, with $n$ leaves labelled by elements from
$[n]$. We visualize this tree with the root on top and the leaves at bottom.
Given $S\subset[n]$, let $v(S)\in V(T)$ denote the lowest common ancestor of
leaves in $S$, ($\text{LCA}(S)$.) Introduce the subtree of $T$ formed by the
paths from $v(S)$ to leaves in $S$. Ignoring (suppressing) degree-2 vertices
of this subtree (except the root itself), we obtain a rooted binary tree with
leaf-set $S$. This binary tree is called “a tree induced by $S$ in $T$”.

Finden and Gordon [12] and Gordon [14] introduced a notion of a “maximum
agreement subtree” (MAST) for a pair of such trees $T^{\prime}$ and
$T^{\prime\prime}$: it is a tree $\mathcal{T}$ with a largest leaf-set
$S\subset[n]$ such that $\mathcal{T}$ is induced by $S$ both in $T^{\prime}$
and $T^{\prime\prime}$. In a pioneering paper [8], Bryant, McKenzie and Steel
addressed the problem of a likely order of
$\text{MAST}(T^{\prime}_{n},T^{\prime\prime}_{n})$ when $T^{\prime}_{n}$ and
$T^{\prime\prime}_{n}$ are two independent copies of a random binary tree
$T_{n}$. To quote from [8], such a problem is “relevant when comparing
evolutionary trees for the same set of species that have been constructed from
two quite different types of data”.

It was proved in [8] that
$\text{MAST}(T^{\prime}_{n},T^{\prime\prime}_{n})\leq(1+o(1))e2^{-1/2}n^{1/2}$
with probability $1-o(1)$ as $n\to\infty$. The proof was based on a remarkable
property of the uniformly random rooted binary tree, and of few other tree
models, known as “sampling consistency”, see Aldous [1]. As observed by Aldous
[3], [4], sampling consistency makes this model conceptually close to a
uniformly random permutation of $[n]$. Combinatorially, it means that a rooted
binary tree $\mathcal{T}$ with with a leaf-set $S\subset[n]$, $|S|=s$, is
induced by $S$ in exactly $\frac{(2n-3)!!}{(2a-3)!!}$ rooted binary trees with
leaf-set $[n]$, regardless of choice of $\mathcal{T}$. Probabilistically, the
rooted binary tree induced by $S$ in $T_{n}$ is distributed uniformly on the
set of all $(2a-3)!!$ such trees. Mike Steel [25] pointed out that the
sampling consistency of the rooted binary tree follows directly from a
recursive process for generating all the rooted trees in which $S$ induces
$\mathcal{T}$.

Bernstein, Ho, Long, Steel, St. John, and Sullivant [6] established a
qualitatively similar upper bound $O(n^{1/2})$ for the likely size of a common
induced subtree in a harder case of Yule-Harding tree, again relying on
sampling consistency of this tree model. Recently Misra and Sullivant [21]
were able to prove the two-sided estimate $\Theta(n^{1/2})$ for the case when
two independent binary trees with $n$ labelled leaves are obtained by
selecting independently, and uniformly at random, two leaf-labelings of the
same unlabelled tree. Using the classic results on the length of the longest
increasing subsequence in the uniformly random permutation, Bernstein et al.
[6] established a first power-law lower bound $cn^{1/8}$ for the likely size
of the common induced subtree in the case of the uniform rooted binary tree,
and a lower bound $cn^{a-o(1)}$, $a=0.344\dots$, for the Yule-Harding model.
Very recently, Aldous [3] proved that a maximum agreement rooted subtree for
two independent, uniform, unrooted trees is likely to have
$n^{\frac{\sqrt{3}-1}{2}-o(1)}\approx n^{0.366}$ leaves, at least. It was
mentioned in [3] that an upper bound $O(n^{1/2})$ could be obtained by “the
first moment method (calculating the expected number of large common
subtrees)”.

In this paper we show that the total number of unrooted trees with leaf-set
$[n]$, which contains a rooted subtree induced by $S\subset[n]$, $a=|S|<n$, is
$\frac{(2n-5)!!}{(2a-3)!!}$. The proof is based on a two-phase counting
procedure, indirectly inspired by the well-known process of generating a
uniformly random unrooted, leaf-labelled, tree. It follows that a rooted
binary tree induced by $S$ in the uniformly random unrooted tree on $[n]$ is
again distributed uniformly on the set of all $(2a-3)!!$ rooted trees, so that
the expected number of agreement trees with $a$ leaves is
$\binom{n}{a}/(2a-3)!!$. Mike Steel [25] informed us recently that this
$\frac{(2n-5)!!}{(2a-3)!!}$ formula can also be obtained by observing that the
number of unrooted binary trees on $[n]$ in which a leaf-set
$\mathcal{S}\subseteq[n]$ induces a given unrooted tree is
$\frac{(2n-5)!!}{(2|\mathcal{S}|-5)!!}$. Using the asymptotic estimate from
[8], we have: a maximum agreement rooted subtree for two independent copies of
the uniformly random unrooted tree is likely to have at most
$(1+o(1))e2^{-1/2}n^{1/2}$ leaves.

Our proof of this $\frac{(2n-5)!!}{(2a-3)!!}$ result suggested, strongly, that
a bound $O(n^{1/2})$ might, just might, be obtained for a broad class of
random rooted trees by using a probabilistic two-phase counting procedure,
where the random tree grows from the root, rather than from leaves.

Consider a Markov branching process initiated by a single progenitor, with a
given offspring distribution $\mathbb{p}=\\{p_{j}\\}_{j\geq 0}$. If $p_{0}>0$
and $\sum_{j}jp_{j}=1$ (critical case), then the process is almost surely
extinct. This process is visualized as a growing rooted tree such that
children of each father are ordered, by “seniority” say.

Let $T_{t}$ be the random terminal tree, and let $T_{n}$ be $T_{t}$
conditioned on the event “$T_{t}$ has $n$ leaves”, that we label, uniformly at
random, by elements of $[n]$. For $p_{0}=p_{2}=1/2$, $T_{n}$ is doubly-random,
obtained by picking uniformly at random a binary tree with $2n-1$ vertices,
such that two children of each father are ordered, and labeling the tree’s $n$
leaves uniformly at random by elements of $[n]$. This scheme certainly
resembles a process studied by Harding [16] (Section 3.2). A key difference is
that Harding considered the case when the children of a parent are
indistinguishable.

In general, we assume that $p_{1}=0$, $\text{g.c.d.}(j:\,p_{j+1}>0)=1$, and
that $P(s):=\sum_{j}p_{j}s^{j}$ has convergence radius $R>1$. We will show
that $\mathbb{P}_{n}:=\mathbb{P}(T_{t}\text{ has }n\text{ leaves})>0$ for all
$n$, meaning that $T_{n}$ is well-defined for all $n$.

Finally, an out-degree of a vertex in $T_{n}$ may now exceed $2$. So we add to
the definition of a tree $\mathcal{T}$, induced by $S$ in $T_{n}$, the
condition: the out-degree of every vertex from $V(\mathcal{T})$ in $T_{n}$ is
the same as its out-degree in $\mathcal{T}$.

Under the conditions above, we prove that a rooted binary tree $\mathcal{T}$
with leaf-set $S\subset[n]$, the vertex set $V(\mathcal{T})$ and the edge set
$E(\mathcal{T})$, is induced by $S$ in $T_{n}$ with probability

(1.1)
$\displaystyle\,\,\frac{(n-a)!}{n!\,p_{0}\,\mathbb{P}_{n}}\,\mathbb{P}(\mathcal{T})\,[y^{n-a}](1-\Phi_{1}(y))^{-e(\mathcal{T})}\Phi^{\prime}(y),\quad(e(\mathcal{T}):=|E(\mathcal{T})|),$
$\displaystyle\Phi(y)=P(\Phi(y))+p_{0}(y-1),\quad\Phi_{1}(y)=\sum_{j>1}jp_{j}\Phi^{j-1}(y);$
$\displaystyle\quad\quad\mathbb{P}(\mathcal{T})=\prod_{v\in
V(\mathcal{T})}p_{d(v,\mathcal{T})},\quad d(v,\mathcal{T}):=\text{out-degree
of }v\text{ in }\mathcal{T}.$

Here $\Phi(y)$ is the probability generating function of the total number of
leaves in the terminal tree. We will use (1.1) to show that for
$p_{0}=p_{2}=1/2$ the expected number of agreement trees with $a$ leaves is
$\binom{n}{a}/\bigl{[}2^{a-1}(2a-3)!!\bigr{]}$. Consequently a
maximum–agreement rooted subtree for two independent copies of the terminal
Galton-Watson tree with $n$ leaves, labelled uniformly at random, is likely to
have at most $(1+o(1))(e/2)n^{1/2}$ leaves.

Note that in general, because of the factor $\mathbb{P}(\mathcal{T})$, and
$e(\mathcal{T})$, the probability of $\mathcal{T}$ being induced by $S$ in
$T_{n}$ depends not only on $|S|$, but also on the whole out-degree sequence
of $\mathcal{T}$.

We use the above identity to prove the following claim. Let

$\displaystyle\qquad\qquad\qquad\quad\,c(\mathbb{p}):=e\,p_{0}\,\lambda\Bigl{[}\max_{r}\Bigl{(}r-\sum\nolimits_{j=2}^{\infty}p_{j}^{2}r^{j}\Bigr{)}\Bigr{]}^{-1/2},$
$\displaystyle\,\,\lambda:=\max(\chi^{-2},\chi^{-1}),\quad\chi:=(2p_{0}\sigma^{2})^{1/2},\quad\sigma^{2}:=\sum\nolimits_{j=2}^{\infty}j(j-1)p_{j};$

($c(\mathbb{p})=e/2$ for $p_{0}=p_{2}=1/2$). Then, for
$\varepsilon\in(0,1/2]$, with probability $\geq
1-(1-\varepsilon)^{(1+\varepsilon)c(\mathbb{p})n^{1/2}}$, the largest number
of leaves in an induced subtree shared by two independent copies of the
conditioned terminal tree $T_{n}$ is at most
$(1+\varepsilon)c(\mathbb{p})n^{1/2}$.

For a wide ranging exposition of combinatorial/probabilistic problems and
methods in theory of phylogeny, we refer the reader to the books [23] by
Semple and Steel, and [24] by Steel. The reader may wish to consult Bóna and
Flajolet [7] for a thought-provoking study of algebraic-analytic properties of
binary trees from the references above.

##  2\. Uniform binary trees

Consider a rooted binary tree $T$ with leaf-set $[n]$. For a given
$S\subset[n]$, there exists a subtree with leaf-set $S$, which is rooted at
the lowest vertex common to all $|S|$ paths leading away from $S$ toward the
root of $T$. The vertex set of this lowest common ancestor (LCA) tree is the
set of all vertices from the paths in question. Ignoring degree-2 vertices of
this subtree (except the root itself), we obtain a rooted binary tree
$\mathcal{T}$. This LCA subtree has a name “a tree induced by $S$ in $T$”, see
[3].

Let $T^{\prime}_{n},T^{{}^{\prime\prime}}_{n}$ be two independent copies of
the uniformly random rooted binary tree with leaf-set $[n]$. Let $X_{n,a}$
denote the random total number of leaf-sets $S\subset[n]$ of cardinality $a$
that induce the same rooted subtree in $T_{n}^{\prime}$ and
$T^{{}^{\prime\prime}}_{n}$. Bryant et al. [8] proved that

(2.1) $\mathbb{E}[X_{n,a}]=\frac{\binom{n}{a}}{(2a-3)!!}.$

The proof was based on sampling consistency of the random tree $T_{n}$, so
that $N(\mathcal{T})$, the number of rooted trees on $[n]$ in which $S$
induces a given rooted tree $\mathcal{T}$ on $S$, is
$\frac{(2n-3)!!}{(2a-3)!!}$, thus dependent only on the leaf-set size.

Following Aldous [3] (see Introduction), we consider the case when a binary
tree $T$ with leaf-set $[n]$ is unrooted. Here the definition of a rooted
subtree induced by a leaf-set $S$ with $|S|=a>1$ remains the same, except that
it makes sense only for $a<n$. An induced subtree uniquely exists for any such
$S$. Indeed, a vertex $v$ adjacent to any fixed leaf $\ell^{*}\in[n]\setminus
S$ is joined by a unique path to each leaf in $S$. By tracing these $a$ paths
toward $v$, we determine their first common vertex $v^{*}$. The subtree formed
by the paths from $v^{*}$ to $S$ is induced by $S$ in $T$. Since $T$ is a
tree, a subtree induced by $S$ is unique.

Let now $T^{\prime}_{n},T^{{}^{\prime\prime}}_{n}$ be two independent copies
of the uniformly random (unrooted) binary tree with leaf-set $[n]$. Let
$X_{n,a}$ denote the random total number of leaf-sets $S\subset[n]$ of
cardinality $a$ that induce the same rooted subtree in $T_{n}^{\prime}$ and
$T^{{}^{\prime\prime}}_{n}$.

######  Lemma 2.1.

Let $a=|S|<n$. Then

(2.2) $\mathbb{E}[X_{n,a}]=\frac{\binom{n}{a}}{(2a-3)!!}.$

Equivalently $\mathcal{N}(\mathcal{T})$, the number of unrooted trees $T$ on
$[n]$, in which $S$ induces a given rooted tree $\mathcal{T}$ with leaf-set
$S$, is $\frac{(2n-5)!!}{(2a-3)!!}$.

Note. So the expectation is the same as for the rooted trees $T$ on $[n]$.
Compared to a recent combinatorial argument by Steele [24], our longer proof
is based on machinery of generating functions. An advantage of our argument is
its being a precursor of an avoidably more complicated argument in Section 3.
There, a random tree grows from root to leaves, rather than from leaves to
root, as it happens for the classic algorithm, used by Steele: the uniformly
random binary tree is generated by attaching labelled leaves to a current
tree, a leaf at a time.

###### Proof.

Let us evaluate $\mathcal{N}(\mathcal{T})$. Consider a generic rooted tree
with $a$ leaves. For $\mathcal{T}$ to be induced by its leaves in $T$ with $n$
leaves, it has to be obtained by ignoring degree-$2$ (non-root) vertices in
the LCA subtree for leaf-set $S$.

The outside (third) neighbors of the ignored vertices are the roots of
subtrees with some $b$ leaves from the remaining $n-a$ leaves, selected in
$\binom{n-a}{b}$ ways. The roots of possible trees, attached to internal
points chosen from some of $2(a-1)$ edges of $\mathcal{T}$, can be easily
ordered. Introduce $F(b,k)$, the total number of ordered forests of $k$ rooted
trees with $b$ leaves altogether. By Lemma 4 of Carter et al. [10] (for the
count of unordered trees), we have

(2.3) $F(b,k)=\frac{k(2b-k-1)!}{(b-k)!\,2^{b-k}}.$

It was indicated in [6] that (2.3) follows from

(2.4) $F(b,k)=b!\cdot[x^{b}]\,B(x)^{k},\quad B(x):=1-\sqrt{1-2x},$

(Semple and Steel [23]). For the reader’s convenience here is a sketch proof
of (2.4) and (2.3). We have

$\displaystyle F(b,k)$
$\displaystyle=b!\sum_{t_{1}+\cdots+t_{k}=b}\prod_{j\in[k]}\frac{(2t_{j}-3)!!}{t_{j}!}=b!\sum_{t_{1}+\cdots+t_{k}=b}\prod_{j\in[k]}\frac{1}{t_{j}2^{t_{j}-1}}\binom{2(t_{j}-1)}{t_{j}-1}$
$\displaystyle=b![x^{b}]\biggl{[}\sum_{t\geq
1}\frac{x^{t}}{t2^{t-1}}\binom{2(t-1)}{t-1}\biggr{]}^{k}=b![x^{b}]B(x)^{k}=\frac{k(2b-k-1)!}{(b-k)!\,2^{b-k}};$

for the last two steps we used Equations (2.5.10), (2.5.16) in Wilf [26].

Introduce $\mathcal{F}(b,k)$, the total number of the ordered forests of $k$
binary trees with roots attached to internal points of $\mathcal{T}$’s edges,
with $b$ leaves altogether. ($b$ leaves have to be chosen from
$[n]\setminus(S\cup\\{\ell^{*}\\})$, so $b\leq n-a-1$.) Since the total number
of integer compositions (ordered partitions) of $k$ with $j\leq 2(a-1)$
positive parts is

$\binom{k-1}{j-1}\binom{2(a-1)}{j}=\binom{k-1}{j-1}\binom{2(a-1)}{2(a-1)-j},$

(2.3) implies

(2.5) $\mathcal{F}(b,k)=F(b,k)\sum_{j\leq
2(a-1)}\binom{k-1}{j-1}\binom{2(a-1)}{2(a-1)-j}\\\
=F(b,k)\binom{k+2a-3}{2a-3}=b!\binom{k+2a-3}{2a-3}[x^{b}]B(x)^{k}.$

Now, $\sum_{k\leq b}\mathcal{F}(b,k)$ is the total number of ways to expand
the host subtree into a full binary subtree rooted at the lowest common
ancestor of the $a$ leaves. To evaluate this sum, first denote $\alpha=2a-3$,
$\beta=B(x)$ and write

$\displaystyle\sum_{k\geq 0}\binom{k+\alpha}{\alpha}\beta^{k}$
$\displaystyle=\sum_{k\geq
0}(-\beta)^{k}\binom{-\alpha-1}{k}=(1-\beta)^{-\alpha-1}.$

Therefore

$\displaystyle\sum_{k\leq b}\binom{k+\alpha}{\alpha}[x^{b}]B(x)^{k}$
$\displaystyle=[x^{b}]\sum_{k\geq
0}\binom{k+\alpha}{\alpha}B(x)^{k}=[x^{b}]\frac{1}{(1-B(x))^{\alpha+1}}$
$\displaystyle=[x^{b}](1-2x)^{-\frac{\alpha+1}{2}}.$

We conclude that

(2.6) $\sum_{k\leq
b}\mathcal{F}(b,k)=b!\Bigl{.}[x^{b}](1-2x)^{-\frac{\alpha+1}{2}}\Bigr{|}_{\alpha=2a-3}=b![x^{b}](1-2x)^{-(a-1)}.$

Recall that $b$ leaves were chosen from $[n]\setminus(S\cup\\{\ell^{*}\\})$.
If $b=n-a-1$, then attaching the single remaining leaf to the root $v^{*}$ we
get a binary tree $T$ with leaf-set $[n]$. If $b\leq n-a-2$, we view the
expanded subtree as a single leaf, and form an unrooted binary tree with
$1+(n-a-b)\geq 3$ leaves, in $[2(n-a-b)-3]!!$ ways. Therefore
$\mathcal{N}(\mathcal{T})$ depends on $a$ only, and with $\nu:=n-a-1$, it is
given by

$\mathcal{N}(\mathcal{T})=\sum_{b\leq\nu}\binom{\nu}{b}b!\,[x^{b}](1-2x)^{-(a-1)}\bigl{(}2(\nu-b)-1\bigr{)}!!\\\
=\nu!\sum_{b\leq\nu}[x^{b}](1-2x)^{-(a-1)}\cdot[x^{\nu-b}](1-2x)^{-1/2}\\\
=\nu![x^{\nu}](1-2x)^{-a+1/2}=\prod_{j=0}^{n-a-2}(2a-1+2j)=\frac{(2n-5)!!}{(2a-3)!!};$

in the first line $(-1)!!:=1$, and for the second line we used

$\frac{(2k-1)!!}{k!}=\frac{(2k)!}{2^{k}(k!)^{2}}=2^{-k}\binom{2k}{k}=[x^{k}](1-2x)^{-1/2}.$

Consequently

(2.7)
$\mathbb{E}[X_{n,a}]=\binom{n}{a}(2a-3)!!\biggl{[}\frac{\mathcal{N}(\mathcal{T})}{(2n-5)!!}\biggr{]}^{2}=\frac{\binom{n}{a}}{(2a-3)!!}.$

∎

##  3\. Branching Process Framework

Consider a branching process initiated by a single progenitor. This process is
visualized as a growing rooted tree. The root is the progenitor, connected by
edges to each of its immediate descendants (children), that are ordered, say
by seniority. Each of the children becomes the root of the corresponding
subtree, so that the children of all these roots are the grandchildren of the
progenitor. We obviously get a recursively defined process. It delivers a
nested sequence of trees, which is either infinite, or terminates at a moment
when none of the current leaves have children.

The classic Galton-Watson branching process is the case when the number of
each member’s children (a) is independent of those numbers for all members
from the preceding and current generations and (b) has the same distribution
$\\{p_{j}\\}_{j\geq 0}$, $(\sum_{j}p_{j}=1)$. It is well-known that if
$p_{0}>0$ and $\sum_{j\geq 0}jp_{j}=1$, then the process terminates with
probability $1$, Harris [17]. Let $T_{t}$ denote the terminal tree. Given a
finite rooted tree $T$, we have

$\mathbb{P}(T_{t}=T)=\prod_{v\in V(T)}p_{d(v,T)},$

where $d(v,T)$ is the out-degree of vertex $v\in V(T)$. $X_{t}:=|V(T_{t})|$,
the total population size by the extinction time, has the probability
generating function (p.g.f) $F(x):=\mathbb{E}[x^{X_{t}}]$, $|x|\leq 1$, that
satisfies

(3.1) $F(x)=xP(F(x)),\quad P(\xi):=\sum_{j\geq 0}p_{j}\xi^{j},\,\,(|\xi|\leq
1).$

Indeed, introducing $F_{\tau}(x)$ the p.g.f. of the total cardinality of the
first $\tau$ generations, we have

$F_{\tau+1}(x)=x\sum_{j\geq
0}p_{j}\bigl{[}F_{\tau}(x)\bigr{]}^{j}=xP(F_{\tau}(x)).$

So letting $\tau\to\infty$, we obtain (3.1). In the same vein, consider the
pair $(X_{t},Y_{t})$, where $Y_{t}:\bigl{|}\\{v\in
V(T_{t}):\,d(v,T_{t})=0\\}\bigr{|}$ is the total number of leaves (zero out-
degree vertices) of the terminal tree. Then denoting
$G(x,y)=\mathbb{E}\bigl{[}x^{X_{t}}y^{Y_{t}}\bigr{]}$, $(|x|,\,|y|\leq 1)$, we
have

(3.2) $G(x,y)=p_{0}xy+x\sum_{j\geq
1}p_{j}\bigl{[}G(x,y)\bigr{]}^{j}=xP(G(x,y))+p_{0}x(y-1).$

So, with $\Phi(y):=\mathbb{E}\bigl{[}y^{Y}\bigr{]}=G(1,y)$, we get

(3.3) $\Phi(y)=\sum_{j\geq 1}p_{j}\Phi^{j}(y)+p_{0}y=P(\Phi(y))+p_{0}(y-1).$

Importantly, this identity allows us to deal directly with the leaf set at the
extinction moment: $\mathbb{P}_{k}:=[y^{k}]\,\Phi(y)$ is the probability that
$T_{t}$ has $k$ leaves. In particular,
$\mathbb{P}_{1}=[y^{1}]\Phi(y)=p_{0}>0$. More generally, $\mathbb{P}_{k}>0$
for all $k\geq 1$. meaning that $\mathbb{P}(T_{t}\text{ has }k\text{
leaves})>0$ for all $k\geq 1$. Indeed, for $k\geq 2$, we have

$\mathbb{P}_{k}=\sum_{j\geq 1}p_{j}\sum_{k_{1}+\cdots+k_{j}=k\atop
k_{1},\dots,k_{j}\geq 1}\mathbb{P}_{k_{1}}\cdots\mathbb{P}_{k_{j}};$

so the claim follows by easy induction on $k$. Introducing the event
$A_{k}:=\\{T_{t}\text{ has }k\text{ leaves}\\}$, we have
$\mathbb{P}(A_{k})=[y^{k}]\Phi(y)$.

If $p_{0}=p_{2}=1/2$, then the branching process is a nested sequence of
binary trees. The equation (3.3) yields

$\Phi(y)=1-(1-y)^{1/2}=\sum_{n\geq
1}\left(\frac{y}{2}\right)^{n}\frac{(2n-3)!!}{n!},\quad|y|\leq 1;$

so $\mathbb{P}(A_{n})=\frac{(2n-3)!!}{2^{n}n!}>0$. On the event $A_{n}$, the
total number of vertices is $2n-1$, and each of rooted binary trees with
ordered pairs of children is a value of the terminal tree with the same
probability $(1/2)^{2n-1}$. Now,

$\frac{\frac{(2n-3)!!}{2^{n}n!}}{(1/2)^{2n-1}}=\frac{1}{n}\binom{2(n-1)}{n-1}$

is the Catalan number $C(n-1)$, which is the total number of rooted binary
trees with $n$ leaves, and $n-1$ non-leaves, each having $2$ ordered children.
Thus, conditionally on $A_{n}$, the terminal tree is distributed uniformly on
the set of these $C(n-1)$ trees. We do not have such uniformity for a general
$\\{p_{j}\\}$, of course.

For a general $\\{p_{j}\\}$, on the event $A_{n}$ we label, uniformly at
random, the leaves of $T_{t}$ by elements of $[n]$. We take liberty to use the
same notation $T_{n}$, as in Section 2, for the resulting doubly random, leaf-
labelled tree.

That $T_{n}$ is again associated with a recursive process is a hopeful sign
that we can get a counterpart of what we proved for the uniformly random,
leaf-labelled binary tree, and also extend an analysis to a more general
distribution $\\{p_{j}\\}$.

We continue to assume that $p_{1}=0$. The notion of an induced subtree needs
to be expanded, since an out-degree of a vertex now may exceed $2$. Let
$\mathcal{T}$ be a tree with a leaf-set $S\subset[n]$, such that every non-
leaf vertex of $\mathcal{T}$ has at least two (ordered) children. We say that
$S$ induces $\mathcal{T}$ in a tree $T_{n}$ provided that: (a) the LCA subtree
for $S$ in $T_{n}$ is $\mathcal{T}$ if we ignore vertices of total degree $2$
in this LCA subtree; (b) the out-degree of every other vertex in the LCA of
$S$ in $T_{n}$ is the same as its out-degree in $\mathcal{T}$. We call this
event $A_{n}(\mathcal{T})$. We evaluate $\mathbb{P}(A_{n}(\mathcal{T}))$ in
steps. Let $|S|=a<n$. Given $b\leq n-a$, let $A_{n}(\mathcal{T},b)$ be the
event:

(i) $A_{n}$ holds, i.e. the terminal tree $T_{t}$ has $n$ leaves; the
uniformly random labelling of the leaves of $T_{t}$, that results in the
random tree $T_{n}$ is such that:

(ii) some $b$ elements from $[n]\setminus S$ are chosen as leaf labels for all
the complementary extinction subtrees rooted at degree-2 vertices sprinkled on
the edges of $\mathcal{T}$, forming–together with $\mathcal{T}$ on leaf-set
$S$–an expanded terminal tree on leaf-set $S\cup\\{b\text{ leaves}\\}$, of
cardinality $a+b$;

(iii) the terminal tree with $n$ labelled leaves is obtained as follows: we
build up a terminal tree with leaf-set $[n]\setminus\bigl{(}S\cup\\{b\text{
leaves}\\}\bigr{)}$ plus an extra super-leaf, which is the root of the tree
built up in (ii), and replace the super-leaf with this tree.

In summary, a terminal tree $T_{n}$, compatible with the event
$A_{n}(\mathcal{T},b)$, is built up of terminal subtrees with a certain number
of leaves, each subtree being delivered by a branching process that starts at
the subtree’s root.

Clearly $A_{n}(\mathcal{T})$ is the disjoint union of the events
$A_{n}(\mathcal{T},b)$. By the very definition, on the event
$A_{n}(\mathcal{T},b)$ the leaf-set $S$ certainly induces $\mathcal{T}$ in
$T_{n}$.

To evaluate $\mathbb{P}(A_{n}(\mathcal{T},b))$ we partition
$A_{n}(\mathcal{T},b)$ into disjoint $\binom{n-a}{b}$ events corresponding to
all choices to select $b$ elements of $[n]\setminus S$. Let $e(\mathcal{T})$
be the total number of edges in $\mathcal{T}$. For each of these choices, on
the event $A_{n}(\mathcal{T},b)$ we must have some $k\leq b$ terminal subtrees
whose roots are some degree-2 vertices, selected from some of $e(\mathcal{T})$
edges, with their respective, nonempty, leaf-sets forming an ordered set
partition of the set of $b$ leaves. The root of each of these trees has one
child down the host edge of $\mathcal{T}$, and all the remaining children are
outside of edges of $\mathcal{T}$. The number of those children is $j$ with
probability $(j+1)p_{j+1}$, and $\\{(j+1)p_{j+1}\\}_{j\geq 1}$ is a
probability distribution, as

$\sum_{j\geq 1}(j+1)p_{j+1}=\sum_{j\geq 0}jp_{j}=1.$

So the total number of leaves of terminal subtrees rooted at those outside
children is $i$ with probability $[y^{i}]\Phi_{1}(y)$, where

(3.4) $\Phi_{1}(y)=\sum_{j\geq 1}(j+1)p_{j+1}\Phi^{j}(y).$

The probability $[y^{i}]\Phi_{1}(y)$ is positive for each $i\geq 1$, since
$[y^{i}]\Phi^{j}(y)>0$ for each $j\geq 1$. Therefore a given set of $b$
elements of $[n]$ is the leaf-set of these terminal subtrees with probability

$b!\sum_{j\leq k\leq
b}\binom{k-1}{j-1}\binom{e(\mathcal{T})}{j}\sum_{b_{1}+\cdots+b_{k}=b}\prod_{t=1}^{k}\,[y^{b_{t}}]\Phi_{1}(y)\\\
=b!\\!\\!\sum_{j\leq k\leq
b}\binom{k-1}{j-1}\binom{e(\mathcal{T})}{e(\mathcal{T})-j}[y^{b}]\Phi_{1}^{k}(y)=b![y^{b}]\sum_{k}\binom{k+e(\mathcal{T})-1}{k}\Phi_{1}^{k}(y)\\\
=b![y^{b}](1-\Phi_{1}(y))^{-e(\mathcal{T})}.$

Explanation: $k$ is a generic total number of trees rooted at ordered internal
points of some $j$ edges of $\mathcal{T}$; $b_{t}$ is a generic number of
leaves of a $t$-th tree; the product of two binomial coefficients in the top
line is the number of ways to pick $j$ edges of $\mathcal{T}$ and to select an
ordered, $j$-long, composition of $k$; the sum is the probability that the $k$
trees have $b$ leaves in total. $b!$ accounts for the number of ways to assign
the chosen $b$ elements as labels of $b$ leaves.

With these complementary trees attached, we obtain a terminal tree with $a+b$
leaves, rooted at the root of $\mathcal{T}$. We denote this expanded tree
$\mathcal{E}(\mathcal{T})$. For $b=n-a$, this is our terminal tree $T$ with
$n$ labelled leaves. If $b<n-a$, then $\mathcal{E}(\mathcal{T})$ is a subtree
of $T$. Specifically, a branching process tree, grown from a progenitor root,
terminates when there is a single active leave, meaning that this leaf is
about to produce children in accordance with offspring distribution
$\mathbb{p}$, and that all other leaves are childless. This single leaf
becomes the root of $\mathcal{E}(\mathcal{T})$, which completes construction
of $T$. Now, $p_{0}$ times the probability that at this moment the number of
childless leaves is $n-a-b$ equals $(n-a-b+1)![y^{n-a-b+1}]\Phi(y)$, which is
the probability of a terminal tree with $n-a-b+1$ leaves labelled by remaining
$n-a-b$ elements of $[n]$ plus $1$, accounting for the root of
$\mathcal{E}(\mathcal{T})$.

Therefore

(3.5) $\displaystyle\mathbb{P}\bigl{(}A_{n}(\mathcal{T},b)\bigr{)}$
$\displaystyle=\frac{\mathbb{P}(\mathcal{T})}{p_{0}\,n!}\binom{n-a}{b}\,\times
b!\,[y^{b}](1-\Phi_{1}(y))^{-e(\mathcal{T})}$
$\displaystyle\quad\times(n-a-b+1)!\,[y^{n-a-b+1}]\Phi(y).$

Here $\mathbb{P}(\mathcal{T}):=\prod_{v\in
V(\mathcal{T})}p_{d(v,\mathcal{T})}$, where $\\{d(v,\mathcal{T})\\}$ is the
out-degree sequence of vertices in $\mathcal{T}$, that includes the actual
out-degree of $\mathcal{T}$’s root. Using
$(j+1)[y^{j+1}]\Phi(y)=[y^{j}]\Phi^{\prime}(y)$, we simplify (3.5):

$\mathbb{P}\bigl{(}A_{n}(\mathcal{T},b)\bigr{)}=\frac{(n-a)!\,\mathbb{P}(\mathcal{T})}{p_{0}n!}\,[y^{b}](1-\Phi_{1}(y))^{-e(\mathcal{T})}\,[y^{n-a-b}]\Phi^{\prime}(y).$

Summing the last equation for $0\leq b\leq n-a$, we obtain

(3.6)
$\mathbb{P}\bigl{(}A_{n}(\mathcal{T})\bigr{)}=\frac{\mathbb{P}(\mathcal{T})(n-a)!}{p_{0}\,n!}\,[y^{n-a}](1-\Phi_{1}(y))^{-e(\mathcal{T})}\Phi^{\prime}(y).$

For $p_{0},\,p_{2}=1/2$, we have
$\mathbb{P}(\mathcal{T})=(1/2)^{2a-1},\Phi_{1}(y)=\Phi(y),$ see (3.4). So

$[y^{n-a}](1-\Phi(y))^{-e(\mathcal{T})}\Phi(y)=[y^{n-a}](1-\Phi(y))^{-2a+2}\Phi^{\prime}(y)\\\
=[y^{n-a}](1-y)^{-a+1}\cdot\frac{1}{2}(1-y)^{-1/2}=\frac{1}{2}[y^{n-a}](1-y)^{-a+1/2}\\\
=2^{-n+a-1}\frac{(2n-3)!!}{(n-a)!\,(2a-3)!!},$

and, by (3.6), we have

(3.7)
$\mathbb{P}\bigl{(}A_{n}(\mathcal{T})\bigr{)}=\frac{(2n-3)!!}{2^{n+a-1}\,n!\,(2a-3)!!}.$

Since $\mathbb{P}(A_{n})=\frac{(2n-3)!!}{2^{n}n!}$, we conclude that

(3.8)
$\mathbb{P}(A_{n}(\mathcal{T})|\,A_{n})=\frac{\mathbb{P}\bigl{(}A_{n}(\mathcal{T})\bigr{)}}{\mathbb{P}(A_{n})}=\frac{1}{2^{a-1}(2a-3)!!},$

for every binary tree $\mathcal{T}$ with leaf-set $S\subset[n]$, $|S|=a$. The
LHS is the probability that $S$ induces $\mathcal{T}$ in the uniformly random
binary tree $T_{n}$.

######  Theorem 3.1.

Let $X_{n,a}$ denote the total number of leaf-sets $S\subset[n]$ that induce
the same binary tree in two independent copies of the random binary tree
$T_{n}$. We have

$\mathbb{E}[X_{n,a}]=\binom{n}{a}[2^{a-1}(2a-3)!!]^{-1};$

in particular,

$\mathbb{E}[X_{n,1}]=n,\quad\mathbb{E}[X_{n,2}]=n(n-1)/4,\quad\mathbb{E}[X_{n,3}]=n(n-1)(n-2)/72.$

Consequently a maximum–agreement rooted subtree for two independent copies of
the terminal Galton-Watson tree with $n$ leaves, labelled uniformly at random,
is likely to have at most $(1+o(1))(e/2)n^{1/2}$ leaves.

###### Proof.

The total number of the binary trees with $a$ leaves in question is
$a!\,C(a-1)=2^{a-1}(2a-3)!!$. Therefore, by (3.8),

$\mathbb{E}[X_{n,a}]=\binom{n}{a}\bigl{[}2^{a-1}(2a-3)!!\bigr{]}^{-2}\cdot
a!\,C(a-1)=\binom{n}{a}\,[2^{a-1}(2a-3)!!]^{-1}.$

∎

For a general distribution $\\{p_{j}\\}$, we have proved

######  Lemma 3.2.

Consider the branching process with the immediate offspring distribution
$\\{p_{j}\\}$, such that $p_{0}>0$, $p_{1}=0$, and $\sum_{j\geq 0}jp_{j}=1$.
With probability $1$, the process eventually stops, so that a finite terminal
tree $T_{t}$ is a.s. well-defined. (1) Setting $A_{n}=\\{T_{t}\text{ has
}n\text{ leaves}\\}$, we have

$\mathbb{P}(A_{n})=[y^{n}]\Phi(y),\quad\Phi(y)=P(\Phi(y))+p_{0}(y-1),$

where $P(\eta):=\sum_{j\geq 0}\eta^{j}p_{j}$. (2) On the event $A_{n}$, we
define $T_{n}$ as the tree $T_{t}$ with leaves labelled uniformly at random by
elements from $[n]$. Given a rooted tree $\mathcal{T}$ with leaf-set
$S\subset[n]$, set $A_{n}(\mathcal{T})$:= “$A_{n}$ holds; $S$ is a subset of
$T_{t}^{\prime}s$ leaf-set ; $S$ induces $\mathcal{T}$ in $T_{n}$”. Then
$\mathbb{P}(A_{n}(\mathcal{T})|\,A_{n})=\frac{\mathbb{P}(A_{n}(\mathcal{T}))}{\mathbb{P}(A_{n})}$,
where

(3.9)
$\displaystyle\,\mathbb{P}\bigl{(}A_{n}(\mathcal{T})\bigr{)}=\frac{\mathbb{P}(\mathcal{T})(n-a)!}{p_{0}\,n!}\,[y^{n-a}](1-\Phi_{1}(y))^{-e(\mathcal{T})}\Phi^{\prime}(y),$
$\displaystyle\,\,\Phi(y)=P(\Phi(y))+p_{0}(y-1),\quad\Phi_{1}(y)=\sum_{j>1}jp_{j}\Phi^{j-1}(y),$
$\displaystyle\qquad\qquad\qquad\mathbb{P}(\mathcal{T})=\\!\\!\\!\prod_{v\in
V(\mathcal{T})}\\!\\!p_{d(v,\mathcal{T})};$

$V(\mathcal{T})$ and $e(\mathcal{T})$ are the set of vertices and the number
of edges of $\mathcal{T}$.

Note. For $p_{0}=p_{2}=1/2$, $\mathbb{P}\bigl{(}A_{n}(\mathcal{T})\bigr{)}$
turned out to be dependent only on the number of leaves of $\mathcal{T}$. The
formula (3.9) clearly shows that, in general, this probability depends on
shape of $\mathcal{T}$. Fortunately, this dependence is confined to a single
factor $\mathbb{P}(\mathcal{T})$, since the rest depends on two scalars, $a$
and $e(\mathcal{T})$. Importantly, these parameters are of the same order of
magnitude. Indeed, if if $a>1$ and $\mathbb{P}(\mathcal{T})>0$ then
$e(\mathcal{T})\geq\max\bigl{(}a,2|V_{\text{int}}(\mathcal{T})|\bigr{)}$,
where $V_{\text{int}}(\mathcal{T})$ is the set of non-leaf vertices of
$\mathcal{T}$. Hence

$a\leq
e(\mathcal{T})=|V(\mathcal{T})|-1=|V_{\text{int}}(\mathcal{T})|+a-1\leq\frac{e(\mathcal{T})}{2}+a-1,$

so that

(3.10) $a\leq e(\mathcal{T})\leq 2(a-1).$

###  3.1. Asymptotics

From now on we assume that the series $\sum_{j}p_{j}s^{j}$ has convergence
radius $R>1$.

######  Lemma 3.3.

Suppose that $d:=\text{g.c.d.}\\{j\geq 1:\,p_{j+1}>0\\}=1$. Let
$\sigma^{2}:=\sum_{j\geq 0}j(j-1)p_{j}$, i.e. $\sigma^{2}$ is the variance of
the immediate offspring, since $\sum_{j\geq 0}jp_{j}=1$. Then

$\mathbb{P}(A_{n})=\frac{(2p_{0})^{1/2}}{\sigma}\frac{(2n-3)!!}{2^{n}\,n!}+O(n^{-2})=\biggl{(}\frac{p_{0}}{2\pi\sigma^{2}}\biggr{)}^{1/2}\\!\\!\\!n^{-3/2}+O(n^{-2}).$

###### Proof.

According to Lemma 3.2, we need to determine an asymptotic behavior of the
coefficient in the power series $\Phi(z)=\sum_{n\geq
1}z^{n}\mathbb{P}(A_{n})$, where $\Phi(z)$ is given implicitly by the
functional equation $\Phi(z)=\sum_{j\geq
0}p_{j}\Phi^{j}(z)+p_{0}(z-1),\,(|z|\leq 1)$.

In 1974 Bender [5] sketched a proof of the following general claim.

######  Theorem 3.4.

Assume that the power series $w(z)=\sum_{n}a_{n}z^{n}$ with nonnegative
coefficients satisfies $F(z,w)\equiv 0$. Suppose that there exist $r>0$ and
$s>0$ such that: (i) for some $R>r$ and $S>s$, $F(z,w)$ is analytic for
$|z|<R$ and $w<S$; (ii) $F(r,s)=F_{w}(r,s)=0$; (iii) $F_{z}(r,s)\neq 0$ and
$F_{ww}(r,s)\neq 0$; (iv) if $|z|\leq r$, $|w|\leq s$, and
$F(z,w)=F_{w}(z,w)=0$, then $z=r$ and $w=s$. Then
$a_{n}\sim\bigl{(}(rF_{z}(r,s))/(2\pi
F_{ww}(r,s))\bigr{)}^{1/2}n^{-3/2}r^{-n}$.

The remainder term aside, that’s exactly what we claim in Lemma 3.3 for our
$\Phi(z)$. The proof in [5] relied on an appealing conjecture that, under the
conditions (i)-(iv), $r$ is the radius of convergence for the power series for
$w(z)$, and $z=r$ is the only singularity for $w(z)$ on the circle $|z|=r$.
However, ten years later Canfield [9] found an example of $F(z,w)$ meeting the
four conditions in which $r$ and the radius of convergence for $w(z)$ are not
the same. Later Meir and Moon found some conditions sufficient for validity of
the conjecture. Our equation $\Phi(z)=P(\Phi(z))+p_{0}(z-1)$ is a special case
of $w=\phi(w)+h(z)$ considered in [19]. For the conditions from [19] to work
in our case, it would have been necessary to have
$\big{|}P^{\prime}(w)/P(w)\big{|}\leq 1$ for complex $w$ with $|w|\leq 1$, a
strong condition difficult to check. (An interesting discussion of these
issues can be found in an encyclopedic book by Flajolet and Sedgewick [13] and
an authoritative survey by Odlyzko [22].)

Let $r$ be the convergence radius for the powers series representing
$\Phi(z)$; so that $r\geq 1$, since $\mathbb{P}(A_{n})\leq 1$. By implicit
differentiation, we have

$\lim_{x\uparrow 1}\Phi^{\prime}(x)=\lim_{x\uparrow
1}\frac{p_{0}}{1-\mathbb{P}_{w}(\Phi(x))}=\infty,$

since $\lim_{x\uparrow 1}P_{w}(\Phi(x))=\sum_{j}jp_{j}=1$. Therefore $r=1$.
Turn to complex $z$. For $|z|<1$, we have $F(z,\Phi(z))=0$, where
$F(z,w):=p_{0}(z-1)+P(w)-w$ is analytic as a function of $z$ and $w$ subject
to $|w|<1$. Observe that $F_{w}(z,w)=P^{\prime}(w)-1=0$ is possible only if
$|w|\geq 1$, since for $|w|<1$ we have $|P^{\prime}(w)|\leq
P^{\prime}(|w|)<P^{\prime}(1)=1$. If $|w|=1$ then $P^{\prime}(w)=\sum_{j\geq
2}jp_{j}w^{j-1}=1$ if and only if $w=w_{k}:=\exp\Bigl{(}i\frac{2\pi
k}{d}\Bigr{)}$, and $k=1,\dots,d$. Notice also that

(3.11) $P(w_{k})=\sum_{j\geq 0}p_{j}w_{k}^{j}=p_{0}+w_{k}\sum_{j\geq
2}p_{j}w_{k}^{j-1}=p_{0}+w_{k}(1-p_{0}).$

Now, $z$ is a singular point of $\Phi(z)$ if and only if $|z|=1$ and
$(P^{\prime}(w)\\!-1\\!)\big{|}_{w=\Phi(z)}\\!=\\!0$, i.e. if and only if
$\Phi(z)=w_{k}$ for some $k\in[d]$, which is equivalent to

$p_{0}(z-1)+P(w_{k})-w_{k}=0.$

Combination of this condition with (3.11) yields $z=w_{k}$. Therefore the set
of all singular points of $\Phi(z)$ on the circle $|z|=1$ is the set of all
$w_{k}$ such that $\Phi(w_{k})=w_{k}$. Notice that

$P^{\prime\prime}(w_{k})=w_{k}^{-1}\sum_{j\geq
2}j(j-1)p_{j}w_{k}^{j-1}=w_{k}^{-1}\sum_{j\geq
2}j(j-1)p_{j}=w_{k}^{-1}\sigma^{2}\neq 0.$

So none of $w_{k}$ is an accumulation point of roots of $P^{\prime}(w)-1$
outside the circle $|w|=1$, i.e. $\\{w_{k}\\}_{k\in[d]}$ is the full root set
of $P^{\prime}(w)-1$ inside the circle $|w|=1+\rho_{0}$, for some small
$\rho_{0}>0$.

Consequently, if $d=1$, then $z=1$ is the only singular point of $\Phi(z)$ on
the circle $|z|=1$. Define the argument $\text{arg}(z)$ by the condition
$\text{arg}(z)\in[0,2\pi)$. By the analytic implicit function theorem applied
to $F(z,w)$, for every $z_{\alpha}=e^{i\alpha}$, $\varepsilon\leq\alpha\leq
2\pi-\varepsilon$, a small $\varepsilon>0$ being fixed, there exists an
analytic function $\Psi_{\alpha}(z)$ defined on $D_{z_{\alpha}}(\rho)$–an open
disc centered at $z_{\alpha}$, of a radius $\rho=\rho(\varepsilon)<\rho_{0}$
small enough to make $\varepsilon/2\leq\text{arg}(z)\leq 2\pi-\varepsilon/2$
for all $z\in D_{z_{\alpha}}$– such that $F(z,\Psi_{\alpha}(z))=0$ for $z\in
D_{z_{\alpha}}$ and $\Psi_{\alpha}(z)=\Phi(z)$ for $z\in D_{z_{\alpha}}$ with
$|z|\leq 1$. Together, these local analytic continuations determine an
analytic continuation of $\Phi(z)$ to a function $\hat{\Psi}(z)$ determined,
and bounded, for $z$ with $|z|<1+\rho$,
$\text{arg}(z)\in[\varepsilon,2\pi-\varepsilon]$.

Since $z_{0}=1$ is the singular point of $\Phi(z)$, there is no analytic
continuation of $\Phi(z)$ for $|z|>1$ and $|z-1|$ small. So instead we delete
an interval $[1,1+\rho)$ and continue $\Phi(z)$ analytically into the
remaining part of a disc centered at $1$. Here is how. We have
$F_{ww}(1,\Phi(1))=P^{\prime\prime}(1)=\sum_{j}j(j-1)p_{j}=\sigma^{2}>0$. By a
“preparation” theorem due to Weierstrass, (Ebeling [11], Krantz [18]), already
used by Bender [5] for the same purpose in the general setting, there exist
two open discs $D_{1}$ and $\mathcal{D}_{1}$ such that for $z\in D_{1}$ and
$w\in\mathcal{D}_{1}$ we have

$F(z,w)=\bigl{[}(w-1)^{2}+c_{1}(z)(w-1)+c_{2}(z)\bigr{]}g(z,w),$

where $c_{j}(z)$ are analytic on $D_{1}$, $c_{j}(1)=0$, and $g(z,w)$ is
analytic, non-vanishing, on $D_{1}\times\mathcal{D}_{1}$. (The degree $2$ of
the polynomial is exactly the order of the first non-vanishing derivative of
$F(z,w)$ with respect to $w$ at $(1,1)$.) So for $z\in D_{1}$ and
$w\in\mathcal{D}_{1}$, $F(z,w)=0$ is equivalent to

$(w-1)^{2}+c_{1}(z)(w-1)+c_{2}(z)=0\Longrightarrow w=1+(z-1)^{1/2}h(z),$

where $h(z)$ is analytic at $z=1$. Plugging the power series
$w=1+(z-1)^{1/2}h(z)=1+(z-1)^{1/2}\sum_{j\geq 0}h_{j}(z-1)^{j}$ into equation
$F(z,w)=0$, and expanding $P(w)$ in powers of $w-1$, we can compute the
coefficients $h_{j}$. In particular,

$w(z)=1-\gamma(1-z)^{1/2}+O(|z-1|),\quad\gamma:=(2p_{0})^{1/2}\sigma^{-1}.$

For $z$ real and $z\in(0,1)$, we have $\Phi(z)=1-\gamma(1-z)^{1/2}+O(1-z)$. So
to use $w(z)$ as an extension $\tilde{\Psi}(z)$ we need to choose
$\sqrt{\xi}=|\xi|^{1/2}\exp\bigl{(}i\text{Arg}(\xi)/2\bigr{)}$, where
$\text{Arg}(\xi)\in(-\pi,\pi)$.

The continuations $\hat{\Psi}(z)$ and $\tilde{\Psi}(z)$ together determine an
analytic continuation of $\Phi(z)$ into a function $\Psi(z)$ which is analytic
and bounded on a disc $D^{*}=D_{0}(1+\rho^{*})$ minus a cut $[1,1+\rho^{*})$,
$\rho^{*}>0$ being chosen sufficiently small, such that

$\Psi(z)\underset{z\in D^{*}\setminus[1,1+\rho^{*})\atop z\to
1}{=}1-\gamma(1-z)^{1/2}+O(|z-1|).$

It follows that

$\mathbb{P}(A_{n})=\frac{1}{2\pi i}\oint_{|z|=1}\frac{\Phi(z)}{z^{n+1}}\,dz\\\
=\frac{1}{2\pi}\oint_{|z|=1+\rho*}\frac{\Psi(z)}{z^{n+1}}+\frac{1}{2\pi
i}\int_{1}^{1+\rho*}\frac{2i\gamma(x-1)^{1/2}+O(x-1)}{x^{n+1}}\,dx\\\
=O\bigl{(}(1+\rho^{*})^{-n}+n^{-2}\bigr{)}+\frac{\gamma}{\pi}\int_{1}^{\infty}\frac{(x-1)^{1/2}}{x^{n+1}}\,dx.$

For the second line we integrated $\Psi(z)/z^{n+1}$ along the limit contour :
it consists of the directed circular arc $z=(1+\rho^{*})e^{i\alpha}$,
$0<\alpha<2\pi$ and a detour part formed by two opposite-directed line
segments, one from $z=(1+\rho^{*})e^{i(2\pi-0)}$ to $z=e^{i(2\pi-0)}$ and
another from $z=e^{i(+0)}$ to $z=(1+\rho^{*})e^{i(+0)}$. By the formula
3.191(2) from Gradshteyn and Ryzik [15], we have

$\displaystyle\int_{1}^{\infty}\frac{(x-1)^{1/2}}{x^{n+1}}\,dx=B(n-1/2,3/2)=\frac{\Gamma(n-1/2)\,\Gamma(3/2)}{\Gamma(n+1)}$
$\displaystyle=\frac{\prod_{m=2}^{n}\Bigl{(}n-\frac{2m-1}{2}\Bigr{)}}{n!}\cdot\frac{1}{2}\Gamma^{2}(1/2)=\pi\frac{(2n-3)!!}{2^{n}\,n!}.$

Therefore

$\frac{\gamma}{\pi}\int_{1}^{\infty}\frac{(x-1)^{1/2}}{x^{n+1}}\,dx=\gamma\frac{(2n-3)!!}{2^{n}\,n!}=\frac{\gamma}{2\pi^{1/2}n^{3/2}}+O(n^{-2}).$

Recalling that $\gamma=(2p_{0})^{1/2}\sigma^{-1}$, we complete the proof of
the Lemma. ∎

Using Lemma 3.2 and Lemma 3.3 we prove

######  Theorem 3.5.

Suppose that $\mathbb{p}=\\{p_{j}\\}$ is such that $p_{0}>0$, $p_{1}=0$ and
$\text{g.c.d.}(j\geq 1:p_{j+1}>0)=1$. (i) Then $T_{n}$, the random finite
terminal tree of of Galton-Watson process with offspring distribution
$\mathbb{p}=\\{p_{j}\\}$, and $n$ leaves, labelled uniformly at random by
elements of $[n]$, is well defined for every $n$. (ii) Let $X_{n,a}$ be the
total number of subsets $S\subset[n]$, $|S|=a$, such that $S$ induces the same
subtree in two independent copies of $T_{n}$. Then there is an explicit
constant $c(\mathbb{p})$, such that: for $\varepsilon\in(0,1/2]$ and
$a\geq(1+\varepsilon)c(\mathbb{p})n^{1/2}$, we have
$\mathbb{E}[X_{n,a}]\leq(1-\varepsilon)^{a}$. So, with probability $\geq
1-(1-\varepsilon)^{(1+\varepsilon)c(\mathbb{p})n^{1/2}}$, the largest number
of leaves in a common induced subtree is
$(1+\varepsilon)c(\mathbb{p})n^{1/2}$, at most. ($c(\mathbb{p})\\!=\\!e/2$ if
$p_{0}=p_{2}=1/2$.)

###### Proof.

By Lemma 3.2,

(3.12) $\displaystyle\qquad\qquad\qquad\qquad\mathbb{P}(S\text{ induces
}\mathcal{T}\text{ in }T_{n})$
$\displaystyle=\frac{(n-a)!}{\mathbb{P}(A_{n})p_{0}\,n!}\,\left(\prod_{v\in
V(\mathcal{T})}p_{d(v,\mathcal{T})}\right)[y^{n-a}](1-\Phi_{1}(y))^{-e(\mathcal{T})}\Phi^{\prime}(y),$
$\displaystyle\qquad\Phi(y)=\sum_{j>1}p_{j}\Phi^{j}(y)+p_{0}y,\quad\Phi_{1}(y)=\sum_{j>1}jp_{j}\Phi^{j-1}(y).$

$\Phi(y)$ and $(1-\Phi_{1}(y))^{-e(\mathcal{T})}$ are generating functions
with positive coefficients; then so is their product. So we obtain a Chernoff-
type bound: for $r\in(0,1)$,

(3.13)
$[y^{n-a}](1-\Phi_{1}(y))^{-e(\mathcal{T})}\Phi^{\prime}(y)\leq\frac{(1-\Phi_{1}(r))^{-e(\mathcal{T})}\Phi^{\prime}(r)}{r^{n-a}}.$

As $\Phi(r)=1-\gamma(1-r)^{1/2}+O(1-r)$, we have

$\displaystyle 1-\Phi_{1}(y)$
$\displaystyle=1-\sum_{j>1}jp_{j}\Phi^{j-1}(y)=1-P^{\prime}(\Phi)$
$\displaystyle=1-P^{\prime}(1)-P^{\prime\prime}(1)(\Phi-1)+O((\Phi-1)^{2})$
$\displaystyle=\chi(1-r)^{1/2}\bigl{(}1+O((1-r)^{1/2})\bigr{)},\quad\chi:=\gamma\sigma^{2}=(2p_{0}\sigma^{2})^{1/2},$

and $\Phi^{\prime}(y)=O((1-r)^{-1/2})$. So the RHS of (3.13) is of order
$\chi^{-e(\mathcal{T})}f(r)$, with $f(r):=(1-r)^{-e(\mathcal{T})/2}r^{-n+a}.$
$f(r)$ attains its maximum

$\frac{\bigl{[}n-a+e(\mathcal{T})/2\bigr{]}^{n-a+e(\mathcal{T})/2}}{(n-a)^{n-a}\,\bigl{[}e(\mathcal{T})/2\bigr{]}^{e(\mathcal{T})/2}}\leq
cn^{1/2}\binom{n-a+e(\mathcal{T})/2}{n-a}$

at $r_{n}=\frac{n-a}{n-a+e(\mathcal{T})/2}$, which is $1-\Theta(a/n)$, since
$e(\mathcal{T})\in[a,2a]$ and $a=o(n)$, see (3.10). In addition, the binomial
factor is at most $\binom{n}{n-a}=\binom{n}{a}$. Hence

$\displaystyle[y^{n-a}](1-\Phi_{1}(y))^{-e(\mathcal{T})}\Phi^{\prime}(y)\leq
c_{1}n\Bigl{(}\chi+O(\sqrt{a/n})\Bigr{)}^{-e(\mathcal{T})}\binom{n}{a}$
$\displaystyle\leq
c_{1}n\lambda^{a}\binom{n}{a},\quad\lambda>\lambda(\mathbb{p})=\left\\{\begin{aligned}
&\chi^{-2},&&\chi\leq 1,\\\ &\chi^{-1},&&\chi>1.\end{aligned}\right.$

Hence, using the second line equation in (3.12), and
$\mathbb{P}(A_{n})=\Theta(n^{-3/2})$, we obtain

(3.14) $\mathbb{P}(S\text{ induces }\mathcal{T}\text{ in
}T_{n})\leq\frac{c_{1}n}{a!}\,\lambda^{a}\prod_{v\in
V(\mathcal{T})}p_{d(v,\mathcal{T})}.$

Therefore we have:

$\mathbb{E}[X_{n,a}]\leq(n)_{a}\Bigl{(}\frac{c_{1}n^{5/2}\lambda^{a}}{a!}\Bigr{)}^{2}\sum_{\mathcal{T}}\prod_{v\in
V(\mathcal{T})}p^{2}_{d(v,\mathcal{T})},$

where the last sum is over all (finite) rooted trees $\mathcal{T}$, with
ordered children and $a$ unlabelled leaves. Define the probability
distribution $\mathbb{q}=\\{q_{j}\\}$: $q_{0}=1-\sum_{j\geq 2}p_{j}^{2}>0$,
$q_{1}=0$, $q_{j}=p_{j}^{2}$ for $j\geq 2$. Then we have

$\prod_{v\in
V(\mathcal{T})}\\!\\!p^{2}_{d(v,\mathcal{T})}=\left(\frac{p^{2}_{0}}{q_{0}}\right)^{a}\prod_{v\in
V(\mathcal{T})}q_{d(v,\mathcal{T})}.$

Observe that $\sum_{j\geq 2}jq_{j}<\sum_{j\geq 2}jp_{j}=1$. Therefore the
process with the offspring distribution $\mathbb{q}$ is almost surely extinct,
implying that

$\displaystyle\sum_{\mathcal{T}}\prod_{v\in
V(\mathcal{T})}p^{2}_{d(v,\mathcal{T})}=\left(\frac{p^{2}_{0}}{q_{0}}\right)^{a}\sum_{\mathcal{T}}\prod_{v\in
V(\mathcal{T})}q_{d(v,\mathcal{T})}\leq\left(\frac{p^{2}_{0}}{q_{0}}\right)^{a}[y^{a}]\Psi(y),$
$\displaystyle\qquad\qquad\qquad\Psi(y)=\sum_{j\geq
0}q_{j}\Psi^{j}(y)+q_{0}(y-1),$

i.e. $\Psi(y)$ is the p.g.f. of the number of leaves in the terminal tree for
the distribution $\mathbb{q}$. Let $C$ be a contour around $y=0$ within the
circle $|y|<1$ and let $\mathcal{C}$ be a circle of radius $\rho$ which is the
maximum point of $r-\sum_{j\geq 2}q_{j}r^{j}$. Then, using
$y=q_{0}^{-1}\bigl{(}\Psi(y)-\sum_{j\geq 2}q_{j}\Psi^{j}(y)\bigr{)}$, we have

$[y^{a}]\Psi(y)=a^{-1}[y^{a-1}]\Psi^{\prime}(y)=\frac{1}{2\pi
ia}\oint_{C}\frac{\Psi^{\prime}(y)}{y^{a}}\,dy\\\ =\frac{q_{0}^{a}}{2\pi
ia}\oint_{\mathcal{C}}\frac{d\eta}{\Bigl{(}\eta-\sum_{j\geq
2}q_{j}\eta^{j}\Bigr{)}^{a}}\leq\frac{q_{0}^{a}\rho}{a\Bigl{(}\rho-\sum_{j\geq
2}q_{j}\rho^{j}\Bigr{)}^{a}}.$

Therefore

$\sum_{\mathcal{T}}\prod_{v\in
V(\mathcal{T})}p^{2}_{d(v,\mathcal{T})}\leq\frac{\rho\,p_{0}^{2a}}{a\Bigl{(}\rho-\sum_{j\geq
2}q_{j}\rho^{j}\Bigr{)}^{a}}.$

So using $a!\geq(a/e)^{a}$, $\binom{n}{a}\leq(ne/a)^{a}$, we obtain: for all
$\lambda>\lambda(\mathbb{p})$,

$\mathbb{E}[X_{n,a}]\leq
c_{2}\frac{n^{5}\binom{n}{a}}{a!}\Bigl{(}\frac{(p_{0}\lambda)^{2}}{\rho-\sum\nolimits_{j\geq
2}q_{j}\rho^{j}}\Bigr{)}^{a}\leq
c_{3}n^{5}\biggl{(}\frac{n}{a^{2}}\,\frac{(ep_{0}\lambda)^{2}}{\rho-\sum\nolimits_{j\geq
2}q_{j}\rho^{j}}\biggr{)}^{a}\to 0,$

if $a\geq(1+\varepsilon)c(\mathbb{p})n^{1/2}$,
$c(\mathbb{p}):=ep_{0}\lambda(\mathbb{p})\Bigl{(}\rho-\sum_{j\geq
2}q_{j}\rho^{j}\Bigr{)}^{-1/2}$. Here
$\lambda(\mathbb{p})=\max(\chi(\mathbb{p})^{-2},\,\chi(\mathbb{p})^{-1})$, and
$\chi(\mathbb{p})=(2p_{0}\sigma^{2})^{1/2}$. ∎

Acknowledgment. I owe a debt of genuine gratitude to Ovidiu Costin and Jeff
McNeal for guiding me to the Weierstrass separation theorem. I thank Daniel
Bernstein, Mike Steel, and Seth Sullivant for an important feedback regarding
the references [8], [6] and [24]. Mike steered me away from pursuing a false
lead regarding the shapes of binary trees.

## References

  * [1] D. J. Aldous, Probability distributions on cladograms, Random Discrete Structures, The IMA Volumes in Mathematics and its Applications, 76, D. Aldous and R. Pemantle, Eds., Springer (1996) 1–18.
  * [2] D. J. Aldous and L. Popovic, A critical branching process model for biodiversity, Adv. Appl. Prob., 37 (2005) 1094–1115.
  * [3] D. J. Aldous, On the largest common subtree of random leaf-labelled binary trees, https://arxiv.org/pdf/2006.10545.pdf
  * [4] D. J. Aldous, Open problems: Largest common substructures in probabilistic combinatorics, (2003) https://www.stat.berkeley.edu/-aldous/Research/OP.
  * [5] E. A. Bender, Asymptotic methods in enumeration, SIAM Review, 16 (1974) 485–515.
  * [6] D. I. Bernstein, L. S. T. Ho, C. Long, M. Steel, K. St. John, A. S. Sullivant,  Bounds on the expected size of the maximum agreement subtree, SIAM J. Discrete Math., 29 (2015) 2065–2074.
  * [7] M. Bóna and P. Flajolet, Isomorphism and symmetries in random phylogenetic trees, J. Appl. Prob., 46 (2009) 1005–1019.
  * [8] D. Bryant, A. McKenzie, and M. Steel, The size of a maximum agreement subtree for random binary trees, in BioConsensus, DIMACS Ser. Discrete Math. Theoret. Comput. Sci.61, AMS (2003) 55–65.
  * [9] E. R. Canfield, Remarks on an asymptotic method in combinatorics, J. Comb. Theory, A, 37 (1984) 348–352.
  * [10] M. Carter, M. Hendy, D. Penny, L. A. Székely, and N. C. Wormald, On the distribution of lengths of evolutionary trees, SIAM J. Discrete Math., 3 (1990) 38–47.
  * [11] W. Ebeling, Functions of Several Complex Variables and Their Singularities, American Mathematical Society (2007).
  * [12] C. R. Finden and A. D. Gordon, Obtaining common pruned trees, J. Classification, 2 (1985) 255–276.
  * [13] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press (2009).
  * [14] A. Gordon, On the assessment and comparison of classifications, in (R. Tomassine, Ed.), Analyse de Données et Informatique, Le Chesnay, INRIA, France (1980) 149–160.
  * [15] L. S. Gradshteyn and I. M. Ryzhik, Table of Integrals, Series, and Products, 6th Edition, Academic Press (2000).
  * [16] E. F. Harding, The probabilities of rooted tree-shapes generated by random bifurcation, Adv. Appl. Probab. 3 (1971), 44–77.
  * [17] T. E. Harris, The Theory of Branching Processes, Springer–Verlag (1963).
  * [18] S. G. Krantz and H. R. Parks, The Implicit Function Theorem: History, Theory, and Applications, Birkhäuser (2013).
  * [19] A. Meir and J. W. Moon, On an asymptotic method in enumeration, J. Comb. Theory, A, 51 (1989) 77–89.
  * [20] A. Meir and J. W. Moon, Erratum: “On an asymptotic method in enumeration”, J. Comb. Theory, A, 52 (1989) 163.
  * [21] P. Misra and S. Sullivant, Bounds on the expected size of the maximum agreement subtree for a given tree shape, SIAM J. Discrete Math., 33 (2019) 2316–2325.
  * [22] A. M. Odlyzko, Asymptotic Enumeration Methods, in Handbook of Combinatorics, II, The MIT Press (1995) 1063–1229.
  * [23] C. Semple and M. Steel, Phylogenetics, Oxford University Press (2003).
  * [24] M. Steel, Phylogeny: Discrete and Random Processes in Evolution, Society for Industrial and Applied Mathematics (2016).
  * [25] M. Steel, Private communications.
  * [26] H. S. Wilf, Generatingfunctionology, 2nd Edition, Academic Press (1994).


# Electroweak scale physics & exotic searches at LHCb

O. Lupton on behalf of the LHCb collaboration  European Organization for
Nuclear Research (CERN), Meyrin, Switzerland

###### Abstract

The LHCb experiment has a broad and varied physics programme, extending far
beyond its core set of flavour physics measurements. This contribution
summarises recent electroweak scale measurements and searches for exotic
states in the dimuon final state.

##  1 Introduction

The LHCb detector is a single-arm forward spectrometer covering the
pseudorapidity range 2–5 that is principally designed for the study of $b$\-
and $c$-hadrons, but which is well-suited to a wide variety of electroweak
scale measurements and exotic searches that are highly complementary to other
experiments at the LHC and elsewhere. Several features of the detector that
are crucial for the core flavour physics programme, such as excellent vertex
and momentum resolution, and a powerful trigger system, contribute to
excellent jet tagging performance and sensitivity to low mass exotic states.
LHCb operates at a substantially lower instantaneous luminosity than the
general purpose detectors at the LHC, ATLAS and CMS, which results in a clean,
low pile-up environment in which to search for physics beyond the Standard
Model (SM).

##  2 Searches for exotic dimuon resonances

The excellent mass resolution and muon identification performance of the
detector over a wide range of momenta make searches for exotic dimuon
resonances an attractive prospect in LHCb data. Two results are presented in
this section, one covering a wide mass range and another focused on the region
in the immediate vicinity of the $\Upsilon$ resonances.

###  2.1 Dark photons

Several theories of physics beyond the SM propose new particles that could
explain the nature of dark matter. Such theories typically include additional
particles and dark boson-mediated forces, with a massive dark photon
$A^{\prime}$ being a popular feature. These dark photons typically do not
couple directly to charged SM particles, but they can gain a weak coupling to
the SM electromagnetic current via kinetic mixing. The strength of this
coupling is suppressed by a factor $\varepsilon$ with respect to the SM
photon. There is, therefore, a 2D parameter space to be probed.

The LHCb measurement[1] presented here uses the dimuon final state and is
based on a dataset corresponding to an integrated luminosity of
$\mathcal{L}=1.6\mathrm{\,fb^{-1}}$ recorded at $\sqrt{s}$ = 13 TeV during
2016. The flexible nature of the LHCb software trigger[2] allows the full rate
of prompt, i.e. consistent with originating at the primary $pp$ interaction
vertex, dimuon candidates to be recorded for analysis, from the dimuon mass
threshold up to the $Z^{0}$. The prompt-like dimuon spectrum is shown in Fig.
1. Backgrounds due to semileptonic decays of heavy-flavour hadrons, and
misidentified hadrons, are determined using fits to $\chi^{2}$-like variables
relating to the dimuon vertex quality. Background due to off-shell photon
decays $\gamma^{\ast}\to\mu^{+}\mu^{-}$ is irreducible and used to normalise
the dark photon search in a data-driven manner. The various well-known
quarkonia peaks labelled in Fig. 1 are excluded from the prompt-like search,
which extends up to $70\mathrm{\,Ge\kern-1.00006ptV\\!/}c^{2}$.

A search is performed for displaced dimuon vertices in the mass range
$[214,350]\mathrm{\,Me\kern-1.00006ptV\\!/}c^{2}$, in this case the background
composition is somewhat different. At radii of more than $5\mathrm{\,mm}$ and
low mass the background is dominated by real photon conversions in the vertex
locator material. Such conversions are vetoed using a new method based on a
large dataset of secondary hadronic interaction vertices[3]. At smaller radii
the background is dominated by heavy flavour decays.

No significant excess is found, and the limits set are shown in Fig. 2. The
prompt-like search sets world-best limits in the mass region
$[10.7,70]\mathrm{\,Ge\kern-1.00006ptV\\!/}c^{2}$, while the displaced search
probes a world-first region of parameter space. Future updates to these
searches are expected to take advantage of the novel all-software trigger in
the LHCb experiment upgrade for Run 3 of the LHC, and to extend to lower
values of $m(A^{\prime})$ by exploiting the dielectron channel.[4, 5]

Figure 1: Prompt-like dimuon spectrum used in the dark photon search with
various resonance peaks labelled.[1] Figure 2: Results of the dark photon
search. Both prompt-like (top) and displaced (centre) exclusions are shown.[1]

###  2.2 Search in vicinity of the $\boldmath\varUpsilon$ resonances

A dedicated search for dimuon resonances in the vicinity of the
$\Upsilon(n\mathrm{S})$ resonances has also been performed, probing closer to,
and in between, these peaks than the dark photon search.[6] The mass region
that is probed in this analysis is illustrated in Fig. 3. No significant
excess is seen, but the first limits are set in the mass range
$[8.7,11.5]\mathrm{\,Ge\kern-1.00006ptV\\!/}c^{2}$. Limits are set assuming
that the produced resonance is either a scalar or a vector boson.

Figure 3: Dimuon spectrum in the vicinity of the $\Upsilon(n\mathrm{S})$
resonances[6]. Peaks corresponding to scalar resonances $\phi$ are also shown,
where it has been assumed that
$\sigma(pp\to\phi)\mathcal{B}(\phi\to\mu^{+}\mu^{-})=50\,\mathrm{pb}$.[6]

Figure 4: $e\mu b$ invariant mass for all 44 selected candidates in the
$t\bar{t}$ measurement[9]. No fit is performed to this distribution, it is
presented simply to illustrate the signal purity.

##  3 $t\bar{t}$ production

Top quark physics forms an important part of the electroweak scale physics
programme at LHCb, and is an excellent example of an area of study where the
forward acceptance of the LHCb detector has several advantages with respect to
the central region instrumented by ATLAS and CMS. For example, top quark
cross-sections can provide important constraints on the large-$x$ gluon PDF,
with the forward kinematic region being particularly sensitive. The forward
region also provides a greater fraction of events with quark-initiated
production than central detectors, enhancing the size of $t\bar{t}$
asymmetries visible at LHCb.

Carrying out such measurements at LHCb presents several challenges relating to
the small acceptance, low luminosity and lack of missing energy measurement.
Despite these challenges, $t$ and $t\bar{t}$ production[7, 8] have previously
been observed at LHCb using data recorded at
$\sqrt{s}=7\mathrm{\,Te\kern-1.00006ptV}$ and
$8\mathrm{\,Te\kern-1.00006ptV}$.

The step to $\sqrt{s}=13\mathrm{\,Te\kern-1.00006ptV}$ for Run 2 of the LHC
has increased the LHCb-visible cross sections for top quark processes by an
order of magnitude, bringing new channels into statistical reach. The new
result presented here is a measurement of $t\bar{t}$ production at
$\sqrt{s}=13\mathrm{\,Te\kern-1.00006ptV}$ using the $e\mu b$ final state[9]
and an integrated luminosity of $\mathcal{L}=2\mathrm{\,fb^{-1}}$. This is a
very pure final state, as the second lepton suppresses $W+b\bar{b}$ production
and the opposite-flavour leptons suppress $Z^{0}+b\bar{b}$. The signal purity
is illustrated in Fig. 4, and the fiducial cross section is calculated as

$\sigma_{t\bar{t}}=\frac{N-N_{\mathrm{bkg}}}{\mathcal{L}\cdot\epsilon}\cdot\mathcal{F}_{\mathrm{res}}=126\pm
19\mathrm{\,(stat)}\pm 16\mathrm{\,(syst)}\pm
5\mathrm{\,(lumi)}\,\mathrm{fb^{-1}}.\\\ $ (1)

Figure 5 compares this result, and an extrapolation to the full cross section,
with SM predictions at next-to-leading order. The measured cross sections are
compatible with these predictions.

Figure 5: Fiducial (top) and extrapolated (bottom) $t\bar{t}$ cross sections,
compared to SM predictions at next-to-leading order[9].

Figure 6: Background subtracted dijet mass spectrum showing the $Z^{0}\to
b\bar{b}$ signal[10].

##  4 $Z^{0}\to b\bar{b}$

The final measurement discussed in these proceedings is the first observation
of $Z^{0}\to b\bar{b}$ production in the forward region[10]. This measurement
is an important validation of the LHCb jet reconstruction and $b$-tagging
performance. Two $b$-tagged jets are reconstructed, with a third balancing jet
also reconstructed to help control the QCD background and define signal and
control regions using a multivariate technique. The background-subtracted
signal distribution is shown in Fig. 6. The signal is observed with a
statistical significance of $6\sigma$ and the measured cross section is found
to be compatible with SM predictions at next-to-leading order.

##  5 Conclusions

LHCb has a broad and exciting programme of electroweak and exotic
measurements, which are typically still statistically limited and will benefit
significantly from further Run 2 updates and, crucially, from the LHCb upgrade
ahead of Run 3 of the LHC.

## References

## References

  * [1] LHCb collaboration, _Search for dark photons produced in 13 TeV $pp$ collisions_, Phys. Rev. Lett. 120 (2018) 061801, arXiv:1710.02867
  * [2] R. Aaij, _Tesla: an application for real-time data analysis in High Energy Physics_ , Comput. Phys. Commun. 208 (2016) 35, arXiv:1604.05596
  * [3] M. Alexander et al., _Mapping the material in the LHCb vertex locator using secondary hadronic interactions_ , arXiv:1803.07466
  * [4] P. Ilten, J. Thaler, M. Williams, and W. Xue, _Dark photons from charm mesons at LHCb_ Phys. Rev. D92 (2015) 115017, arXiv:1509.06765
  * [5] P. Ilten et al., _Proposed inclusive dark photon search at LHCb_ , Phys. Rev. Lett. 116 (2016) 251803, arXiv:1603.08926
  * [6] LHCb collaboration, _Search for a dimuon resonance in the $\varUpsilon$ mass region_, arXiv:1805.09820, submitted to JHEP
  * [7] LHCb collaboration, _First observation of top quark production in the forward region_ , Phys. Rev. Lett. 115 (2015) 112001, arXiv:1506.00903
  * [8] LHCb collaboration, _Measurement of the $t\bar{t}$, $W+b\bar{b}$ and $W+c\bar{c}$ production cross sections in $pp$ collisions at $\sqrt{s}$ = 8 TeV_, Phys. Lett. B767 (2017) 110, arXiv:1610.08142
  * [9] LHCb collaboration, _Measurement of forward top pair production in the dilepton channel in $pp$ collisions at $\sqrt{s}$ = 13 TeV_, arXiv:1803.05188, submitted to JHEP
  * [10] LHCb collaboration, _First observation of forward $Z\to b\bar{b}$ production in $pp$ collisions at $\sqrt{s}$ = 8 TeV_, Phys. Lett. B776 (2017) 430, arXiv:1709.03458


11institutetext: Department of Computer Science,
University of California, Irvine,
11email<EMAIL_ADDRESS>
22institutetext:  Department of Industrial Engineering and Operations
Research,
University of California, Berkeley,
22email<EMAIL_ADDRESS>
# Almost Tight Bounds for
Online Hypergraph Matching

Thorben Tröbst 11 Rajan Udwani 22

###### Abstract

In the online hypergraph matching problem, hyperedges of size $k$ over a
common ground set arrive online in adversarial order. The goal is to obtain a
maximum matching (disjoint set of hyperedges). A naïve greedy algorithm for
this problem achieves a competitive ratio of $\frac{1}{k}$. We show that no
(randomized) online algorithm has competitive ratio better than
$\frac{2+o(1)}{k}$. If edges are allowed to be assigned fractionally, we give
a deterministic online algorithm with competitive ratio
$\frac{1-o(1)}{\ln(k)}$ and show that no online algorithm can have competitive
ratio strictly better than $\frac{1+o(1)}{\ln(k)}$. Lastly, we give a
$\frac{1-o(1)}{\ln(k)}$ competitive algorithm for the fractional _edge-
weighted_ version of the problem under a free disposal assumption.

###### Keywords:

Online algorithms hypergraph matching set packing

##  1 Introduction

In the classic problem of online bipartite matching (OBM), we have bipartite
graph between resources (offline vertices) and agents (online vertices).
Agents arrive sequentially and edges incident on an agent are revealed on
arrival. Each agent must be matched to at most one available resource. Matches
are irrevocable and the goal is to maximize the size of the overall matching.
We evaluate the performance of an online algorithm using its competitive ratio
(CR). CR is the worst case ratio between the cardinality of online matching
and the optimal offline solution, which, for OBM, is the maximum cardinality
matching.

OBM captures the essence of resource allocation under sequential and
heterogeneous demand [11]. Fundamental to OBM and its many variations [17], is
the assumption that every agent seeks at most one type of resource. In a
variety of settings, ranging from revenue management in airlines [19, 20] to
combinatorial auctions [12, 13] and ridesharing [18], agents require a bundle
(set) of resources and an allocation that does not include every resource in
the bundle has no value. Inspired by this, we study a fundamental
generalization of OBM, namely, online hypergraph matching. A hypergraph is a
generalization of a graph where an edge can join any number of vertices. The
maximum cardinality of an edge, or hyperedge, is the rank of the hypergraph,
i.e. hyperedges of a rank $k$ hypergraph have at most $k$ vertices. A matching
in a hypergraph is a set of disjoint edges. In online hypergraph matching,
edges are revealed sequentially in a (possibly) adversarial order. On arrival
of an edge, we must make an immediate an irrevocable decision to include the
edge in the matching or reject it forever. The objective is to maximize the
size of the matching. In the fractional version of the problem, arriving edges
can be fractionally included in the matching, subject to the constraint that
the total fraction of edges incident on any vertex is at most one.

In case of OBM, the offline optimum can be found in polynomial time. In sharp
contrast, for a rank $k$ hypergraph it is NP hard to find a $\frac{\Omega(\log
k)}{k}$ approximation for the offline hypergraph matching problem, unless P=NP
[8]. As $k$ increases, the separation between these problems widens since the
hypergraph matching problem becomes harder to approximate. In this paper, our
goal is to find tight upper and lower bounds for online hypergraph matching
for large $k$. We consider both the integral and fractional version of the
online hypergraph matching problem.

In the integral case, it can be shown that a simple greedy algorithm that
always includes an arriving edge in the matching, if feasible, is
$\frac{1}{k}$ competitive. In fact, no deterministic algorithm can do better
in the worst case. From the hardness of the offline problem, no polynomial
time (online) algorithm can have competitive ratio better than
$\frac{\Omega(\log k)}{k}$ (unless P=NP). For the fractional case, where the
computational hardness disappears111In the fraction version, we evaluate
competitive ratio against a fractional relaxation of the offline problem that
can solved in polynomial time by using linear programming., a result for the
online packing problem [2] gives a $O(\log k)$ competitive algorithm for
online hypergraph matching. This exponential gap between the fractional and
integral setting raises the following natural question:

_For some $\epsilon>0$, is there an (exponential time) online algorithm with
competitive ratio $\frac{O(1)}{k^{1-\epsilon}}$ for (integral) online
hypergraph matching?_

We answer this question in the negative and establish the following result.
Let $o(1)=f(k)$ for some non-negative function $f(k)$ such that
$\lim_{k\to+\infty}f(k)=0$.

######  Theorem (Informal).

No (randomized and exponential time) online algorithm can achieve a
competitive ratio better than $\frac{2+o(1)}{k}$ for online hypergraph
matching.

Unlike the state-of-the-art complexity theoretic upper bound of
$\frac{\Omega(\log k)}{k}$, our result is unconditional and arises from the
online nature of the problem (as opposed to any computational barriers). For
the fractional case, we give new upper and lower bounds, closing the existing
constant factor gap for large $k$.

######  Theorem (Informal).

There is an efficient algorithm for fractional online hypergraph matching with
competitive ratio $\frac{1-o(1)}{\ln k}$. This is the best possible
(asymptotic) CR for any online algorithm.

##  2 Model

Consider a hypergraph $G$ with offline vertices (resources) $I$, online
vertices $t\in T$. A hyperedge $e\in E$ is a tuple $(S,t)$ where $S\subseteq
I$. For a degree $k$ hypergraph, we have $|S|\leq k$ for every edge, i.e., an
edge intersects at most $k$ offline vertices. In the vertex arrival model of
online hypergraph matching, vertices $t\in T$ arrive sequentially. On arrival
of a vertex $t$, all hyperedges incident on $t$ are revealed and we can
irrevocably choose at most one edge, provided this edge does not intersect
with any edge chosen prior to the arrival of $t$. The goal is to choose the
maximum number of disjoint edges, i.e., maximize the size of the matching. In
the edge-arrival model, that we discussed previously and use more frequently
in the paper, each online vertex has exactly one edge incident on it. In both
models, the arrival sequence is adversarial.

In terms of competitive ratio guarantee, the vertex arrival model is
equivalent to the edge arrival model for large $k$ (the regime of interest in
this paper). To see this, observe that an $\alpha$ competitive algorithm for
the vertex arrival model is also $\alpha$ competitive for the edge arrival
model. Further, given an $\alpha$ competitive algorithm for degree $k+1$
hypergraphs in the edge arrival model, we can construct an online algorithm
with CR $\alpha$ for degree $k$ hypergraphs in the vertex arrival model. The
algorithm for vertex arrivals will emulate the edge arrival based algorithm on
a transformed instance with edge arrivals. On arrival of a vertex $t\in T$
with incident edges $\\{e_{1},e_{2},\cdots,e_{m}\\}$ in the vertex arrival
model, we create $m$ new arrivals and add an additional offline vertex $i_{t}$
in the edge arrival instance. For $\ell\leq m$, the $\ell$-th new arrival in
the edge arrival instance has a single edge $E_{\ell}\cup\\{i_{t}\\}$. We
input the $m$ edges one-by-one (in arbitrary order) to the algorithm for edge
arrivals. If the algorithm chooses edge edge $\ell\in[m]$, then we choose edge
$e_{\ell}$ for arrival $t$ in the vertex arrival model. This procedure gives
an online algorithm for the vertex arrival model with CR $\alpha$.

In the fractional version, the optimal offline solution in edge arrival model
is a solution to the following linear program,

$\displaystyle\textbf{Fractional LP:}\qquad\max_{\\{x_{e}\\}_{e\in E}}$
$\displaystyle\sum_{e\in E}x_{e},$ $\displaystyle s.t.\,$
$\displaystyle\sum_{i\in e}x_{e}$ $\displaystyle\leq 1,\qquad\forall i\in I,$
$\displaystyle x_{e}$ $\displaystyle\geq 0\qquad\forall e\in E.$

Decision variable $x_{e}\in[0,1]$ in the LP captures the fraction of edge $e$
included in the matching. The constraint, $\sum_{i\in e}x_{e}\leq 1$, enforces
total fraction of edges incident on a resource $i\in I$ to be at most 1. An
online algorithm can include arbitrary fraction of each arriving edge, subject
to the same constraint as the LP.

Finally, note that by adding dummy resources we can assume w.l.o.g., that
every edge has exactly $k$ offline vertices. Unless stated otherwise, in the
rest of the paper we consider the edge arrival model and assume that instances
are $k$-uniform, i.e., every edge intersects $k$ offline vertices.

###  2.1 Related Work

Perhaps closest to our setting is the work of Buchbinder and Naor [2] on
online packing. They considered an online packing problem that generalizes the
fractional online hypergraph matching problem and gave a $O(\log k)$
competitive algorithm. Buchbinder and Naor [2] also showed that no online
algorithm can have competitive ratio better than $\Omega(\log k)$ for
fractional online hypergraph matching. A special case of the online packing
problem was considered earlier in [1], in the context of online routing.
Another closely related line of work is on the problem of network revenue
management (NRM) [19, 20]. This is a stochastic arrival setting where seats in
flights are offline resources allocated to sequentially arriving customers. A
customer with multi-stop itinerary requires a seat on each flight in the
itinerary. Recently, Ma et al. [15] gave a $\frac{1}{k+1}$ algorithm for NRM.
Another stream of work has focused on hypergraph matching from the perspective
of ridesharing. Pavone et al. [18] introduced a hypergraph matching problem
with deadlines to capture applications in ridesharing. Their model and results
are incomparable to ours. Lowalekar et al. [14] consider a model inspired by
ridesharing but with a stochastic arrival sequence. Finally, [12, 13] consider
related settings in combinatorial auctions that correspond to online
hypergraph matching with stochastic arrivals.

For the offline hypergraph matching problem, Hazan et al. [8] showed that
unless P=NP, no polynomial time algorithm can find an matching better than
$O(\frac{\log k}{k})$ of the optimum matching. [3, 4] give approximation
algorithms for the problem. To the best of our knowledge, the state-of-the-art
result is a $\frac{3}{k}$ approximation due to Cygan [4].

##  3 Integral Matchings

In the following, fix some $k\geq 2$. We will focus on the online hypergraph
matching problem in the edge arrival model. We start with a result that is
folklore in the literature on online matching [17].

######  Theorem 3.1 (Folklore).

There is a $\frac{1}{k}$-competitive algorithm for the online hypergraph
matching problem. This is the best possible CR for deterministic algorithms.

###### Proof.

Consider the online algorithm that includes an arriving edge $e$ in the
matching if it is disjoint with all previously included edges. Let
$e_{1},\ldots,e_{\ell}$ be the set of edges included in an offline optimum
solution and let $I_{o}\subseteq I$ denote the set of offline vertices that
are covered by the edges chosen in the online algorithm. For each edge
$e_{i}$, at least one of the resources that it intersects must be included in
$I_{o}$. Thus, $|I_{o}|\geq\frac{1}{k}\ell\,k$ and the online algorithm picks
at least $\frac{1}{k}\ell$ hyper edges.

To see that this is the best possible CR, consider two arrival sequences. In
the first sequence, we have a single arrival. In the second sequence, we
augment the first sequence with $k$ more arrivals such that the optimal
offline matching has size $k$ but the first edge intersects every other edge.
A deterministic algorithm with non-zero competitive ratio must match the first
arrival. ∎

In our first result, we show that even a randomized and possibly exponential
time online algorithm cannot achieve a much better competitive ratio for this
problem. To show this, we will use Yao’s minimax principle, as stated below.

######  Lemma 1 (Yao’s Principle).

Let $\alpha$ be the best competitive ratio of any randomized algorithm. Let
$\beta$ be the competitive ratio of the best deterministic algorithm against
some fixed distribution of instances. Then $\alpha\leq\beta$.

Before we get to our main result, we will first give a slightly weaker result
that serves both as a warm up and as a gadget for the main result. Recall
that, $o(1)=f(k)$ for some non-negative function $f(k)$ such that
$\lim_{k\to+\infty}f(k)=0$.

######  Theorem 3.2.

There does not exist a $\frac{4+o(1)}{k}$ competitive algorithm for the
$k$-uniform online hypergraph matching problem for any $\epsilon>0$.

###### Proof.

Using Yao’s principle, we will construct a distribution of instances with even
$k$ where $\mathrm{OPT}=\frac{k}{2}$ but the best deterministic online
algorithm can only achieve an expected matching size of $2$.

For any given even value $k$, the overall (random) instance $G_{k}$ will
consist of $\frac{k}{2}$ “red” edges and $\frac{k}{2}$ “blue” edges
constructed in $\frac{k}{2}$ phases. See Figure 1 for an example. In each
phase, do the following:

  1. 1.

Let $A$ be a set of vertices such that every vertex in $A$ is contained in
exactly one blue edge and every blue edge contains exactly one vertex from
$A$. Create a new edge $e_{1}$ which consists of $A$ and $k-|A|$ many new
vertices that have not been in any edges yet. Let $e_{1}$ arrive in the
instance.

  2. 2.

Repeat step 1 to get another edge $e_{2}$ with the same properties (note that,
in paritcular, $e_{2}$ will intersect $e_{1}$). Let $e_{2}$ arrive in the
instance.

  3. 3.

Randomly let one of $\\{e_{1},e_{2}\\}$ be red and the other blue with equal
probability.

The crucial properties of this construction are that each blue edge intersects
all future edges whereas each red edge is disjoint from all future edges. In
particular, the $\frac{k}{2}$ red edges form a maximum size matching, i.e.
$\mathrm{OPT}=\frac{k}{2}$.

Now consider some deterministic online algorithm $\mathcal{A}$. Let
$\alpha_{i}$ be the probability that $\mathcal{A}$ matches the red edge in
phase $i$ and let $\beta_{i}$ be the probability that $\mathcal{A}$ matches
the blue edge in phase $i$. Clearly, since the red and blue edges are
determined independently and uniformly at random, we must have
$\alpha_{i}=\beta_{i}$. Moreover, since at most one blue edge can be picked,
we know $\alpha_{1}+\dots+\alpha_{k/2}\leq 1$. Thus the expected size of the
matching generated by $\mathcal{A}$ is at most

$\alpha_{1}+\dots+\alpha_{k/2}+\beta_{1}+\dots+\beta_{k/2}\leq 2.\qed$

$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$$A_{1}$$A_{2}$$A_{3}$$A_{4}$$A_{5}$ Figure 1:
Shown is gadget $G_{10}$ proving that a competitive ratio of
$\frac{4}{k}+\epsilon$ is imposisble for $k=10$. The numbers indicate in which
phase each edge was added. The lightly shaded areas represent the vertex sets
$A_{1},\ldots,A_{5}$ which are useful for the construction of $H_{k}$.

######  Theorem 3.3.

There does not exist a $\frac{2+o(1)}{k}$ competitive algorithm for the online
hypergraph matching problem for any $\epsilon>0$.

###### Proof Sketch.

Due to space limitation, we give an outline of the main steps. We will use
induction to create a distribution over graphs $H_{k}$ for all $k$, with the
following properties:

  1. 1.

There are $k$ red and $k$ blue edges.

  2. 2.

The edges appear in $k$ phases, each of which consists of one red and one blue
edge where the color is chosen uniformly and independently at random.

  3. 3.

Every blue edge intersects all future edges.

  4. 4.

Every red edge is disjoint from all future edges.

$H_{1}$ is trivial to construct. We will just have a single vertex which is
simultaneously in both a red and blue singleton edge. Suppose that we can
construct $H_{\ell}$, for all $1\leq\ell\leq k-1$.

Now in order to construct $H_{k}$, we first employ the $\frac{k}{2}$ phases of
$G_{k}$. After this we can construct $\frac{k}{2}$ disjoint sets
$A_{1},\ldots,A_{k/2}$ of $\frac{k}{2}$ vertices each such that each $A_{i}$
intersects all blue edges and none of the red edges. See again Figure 1. Now,
for the remaining $k/2$ phases, we recursively employ the distribution
$H_{k/2}$ as follows. In phase $i+\frac{k}{2}$, we extend the the two edges
from phase $i$ of $H_{k/2}$ by the set $A_{i}$ to form sets of size $k$. This
gives us the two edges of rank $k$ for phase $i+\frac{k}{2}$.

Finally, one may check that properties $1-4$ are satisfied by induction. Thus,
we may conclude the proof similar to the proof of Theorem 3.2: the optimum
solution picks all $k$ red edges whereas any deterministic online algorithm
can only get an expected value of $2$ since at most one blue edge can be
picked and red and blue edges in each phase are indistinguishable for the
online algorithm. ∎

##  4 Fractional Matchings

Inspired by the Waterfilling (or Balancing) algorithm of [10, 16], designed
for online bipartite matching and its variants, we propose the following
online algorithm for fractional hypergraph matching in the edge arrival model.

1 For each $e\in E$, set $y_{e}\coloneqq 0$.

2 for  _each edge $e$ which arrives_ do

3 Increase $y_{e}$ continuously as long as $\sum_{i\in
e}(k\,\ln(k))^{x_{i}-1}\leq 1$ where $x_{i}\coloneqq\sum_{f\in E:i\in
f}y_{f}$.

Algorithm 1 Hypergraph Water-Filling

The final value of variable $y_{e}$ in the algorithm is the fraction of edge
$e$ that is included in the matching. At any moment, variable $x_{i}$ in the
algorithm captures the total fraction of edges incident on resource $i$ that
have been included in the matching. In other words, the value of $x_{i}$ is
the fraction of $i$ that has already been “matched" by the algorithm. In order
to “preserve" resources for future edges, Algorithm 1 stops matching an edge
when the value of $\sum_{i\in e}(k\,\ln(k))^{x_{i}-1}$ reaches 1. For
illustration, consider the following scenarios at the arrival of edge $e$
incident on resources $\\{1,2,\cdots,k\\}$.

$(i)$ $x_{i}=0\,\,\forall i\in[k]$ on arrival of $e$. Then, the algorithm will
match $\frac{\ln(\ln k)}{\ln(k)+\ln(\ln k)}$ fraction of the edge before
stopping.

$(ii)$ $x_{i}=0.5\,\,\forall i\leq\sqrt{k\ln(k)}$ and $x_{i}=0$ otherwise.
Then, for sufficiently large values of $k$, the algorithm does not match any
fraction of edge $e$.

We would like to note that Algorithm 1 constructs a fractional matching by
augmenting the primal solution $y$, whereas the online packing algorithm of
[2] augments the dual solution. We show that Algorithm 1 achieves the best
possible competitive ratio guarantee for large $k$.

######  Theorem 4.1.

For some non-negative function $f(k)$ such that $\lim_{k\to+\infty}f(k)=0$,
Algorithm 1 is $\frac{1-f(k)}{\ln(k)}$-competitive for the fractional online
hypergraph matching problem.

###### Proof.

Given a hypergraph $G$ with resources $I$ and set of hyperedges $E$, let
$\mathrm{ALG}$ denote the total revenue of the online algorithm and let
$\mathrm{OPT}$ denote the value of the optimal fractional offline solution. We
use a primal-dual approach inspired by [2, 5] to prove the result. Using weak
duality, it suffices to find a feasible solution to the following system of
linear inequalities,

$\displaystyle\sum_{e\in E}u_{e}+\sum_{i\in I}r_{i}$ $\displaystyle\leq$
$\displaystyle\mathrm{ALG},$ (1) $\displaystyle u_{e}+\sum_{i\in e}r_{i}$
$\displaystyle\geq$
$\displaystyle\frac{1-\frac{1}{\ln(k)}}{\ln(k)+\ln(\ln(k))}\quad\forall e\in
E.$ (2)

We set the dual variables using the following procedure. In the beginning, all
variables are set to 0. When Algorithm 1 is matching edge $e$ in line 3, we
interpret the quantity $\sum_{i\in e}(k\ln(k))^{x_{i}-1}$ as the _price_ of
edge $e$. Accordingly, if $e$ is matched some by some infinitesimal amount
$\mathrm{d}t$, then,

  1. 1.

For every resource $i\in e$, we increase the _revenue_ $r_{i}$ by
$(k\ln(k))^{x_{i}-1}\mathrm{d}t$.

  2. 2.

We increase the _utility_ $u_{e}$ of $e$ by $\left(1-\sum_{i\in
e}(k\ln(k))^{x_{i}-1}\right)\mathrm{d}t$.

Note that this implies that the total sum of all revenues and utilities is
equal to the total size of the matching, i.e., inequality (1) is satisfied.

It remains to show inequality (2) for every edge. Fix an arbitrary edge $e\in
E$ and consider the following two cases.

Case 1: Let $e\in E$ be arbitrary and let $x_{i}$ be the final fill levels of
the vertices $i\in e$. If $x_{i}=1$ for any $i$, we know that

$r_{i}=\int_{0}^{1}{(k\ln(k))^{t-1}\,\mathrm{d}t}=\frac{1-1/(k\ln(k))}{\ln(k)+\ln(\ln(k))}\geq\frac{1-1/\ln(k)}{\ln(k)+\ln(\ln(k))},$

so the revenue of this one vertex is already enough for the claim.

Case 2: Otherwise, we can assume that $x_{i}<1$ for all $i$. But in that case,
at any time at which $e$ was being matched by some $\mathrm{d}t$, $e$ would
have gotten a utility of at least,

$\max\left\\{0,\left(1-\sum_{i\in
e}(k\ln(k))^{x_{i}-1}\right)\mathrm{d}t\right\\}.$

Let us denote $P\coloneqq\sum_{i\in e}(k\ln(k))^{x_{i}-1}$, then this implies
that $u_{e}\geq\max\\{0,1-P\\}$. In total, we get

$\displaystyle u_{e}+\sum_{i\in e}r_{i}$
$\displaystyle\geq\max\\{0,1-P\\}+\sum_{i\in
e}\int_{0}^{x_{i}}(k\ln(k))^{t-1}\,\mathrm{d}t$
$\displaystyle=\max\\{0,1-P\\}+\frac{P-1/\ln(k)}{\ln(k)+\ln(\ln(k))}.$

Finally, observe that this quantity is minimized if $P=1$ under the assumption
that $\ln(k)+\ln(\ln(k))\geq 1$. Thus the claim, and the theorem, follows. ∎

Next, we show that no online algorithm can beat the performance of Algorithm
1.

######  Theorem 4.2.

For some non-negative function $f(k)$ such that $\lim_{k\to+\infty}f(k)=0$,
there does not exist any online algorithm which is
$\frac{1+f(k)}{\ln(k)}$-competitive for online hypergraph matching problem.

$\Rightarrow$$\Rightarrow$$\Rightarrow$$\Rightarrow$ Figure 2: Shown is the
upper-bounding construction with $k=10$, $l=3$, $\delta=0.5$. In each step we
replace the blue edges with as many red edges of $\frac{1}{1+\delta}$ times
the size as possible. Then we pick the $l$ red edges that the algorithm puts
the most weight on, make those the new blue edges and repeat until only
singleton edges are left.

###### Proof Sketch.

Due to space limitation, we give an outline of the main steps. Let
$\mathcal{A}$ be some algorithm for the fractional online hypergraph matching
problem. We can assume w.l.o.g., that $\mathcal{A}$ is deterministic. This is
because if $\mathcal{A}$ is randomized, we may create another algorithm
$\mathcal{A}^{\prime}$ which simply fractionally allocates every edge $e$ with
the expected value of $\mathcal{A}$. Then $\mathcal{A}^{\prime}$ is a
deterministic algorithm that performs just as well as $\mathcal{A}$.

Fix some large $l\in\mathbb{N}$ and small $\delta>0$. We will now construct an
instance in with some hyperedges may have less than $k$ vertices. The instance
is created according to the following procedure (see Figure 2).

  1. 1.

Set $m\leftarrow k$ and let $l$ disjoint edges of size $k$ arrive. Let $U$ be
the set of all vertices in these $l$ edges.

  2. 2.

If $m=0$, stop. Otherwise, set
$m\leftarrow\left\lfloor\frac{m}{1+\delta}\right\rfloor$.

  3. 3.

Partition $U$ into as many disjoint edges of size $m$ as possible and let
these arrive.

  4. 4.

Let $e_{1},\ldots,e_{l}$ be the $l$ of these edges that $\mathcal{A}$ matches
the most.

  5. 5.

Update $U\leftarrow e_{1}\cup\dots\cup e_{l}$ and go back to step 2.

Now let $\alpha$ be the competitive ratio of $\mathcal{A}$. Our first
observation is that steps 2–5 execute $(1-o(1))\log_{1+\delta}(k)$ many times
as $k\rightarrow\infty$. Moreover, in each iteration, we cover $l$ edges with

$\left\lfloor\frac{lm}{\left\lfloor\frac{m}{1+\delta}\right\rfloor}\right\rfloor\geq(1+\delta)l-1$

edges. Thus
$\mathrm{ALG}\geq\alpha\mathrm{OPT}\geq\alpha(1-o(1))\log_{1+\delta}(k)(\delta
l-1)$.

Let $E^{\star}\subseteq E$ be the set of edges which are picked at various
points in step 4 and let $y$ be the fractional matching constructed by
$\mathcal{A}$. Then because these edges are always the $l$ most covered edges
we know that

$y(E^{\star})\geq\min_{m\geq
1}\frac{l}{\left\lfloor\frac{lm}{\left\lfloor\frac{m}{1+\delta}\right\rfloor}\right\rfloor}\mathrm{ALG}\geq\frac{1}{1+\delta-\frac{1}{l}}\mathrm{ALG}.$

Lastly, we know that that all edges in $E^{\star}$ overlap in $l$ vertices,
namely the $l$ vertices that are contained in the final iteration of the loop.
This implies that $y(E^{\star})\leq l$. Combining these inequalities, we thus
get

$\displaystyle\alpha$
$\displaystyle\leq\frac{\left(1+\delta-\frac{1}{l}\right)l}{(1-o(1))\log_{1+\delta}(k)(\delta
l-1)}$ $\displaystyle=\frac{((1+\delta)l-1)\ln(1+\delta)}{(1-o(1))(\delta
l-1)}\cdot\frac{1}{\ln(k)}$

Finally, observe that for small $\delta$, large $l$ and large $k$, we get
$\alpha<\frac{1+\epsilon}{\ln(k)}$ as claimed. ∎

##  5 Edge-Weights

In this section, we consider the free disposal model for online weighted
matching [6], and generalize Algorithm 1 to online fractional weighted
hypergraph matching with free disposal. In this model, we are allowed to drop
previously matched edges with no penalty (though of course we do not count
such dropped edges towards our objective function).

1 For each $e\in E$, let $y_{e}\coloneqq 0$.

2 For each $i\in V$, let $f_{i}(t)\coloneqq\sum_{e:i\in e,w_{e}\geq t}y_{e}$
for all $t\geq 0$.

3 for  _each edge $e$ which arrives_ do

4 while  _$\sum_{i\in
e}\int_{0}^{w_{e}}(k\ln(k))^{f_{i}(t)-1}\,\mathrm{d}t\leq 1$_ do

5 for  _$i\in e$ with $x_{i}=1$_ do

6 Let $e^{-}_{i}$ be a minimum weight edge with $i\in e^{-}_{i}$ and
$y_{e^{-}_{i}}>0$.

7 $y_{e^{-}_{i}}\leftarrow y_{e^{-}_{i}}-\mathrm{d}x$

8 $y_{e}\leftarrow y_{e}+\mathrm{d}x$

9

Algorithm 2 Hypergraph Weighted Water-Filling

######  Theorem 5.1.

For some non-negative function $f(k)$ such that $\lim_{k\to+\infty}f(k)=0$,
Algorithm 2 is $\frac{1-f(k)}{\ln(k)}$-competitive for online fractional
weighted hypergraph matching problem with free disposal.

###### Proof Sketch.

Due to space limitation, we give an outline of the main steps. The proof will
use a similar primal-dual approach as Theorem 4.1. Once again, when Algorithm
2 is matching an edge $e$ by some amount $\mathrm{d}x$, we split the resulting
gain into _revenue_ and _utility_ through the price $\sum_{i\in
e}\int_{0}^{w_{e}}(k\ln(k))^{f_{i}(t)-1}\,\mathrm{d}t$. However, this time the
price is split into three parts:

  1. 1.

Each $i\in e$, earns a revenue of $\sum_{i\in
e}\int_{w_{e^{-}_{i}}}^{w_{e}}(k\ln(k))^{f_{i}(t)-1}\,\mathrm{d}t\mathrm{d}x$
where $w_{e^{-}_{i}}\coloneqq 0$ if $x_{i}<1$.

  2. 2.

$e$ earns a utility of $\left(w_{e}-\sum_{i\in
e}\int_{0}^{w_{e}}(k\ln(k))^{f_{i}(t)-1}\,\mathrm{d}t\right)\mathrm{d}x$.

  3. 3.

The remaining

$\displaystyle\phantom{=}\left(\sum_{i\in
e}\int_{0}^{w_{e}}(k\ln(k))^{f_{i}(t)-1}\,\mathrm{d}t-\sum_{i\in
e}\int_{w_{e^{-}_{i}}}^{w_{e}}(k\ln(k))^{f_{i}(t)-1}\,\mathrm{d}t\right)\mathrm{d}x$
$\displaystyle=\sum_{i\in e}w_{e^{-}_{i}}\mathrm{d}x$

can be thought of as “paying off” the edges $e^{-}_{i}$ for the decrease in
$y_{e^{-}_{i}}$.

This means that as $e$ gets matched by some $\mathrm{d}x$, the total increase
in the weight of the matching is $\left(w_{e}-\sum_{i\in
e}w_{e^{-}_{i}}\right)\mathrm{d}x$ which is also the total increase in all
revenues and utilities. Thus, if $r_{i}$ is the final revenue of $i\in V$ and
$u_{e}$ is the final utility of $e\in E$, this implies that
$\mathrm{ALG}=\sum_{i\in V}r_{i}+\sum_{e\in E}u_{e}$. Recall also from the
proof of Theorem 4.1, that this, together with the following claim,
establishes the result.

Claim: For any $e\in E$, we have

$u_{e}+\sum_{i\in e}r_{i}\geq w_{e}\frac{1-1/\ln(k)}{\ln(k)+\ln(\ln(k))}.$

Proof of Claim: Let $f_{i}$ be the step function defined in Algorithm 2 at the
end of the algorithm. Then because prices (and utilities) are non-decreasing,
we know that

$u_{e}\geq w_{e}-\sum_{i\in
e}\int_{0}^{w_{e}}(k\ln(k))^{f_{i}(t)-1}\,\mathrm{d}t$

On the other hand, the total revenue collected by each $i\in V$ satisfies

$\displaystyle r_{i}$
$\displaystyle=\int_{0}^{\infty}\int_{0}^{f_{i}(t)}(k\ln(k))^{s-1}\,\mathrm{d}s\,\mathrm{d}t$
$\displaystyle=\int_{0}^{\infty}\frac{\sum_{i\in
e}(k\ln(k))^{f_{i}(t)-1}-1/\ln(k)}{\ln(k)+\ln(\ln(k))}\,\mathrm{d}t$

Now let $P(t)\coloneqq\sum_{i\in e}(k\ln(k))^{f_{i}(t)-1}$, then this means
that

$\displaystyle u_{e}+\sum_{i\in e}r_{i}$
$\displaystyle=\max\left\\{0,w_{e}-\int_{0}^{w_{e}}P(t)\,\mathrm{d}t\right\\}+\int_{0}^{\infty}\frac{P(t)-1/\ln(k)}{\ln(k)+\ln(\ln(k))}\,\mathrm{d}t$
$\displaystyle\geq\max\left\\{0,w_{e}-\int_{0}^{w_{e}}P(t)\,\mathrm{d}t\right\\}+\int_{0}^{w_{e}}\frac{P(t)-1/\ln(k)}{\ln(k)+\ln(\ln(k))}\,\mathrm{d}t$
$\displaystyle=\max\left\\{0,w_{e}-\int_{0}^{w_{e}}P(t)\,\mathrm{d}t\right\\}+\frac{\int_{0}^{w_{e}}P(t)\,\mathrm{d}t-w_{e}/\ln(k)}{\ln(k)+\ln(\ln(k))}.$

Since this expression is minimized for
$\int_{0}^{w_{e}}P(t)\,\mathrm{d}t=w_{e}$, the claim and thus the theorem
follows. ∎

##  6 Conclusion

In this paper we have given a tight asymptotic bound for the fractional
$k$-uniform hypergraph matching problem and an almost tight bound for the
integral variant. This leaves room for some interesting directions for future
research:

A major open problem is to beat the $\frac{1}{k}$ lower bound in the integral
setting. In fact, just recently Gamlath et al. [7] showed that for $k=2$, no
algorithm beats $\frac{1}{2}$, even if the underlying graph is bipartite.
However, their construction in fact shows this result for the fractional
setting and where we know how to beat $\frac{1}{k}$ for large $k$. It thus
remains open whether $\frac{1}{k}+\epsilon$ is achievable for _any_ $k$. In
fact, for small $k$, one may also explicitly distinguish between edge arrival
and vertex arrival models as mentioned in Section 2 or even the fully-online
arrival model of Huang et al. [9]. To the best of our knowledge, these models
have only been explored for $k=2$ and showing any improvement over
$\frac{1}{k}$ for $k>2$ even under additional assumptions such as
$k$-partiteness would be rather interesting.

Finally, we remark that even in the fractional setting, exactly tight bounds
are only known for $k=2$ and finding a tight non-asymptotic result remains
open.

####  6.0.1 Acknowledgements

We would like to thank Vijay Vazirani for several helpful comments during both
the research and writing process.

## References

  * [1] Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive on-line routing. In: Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. pp. 32–40. IEEE (1993)
  * [2] Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Mathematics of Operations Research 34(2), 270–286 (2009)
  * [3] Chan, Y.H., Lau, L.C.: On linear and semidefinite programming relaxations for hypergraph matching. Mathematical programming 135(1), 123–148 (2012)
  * [4] Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 509–518. IEEE (2013)
  * [5] Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of ranking for online bipartite matching. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. pp. 101–107. SIAM (2013)
  * [6] Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., Pál, M.: Online ad assignment with free disposal. In: International workshop on internet and network economics. pp. 374–385. Springer (2009)
  * [7] Gamlath, B., Kapralov, M., Maggiori, A., Svensson, O., Wajc, D.: Online matching with general arrivals. pp. 26–37 (11 2019). https://doi.org/10.1109/FOCS.2019.00011
  * [8] Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. computational complexity 15(1), 20–39 (2006)
  * [9] Huang, Z., Kang, N., Tang, Z.G., Wu, X., Zhang, Y., Zhu, X.: Fully online matching. J. ACM 67(3) (may 2020). https://doi.org/10.1145/3390890, https://doi.org/10.1145/3390890
  * [10] Kalyanasundaram, B., Pruhs, K.R.: An optimal deterministic algorithm for online b-matching. Theoretical Computer Science 233(1-2), 319–325 (2000)
  * [11] Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the twenty-second annual ACM symposium on Theory of computing. pp. 352–358 (1990)
  * [12] Kesselheim, T., Radke, K., Tönnis, A., Vöcking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: European symposium on algorithms. pp. 589–600. Springer (2013)
  * [13] Korula, N., Pál, M.: Algorithms for secretary problems on graphs and hypergraphs. In: International Colloquium on Automata, Languages, and Programming. pp. 508–520. Springer (2009)
  * [14] Lowalekar, M., Varakantham, P., Jaillet, P.: Competitive ratios for online multi-capacity ridesharing. arXiv preprint arXiv:2009.07925 (2020)
  * [15] Ma, Y., Rusmevichientong, P., Sumida, M., Topaloglu, H.: An approximation algorithm for network revenue management under nonstationary arrivals. Operations Research 68(3), 834–855 (2020)
  * [16] Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. Journal of the ACM (JACM) 54(5), 22–es (2007)
  * [17] Mehta, A., et al.: Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science 8(4), 265–368 (2013)
  * [18] Pavone, M., Saberi, A., Schiffer, M., Tsao, M.W.: Online hypergraph matching with delays. Operations Research (2022)
  * [19] Simpson, R.W.: Using network flow techniques to find shadow prices for market demands and seat inventory control. MIT Press, Cambridge, MA (1989)
  * [20] Talluri, K., Van Ryzin, G.: An analysis of bid-price controls for network revenue management. Management science 44(11-part-1), 1577–1593 (1998)