WIHHIWHHHHIHHUNWWNWlHlWlll

      
      

(00')

 

4—:
O
U)

H

ms

1 001/

This is to certify that the

dissertation entitled

Hypertrees in d-uniform Hypergraph

presented by

Wai Cheong Siu

has been accepted towards fulfillment
of the requirements for

Ph . D . degree in Mathematics

 

Xena (7W

0 Major professor

Date April 30. 2002

MS U is an Affirmative Action/Equal Opportunity Institution 0- 12771

—-——-

V_...V

 

 

LIBRARY

Michigan State
University

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE

DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/01 c:/CIRC/DatoDue.p65-p.15

 

Hypertrees in d—uniform hypergraphs
By

Wai-Cheong Siu

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements

for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

2002

ABSTRACT

Hypertrees in d-uniform hypergraphs
By

Wai-Cheong Siu

Traditionally a d-uniform hypertree has been defined as a d-uniform hypergraph
that is connected and has no cycle. In this dissertation, we study various alter-
native definitions of d-uniform hypertrees. In particular, we formulate a new kind
of hypertree called a (d, k)-tree. We have enumerated rooted and unrooted labeled
(d, k)-trees and (d, k)-forests. We also provide some results on (d, k)-trees in random
hypergraphs. In particular, we have approximated the number of edges in a random

hypergraph so that with high probability a Spanning hypertree exists.

ACKNOWLEDGMENTS

I would like to thank my thesis advisor Professor Edgar M. Palmer for his patience,
guidance and valuable advice. I also would like to thank Professor Bruce E. Sagan
for his lectures that equipped me the knowledge of combinatorics and graph theory
and for serving in my committee. I would like to thank Professor Abdol-Hossein
Esfahanian, Peter Magyar and Eric Torng for serving in my guidance committee.
Finally, I would like to thank my parents, Siu, Tsang-Kwai and Chow, How-Ling and

my sister Siu, Mei-Lam for their encouragement and support.

iii

TABLE OF CONTENTS

LIST OF FIGURES
LIST OF TABLES

1 Introduction

1.1 Hypergraphs .................................
1.2 Hypertrees ...................................
1.2.1 Traditional definition of hypertrees ....................
1.2.2 N P-hypertrees ...............................
1.2.3 HP—hypertrees ...............................
1.2.4 BD-hypertrees ...............................
1.2.5 Tomescu definition of hypertrees .....................

2 The definition and enumeration of (d, k)-hypertrees

2.1 Definition of a (d, k)-tree ...........................
2.2 Enumeration of (d, k)-trees ..........................
2.3 Forests of (d, k)-trees .............................

2.4 Enumeration of 3—trees ............................

3 Threshold problems for random hypergraphs

3.1 Random hypergraphs .............................
3.2 Spanning trees in random hypergraphs ...................
3.3 Maximum matchings in hypergraphs ....................
3.3.1 Hypergraph Ho and Ho-hypertree .....................
3.3.2 A matching that covers all vertices ....................

BIBLIOGRAPHY

iv

<

S.

OCOQrP-iD-ANH

1.1
1.2
1.3
1.4
1.5
1.6
1.7

LIST OF FIGURES

Hypergraph H1 ................................
Traditional 3-uniform hypertree H2 .....................
H3 .......................................
NP-hypertree H4 ...............................
HP-hypertree H5 ...............................
BD—hypertree H5 ............................... 1
Tomescu 3-hypertree H 7 ........................... 1

HOOOKICHUIOJ

1.1
1.2
1.3
1.4
1.5
1.6
1.7

2.1
2.2

LIST OF TABLES

Number of Unlabeled and Labeled 3—uniform Hypertrees .......... 6
Number of Unlabeled and Labeled 4—uniform Hypertrees .......... 6
Number of Unlabeled and Labeled 3-uniform NP-hypertrees ....... 7
Number of Unlabeled and Labeled 4-uniform NP-hypertrees ....... 7
Number of HP-hypertrees with d = 3 .................... 9
Number of HP—hypertrees with d = 4 .................... 9
Number of Labeled BD—hypertrees ..................... 10
Average Number of Components in a (d, k)-forest ............. 25
Number of 1-rooted, 2-rooted, rooted 3-trees and unrooted 3-trees. . . . . 28

vi

CHAPTER 1

Introduction

The study of graph structure has a long history which datas to the early eighteenth
century when the Kéinigsberg bridge problem was posed. The problem was solved in
1736 by Euler in the first paper published on graph theory [BiLW76]. For the next
two hundred years graph theory underwent steady and important growth and many
famous mathematicians, like Cayley, Hamilton, Heawood, Kirchhoff and Tait were
involved in formulating and solving interesting new problems. Their efforts formed
the footings of the foundation of graph theory. In the last half of the 20$ century,
the growth of graph theory has been impressive, as evidenced by the numerous books
and new jounals devoted to the subject, as well as by many other important scholarly
activities. No doubt the applications of graph theory to other areas such as com-
puter science, operation research, theoretical chemistry, etc, account for some of this
growth. But mathematicaians have also been drawn by the beauty of the subject and
the promise of the area to continue to be a rich source of attractive and important
problems.

Among the many interesting types of graphs that have been studied throughout
the history of graph theory, the tree is the simplest and the most useful. Therefore,
counting the number of tress (both labeled and unlabeled) attracted the attention

of many researchers. For a comprehensive survey of techniques and results on tree

1

enumeration, the reader can consult [M70].

Besides developing the theory of graphs, mathematicans started to generalize the
concept of graphs and trees to higher dimensions in the 1960’s, when hypergraphs and
hypertrees were introduced. Claude Berge was a pioneer in this field and the reader
can consult his books [Be70], [Be73] and [Be87] for an introduction to hypergraphs.
We will review and discuss verious definitions for hypertrees in the next sections.

At almost the same time, Erdbs and Rényi wrote a series of remarkable papers
[ErR59], [ErRGO], [ErR61a], [ErR61b], [ErR64] and [ErR68] that gave birth to the
theory of random graphs. One of their startling discoveries revealed the concept of
the probabilistic threshold for monotone graph properties. These prOperties were
found to occur rather abruptly in large random graphs when the number of edges
increased only slightly. And Erdbs and Rényi discovered many important examples.
To illustrate, let wn —) 00 as n —+ co and consider a sequence {Ga} of random
graphs. If each a. has W edges, then with high probability G, has a spanning
tree, i.e. the probability that G,, has a spanning tree approaches 1 as n ——+ 00. On
the other hand if G7, has only 39392151 edges, then with high probability Gn does not

have a spanning tree.

1. 1 Hypergraphs

Let V = {v1,v2,...,v,,} be a finite set and E = {e1,e2,...,em} be a subset of the

power set 1P(V). The ordered pair H = (V, E) is called a hypergraph by [Be87] if
(1) e,;éz (i=1,2,...,m)
(2) U21 61' = V-

The finite set V is called the vertex set and the elements of V are vertices. The set

E is the edge set of the hypergraph H and the elements of E are edges of hypergraph

2

Figure 1.1: Hypergraph H1

 

 

 

 

 

H. The cardinality of the vertex set V is the order of the hypergraph H and is
denoted by n. The cardinality of the edge set E is the size of the hypergraph H
and is denoted by m. For example, H1 = (V1,E1) where V1 = {1,2,3,4, 5} and
E1 = {{1, 2, 3}, {2, 3, 4, 5}, {1,4}} is a hypergraph (see Figure 1.1). The enumeration
problem for unlabeled hypergraph was treated by Tom Ishihara [1301] using standard
Polya theory [HaP73].

A hypergraph H is d-uniform if the edges all have the same cardinality d. A
one—element edge is a singleton or loop.

Let u,v,wo,w1, . . . ,wt be vertices of H and e1, e2, . . . , e, be edges of H where t is
a non-negative integer. If mo 2 u, wt = v, we 6 el, wt 6 et, 21).- E e.- and w,- E e,“ for
all z' E [t - 1], the sequence (wo,e1,w1,e2, . . . ,e,,wt) is called a u — v walk of H . A
u — v walk is a u — v trail if all the edges e,- are distinct. A u — v walk is called a path
if all the vertices w,- are distinct. A u — 2) walk is called a u — v hyperpath if all the
vertices w,- and all the edges e.- are distinct. A u — 1) walk is called a cycle of length

t if t _>_ 2, u = v, w,- are distinct for 1 g i g t and all the edges e, are distinct. A

hypergraph H is connected if there is a u —- v path between any two vertices, u and

v in H. A hypergraph H is acyclic if it has no cycle.

1.2 Hypertrees

Here are five different definitions of a hypertree that have been used by researchers

in the development of the field.

1.2.1 Traditional definition of hypertrees

In the traditional definition, a hypertree is defined as a connected hy-

pergraph which contains neither 100ps nor cycles [SoTOO] [8084].

So, a d-uniform hypertree with d = 1 is an ordinary graph-theoretic
tree). For example, H2 with V(H2) = {1,2,3,4,5,6,7,8,9,10,11} and
E(H2) = {{1,2,3},{3,4,5},{4,6,7},{5,8,9},{9,10,11}} is a 3-uniform hy-
pertree (see Figure 1.2). However H3 with V(H3) = {1,2,3,4,5,6} and

E(H3) = {{1,2,3}, {2,3,4}, {3,4,5}, {2,4,6}} (see Figure 1.3) is a 3-uniform
hypergraph but not a hypertree, because it contains the following cycle:
{3}{3, 4, 5}{4}{2, 4, 6}{2}{1, 2, 3}{3}-

Table 1.1 and Table 1.2 give the number of 3—uniform and 4-uniform hypertrees
with small order n. These numbers were found by constructing the relevant configu-

rations.

1.2.2 NP-hypertrees

The N P-hypertrees were introduced by J. Nieminen and M. Peltola in their paper
[NiP99]. A hypergraph H is an NP—hypertree if H is trivial or the removal of any edge

from it results in a disconnected hypergraph. This family of hypertrees is a superset of

Table 1.1: Number of Unlabeled and Labeled 3-uniform Hypertrees.

 

 

n Unlabeled Labeléf
3 1 1
5 1 15
7 2 735
9 4 76,545
11 8 13,835,745

Table 1.2: Number of Unlabeled and Labeled 4-uniform Hypertrees.

 

 

n UnlaEeled Lawled
4 I 1
7 1 70
10 2 28,000
13 4 33,833,800
16 9 91,842,150,400

the family of traditional hypertrees. For example, H, with V(H4) = {1,2, 3,4,5,6}
and E(H4) = {{1,2,3},{3,4,5},{4,5,6}} is a 3-uniform NP-hypertree(see Figure
1.4). Notice that H4 is not a traditional hypertree but H2 (see Figure 1.2) is an
N P-hypertree.

Table 1.3 and Table 1.4 give the number of 3-uniform and 4-uniform NP-hypertrees
with small n. The data was determined by constructive methods. Notice that the

enumeration problem for NP-hypertrees has not been solved.

1.2.3 HP-hypertrees

Harary and Palmer [HaP68] defined certain families of graphs with tree-like structure
that correspond to hypergraphs. These are different from the traditional hypertrees

and so we will call them HP-hypertrees. These trees were characterized by [HaP68]

Figure 1.4: NP-hypertree H4

 

Table 1.3: Number of Unlabeled and Labeled 3-uniform NP-hypertrees

 

 

n Unlabeled Labeled
1 1 1
3 1 1
4 1 6
5 3 160
6 4 495

Table 1.4: Number of Unlabeled and Labeled 4-uniform NP—hypertrees

 

 

n Unlabeled Labeled
1 1 1
4 1 1
5 1 10
6 2 11 0
7 4 2,275

Figure 1.5: HP-hypertree H5
( ‘
J

For any positive integer d greater than 1:

(1) Any d-set V forms a hypertree H = (V, E) with E = {V}.

(2) A hypertree H = (V, E) of order n can be formed as follows: First consider a
hypertree H = (V', E') of order n — 1 and a new vertex 2) ¢ V'. Then we pick a
(d — 1)-subset e from an edge e' E E'. Next set V = V' U {o} and

E = E’ U {6 U {v}}.

For example, H5 with V(H5) = {1, 2, 3,4, 5, 6} and E(H5) =
{{1, 2, 3}, {2, 3,4}, {3,4, 5}, {4,5, 6}} is an 3-uniform HP-hypertree. (see Fig—
ure 1.5)

Table 1.5 and Table 1.6 give the number of HP-hypertrees for small n with d = 3
and d = 4. The enumeration of labeled HP-hypertrees was solved by Beineke and
Pippert (see [BeP69]). Harary and Palmer (see [HaP68]) handled the unlabeled case.
The numbers for the labeled cases in the tables are calculated by using the formula
from [BeP69]. The numbers for the unlabeled cases in the Table 1.5 are from [HaP68]

and those in Table 1.6 are found by construction.

Table 1.5: Number of HP-hypertrees with d = 3

 

 

n Unlabeled labeled
3 1 1
4 1 6
5 2 70
6 5 1,215
7 12 2,7951

Table 1.6: Number of HP-hypertrees with d = 4

 

 

n Unlabeled LabelecT
4 1 1
5 1 10
6 2 200
7 4 5,915

1.2.4 BD-hypertrees

The BD-hypertrees were studied intensively by Andreas Brandsta'dt, V. D. Chepoi
and Feodor F. Dragan (see [BrCD95], [BrD96] and [BrCD98]). This hypertree
structure can be used to construct efficent graph algorithms. Here, a hypergraph
H = (V, E) is a BD-hypertree if there is an ordinary graph-theoretic tree T with
vertex set V such that every edge e E E induces a subtree in T. For exam-
ple, H6 with V(Hs) = {1,2, 3,4,5,6} and E(Hs) = {{1,2},{2,3,4},{3,5,6}} is a
BD-hypertree. Notice that the ordinary tree T with V(T) = {1,2, 3, 4, 5,6} and
E(T) = {{1, 2}, {2,3}, {3,4}, {3,5}, {5,6}} satisfies the above requirement.(see Fig-
ure 1.6) Table 1.7 gives the number of BD-hypertrees with small 11.

Notice that the enumeration problem for BD—hypertrees has not been solved.

Figure 1.6: BD-hypertree H6

9‘1»

Table 1.7: Number of Labeled BD-hypertrees

 

 

n Labeled
2 1
3 9
4 401

1.2.5 Tomescu definition of hypertrees

The Tomescu hypertrees were introduced to obtain the Bonferronni inequalities by
Ioan Tomescu. They are discussed in [T086], [T092], [ToZ94]. At least seven equiva—
lent definitions of these hypertrees have been pr0posed. The following is the version
using recursive definition to define the hypertrees.

Let T = (V, E) be an h-uniforrn hypergraph. When h = 2, T is a graph and T is
called an h-hypertree if T is a tree. When h 2 3, T is an h-hypertree if and only if

(1) | V ]= h and E = {V}, i.e. T has exactly one edge consisting of all h vertices
of V.

OR

(2) [ V [_>_ h + 1 then there is a vertex v,- e V such that if 81,82, . . .,eq denote

10

Figure 1.7: Tomescu 3-hypertree H7

 

all edges containing u.- then e1\{v;},...,eq\{v,-} induce an (h — 1)-hypertree with
vertex set V\{v.-} and the remaining edges of T induce an hrhypertree with vertex
set V\{v,~}.

For example, H7 with V(H7) = {1,2,3,4,5, 6}, E(H7) =
{{1,3,4}, {1,4,6}, {1,5,6}, {2,3,4}, {2,4,5}, {2,4,6}} (see Figure 1.7) is a Tomescu
3-hypertree.

The enumeration of Tomescu hypertrees remains an unsolved problem.

11

CHAPTER 2

The definition and enumeration of

(d, k)-hypertrees

In this chapter, we define and enumerate two tree-like hypergraph structures which
we call them ((1, k)-trees and d-trees, where d 2 2 and k > 0 are integers. These new

definitions generalize traditional and HP-hypertrees.

2.1 Definition of a (d, k)-tree

For I: fixed, with 1 S k g d - 1, a (d, k)-tree is defined inductively as follows :

(1) A single edge is a (d, k)-tree.

(2) Suppose T is a (d,k)-tree with m vertices, then the hypergraph formed by
adding a new edge consisting of d - k new vertices and any It vertices of any edge of
T is also a (d, k)-tree.

Note that when k = d — 1, these are the d—dimensional HP—hypertrees that first
appeared in [HaP68] and were subsequently studied in [M70] [BeM69] and [BeP69].
Of course, when d = 2, then k = 1, we have the ordinary trees of graph theory with
at least one edge. When d = 3 and k = 1, they are pure Husimi trees [Hu50].

If we relax condition (2) and allow k to vary (1 g k g d — 1), we obtain a different

12

kind of hypertree called a d-tree.

2.2 Enumeration of (d, k)-trees

We begin by determining egf’s for various types of rooted (d, k)-trees. The relation-
ships between these egf’s are determined in the following lemmas, concluding with
a specific generalization of Cayly’s famous n"’2 formula. Note that the number of

vertices |V(T)| and the number of edges IE (T)| of a (d, k)-tree satisfy the equation
lVl -k= |E|(d-k) (2-1)

which reduces to the familiar

IVI — = IE! (2.2)

for (2,1)-trees.

A simply rooted (d, k)-tree has as its root a linearly ordered k-subset of vertices
which belongs to exactly one edge.

Let ym be the number of labeled simply rooted (d, k)-trees with m edges, whose
vertices are labeled except for the k linearly ordered vertices of the root and let y be
the exponential generating function for these labeled simply rooted (d, k)-trees. Then

it follows from (2.1) that y has the form :

2‘”: $m(d-k) (2 3)
y = ym— - -
m=l (m(d - 19))!

Note that y1 = 1 and y2 = 69:3)(6) -— 1).

Lemma 2.1 The egf y for simply rooted (d, k)-trees satisfies the functional equation

_ (ell) (2)—1:1:‘1'4‘
y" (d—a!

 

94)

Proof : Since y is the eg‘f for the labeled simply rooted (d, k)—trees, e” is the egf for

the labeled (d, k)-trees which are rooted at an unlabeled, linearly ordered k-subset of

13

an edge (the k-subset may belong to many edges). Then, (4)“)—1 is the egf of (z) —
ordered c0pies of this kind of (d, k)-tree. Now, if we start with an ordered d-set of
vertices, then the order of the vertices imposes a natural order on all the k-subsets of
it. Next we use the orders to match up the (g) — 1 c0pies of special (d, k)-trees with
the k-subsets, and then, identify the vertices in the (d, k)-trees with the vertices in
the corresponding k-subsets using the orders. The result is a tree like structure whose
egf is (e”)(:)‘1. Now, if we label the unlabeled vertices and remove the order on the
d-set except for those vertices in the last k-subset (which has no special (d, k)-tree
assigned to it), we get a labeled, simply rooted (d, k)-tree. But its egf is 8" (jigfd—b
as in (2.4). D

A rooted (d, k)-tree has as its root a k-subset of vertices which belongs to at least
one edge. We denote by Y the egf for rooted (d, k)-trees whose vertices are all labeled,
even those which belong to the root. We define the coefficients of Y as follows :

$m(d-k)+k

Y: mZY'H (-m(d k)+k)!

l

 

(2.5)

So Ym is the number of these trees with m edges, and we have Y1 = (z) and Y2 =
2a— 1: I:
(h) dihklcjl: )

Lemma 2.2 The egf Y for rooted (d,k)-trees can be expressed in terms of the egf y

for simply rooted trees as follows :

e” — 1):c"

Y = ( k! (2.6)

Proof : From the proof of Lemma 2.1, e” — 1 is the egf for the labeled (d, k)—trees
rooted at an unlabeled, linearly ordered k-subset of an edge (the k-subset may belong
to many edges), with at least one edge. If we label the k vertices of the root and
remove the order on them, we have a rooted (d, k)-tree. The egf of the rooted (d, k)-

trees resulting from the above Operations is gig—)5. Notice that when d = 2 and

14

= 1 (i.e. ordinary trees), we have to use Y = eyx instead of (2.6). It’s because

unlike d 2 3 cases, a single rooted vertex is considered as a rooted tree with no edge
ind=2andk=1. C]

An edge rooted (d, k)-tree has as its root a single edge. Let 2 be the egf for these.

Then the coefficients of z are defined by

 

xm(d-k)+k ( )
z = 2m 2.7
m=l (m(d — k) + It)!
So we have 21 = 1 and 22 = iffzti).

Lemma 2.3 The egf for edge rooted (d,k)-trees can be expressed in terms of the egf
for simply rooted trees as follows :

cu (ilxd
z = ngfl— . (2.8)

Proof : We follow the proof of lemma 1, but use ordered (z) c0pies of the special kind
of (d, k)—trees and match them to all the k-subsets of the ordered d-set. Then we fill
in labels for all d unlabeled vertices and remove the order on them to obtain we have
an edge rooted (d, k)-tree. The egf of the edge rooted (d, k)-tree resulting from the
above Operations is (£43914. C]

We denote the egf for (d, k)-trees by Z and define its coefficients by

°° $m(d—k)+lc
Z m
22 (m(d— k) +k)!

m=l

(2.9)

 

($17.22)
_ _ z _ - '-
ThenZ1—1,Z2——.}———I§J——.

Lemma 2.4 The egf for (d,k)-trees is expressed in terms of Y and 2 as follows .°

2 = Y — ((2) — 1) z. (2.10)

Proof : Consider a (d, k)-tree T. By the inductive definition of (d, h)—trees, there is a

way to construct T by adding edges one by one. Following the order of construction,

15

we can order the edge set of T. By using the order of the edge set, we can construct
a many-to—one mapping from the set of labeled rooted (d, k)-tree obtained from T to
the set of labeled edge rooted (d, k)-trees obtained from T as follows : For a labeled
rooted (d,k)-tree of T, we map it to a labeled edge rooted (d,k)-tree of T whose
rooted edge contains the k-set which form the root of the labeled rooted (d, k)-tree of
T. If the k-set is contained in more than one edge of T, we choose the labeled edge
rooted (d, k)-tree of T whose rooted edge has the highest priority among the edges
which contain the rooted k-set. It’s easy to see that the above construction provides
a many to one mapping. Futhermore, there are exactly (Z) — 1 many labeled rooted
(d, k)-trees of T mapped to every labeled edge rooted (d, k)-tree of T, except the one
which is rooted at the edge of T with highest priority among all the edges of T. For
the only exception here, it is mapped by exactly (I?) rooted (d, k)-trees. Therefore,
we have :
1 = (number of ways to root the (d, k)—tree T)

—((f) — 1)(number of ways to root the (d, k)-tree T at an edge)

01’

Z... = Y... — ((2) —1)z... (2.11)

where m is the number of edges of a (d, k)-tree.

$m(d—k)+h

Multiplying both sides of (2.11) by W

and summing over m _>_ 1, we arrive
the generating function equation (2.10). [:1

From (2.4), (2.6), (2.8) and (2.11), we obtain the following theorm:

Theorem 2.1 The number of (d, k)—trees of order n = m(d — k) + It is

a=n_«9-g. he)

((m (d — k) + mg) (m ((i) _ 1) +1)m-1
mlk! ((d— mm

where

Y... = (2.13)

 

16

_<:><<m (d- k>+k>!> (((Z)—1)m+1)"“2 (2,.)
d.((d—k)!)"’ (Tn—1)!

Proof : Let n = m(d — k) + k and a = x‘H‘. If we write y in terms of a, then from

(2.4), we find
(ey)(:)—lxd—k (eU)(Z)—la
y = (d — k)! = “(372)!- = my)“ (2'15)

(8112(0'1

where ¢(y) = M4), .

 

The coefficients of Y are extracted from (2.6) by the following steps:

[fly = [at] t_e"-._1..)a=.."_

 

n! n! k!
_ n! x" h ell—1
_ (n-lc)! [(n—k)!] k! (2.16)
! ( —lc)! m
= (n—flc)!k! “m: [%l 6” _ 1
_ (m(d-k[+k]! g: y
— mlk! [ml] e _ 1'

On applying Lagrange’s inversion formula to (2.15), we have

[ails = (.——$i‘)y=, (e) a ma)
(m(m- 1) +2)“

((d-kl’)

m d _ m-l
Therefore, Y... =(( (‘1 k):.)3(((d(,(c),))al) +1) . We can obtain (2.14) in a similar

 

way. Note that the formula works for d 2 3 with m 2 1 and d = 2 with m 2 O. For
at 2 3 with m = 0, the number should be 0. D
To obtain Cayley’s Theorem as a corollary, we take d = 2, k = 1 and m = n — 1.

Then Z... is the number of labeled trees of order n, and the formulas in the Theorem

yield
z... = (n — 1)n"‘2 (2.17)
Y... = n"-1 (2.18)
Z... = a”. (2.19)

17

When I: = d — 1, The Theorem provides the formulas for the number of (d — 1)-
dimensional trees found by Beineke and Pippert [BeP69]. In this case m = n — d + 1

and formulas (2.12), (2.13) and (2.14) give

 

z... = (Z) (d ((n — d)(d -1)+ d)"—d_l) (2.20)
Y... 2 (dj 1) (((n — d)(d — l) + d)"-d) (2.21)

z... = (df1)((d -1)(n — (d — 1)) + 1)"—(d-1>-2 = (2)0411 — k) +1)“-2
(2.22)

Note that
7112... = z... (2.23)
provides the preferred formula

2... ___ (g) ((m (d _ 1.) + 1.)!) (((g) _ 1) m +1)"“2 (224)

dlm! ((d —- k)!)m_1
for Z... over (2.12).

Note that Beineke and Pippert found the formula for Z... with k = d — 1 by using
a special case of (2.6) and did not extend the egfs to include our equations (2.8) and

(2.10). We have done this to enable us to enumerate forests in the next section.

2.3 Forests of (d, k)-trees

Let f,(m, d, k) be the number of forests of (d, k)-trees with l components and m edges,
then 11 = m(d -— k) + kl and the egf for forests of (d, k)-trees with 1 components is

Z‘ _ (Y- ((i) -1)Z)l

F" 1!

 

18

__Z(1)('-)(Y)’u‘((i) -1)’Z‘

On extracting the coefficients of this egf, we have the following theorem.

Theorem 2.2 If f.(m, d, k) be the number offorests of (d, k)-trees with 1 components

and m edges, then

" ()-1) ( (d—k)+kl)'

(m d k) :20 C )l(!(_1)— k1)! (MN —z')! ((d -— k)!)m’.iBi

1—

 

where m = 2:21 and

22:61 ("3’1)(-1)"”1‘j(W65) -1) +1) (7" ((2’) -1)
B.- = +1 +j + 1)’"“"‘1 — 10:) (m ((;j) — 1) +1+j)"’"’1) 0 g i <1

l(Z) (m (Cf) - 1) +l)m+1 i=1

Proof: To find f.(m, d, k), we use (2.4), (2.6), (2.8) and Lagrange’s inversion formula

 

to extract coefficients. Here are some steps:

 

 

12—71%: = [as-12:4 "()"""_‘((i)‘ll"‘
= [%]Z§_—.fo()( 1’ ‘1 Y'izi
= 2:0 (DHY ["1 [1—1‘] YHZI
= 3:06 1—n<(z-1'[.1_7](.y;n.) (We )
- Zl=o(:)(;[)).:)((f.(;]. [$.21](ey—1)‘-1(ey)i(i)xk(t—i)+id
— z: o (i) “[3,? {533.112. [(3113,] (a _ 1)’-i(ey)i(i)

If we apply Lagrange’s inversion formula and expand (ey — 1)"‘ when necessary, then
we can continue in a similar way as in the proof of Theorem 2.1 to obtain the formula
of the theorem. E]

The formula in Theorem 2.2 opened the way for us to estimate the average number
of (d, k)-trees in a labeled ((1, k)-forest with large n. The ordinary labeled tree case
of this problem was treated in [M70] and the ordinary unlabeled tree case was solved

by EM. Palmer and A.J. Schewnk in [PaS79].

19

Let us consider the special case d = (b+1)a and k 2 ba where a, b are any natural
numbers not not both equal to 1. Note that when a = 1, we get d-dimensional
HID-hypertrees. We also let 1 2 2 and fix the number of vertices n such that n =
m1(d — k) + k : m(d — k) + kl. Therefore m1 is the number of edges in a (d, k)-tree
with n vertices and m is the number of edges in a (d, k)-forest with n vertices and 1
components. We can write ml in terms of m and then we have m. = m+h where h =
b(l — 1) is an integer greater than 0. Consider the function 5(n) = n!((r(:,f!)((—d1_)g:)):"‘.
Note that E(n) ~ le...,. If we divide f)(m,d, k) by 5(n), we have

fit???) 2 21:06) (l!(kl!))7£('32!))i) ((731%) (($51.13)?) (((:)_1)m1€'l(m,)m.—1)

= leo (f) ((——’1fl31)——1‘)‘k")1 (W) (fit—11);) (((d)_1)m+bg'(m+h)m+h-1)

(2.25)

 

 

 

where B.- is defined in Theorem 2.2.

Continuing to simplfy formula (2.25), we have

(iii???) (((:)—1)"‘+"3‘<m+111+1-1l z

(m+h)(m+h—1)---(m- (1- 1))

x (23:: ("3‘1)(—1)'-1-1—1((1((::) — 1) +1)

x (m((:) -1)+1+1+1)’"“"1—1(:)(m((:) —1)+1+1)’"“”))

/(((:) —1)"‘+"“(m + m+h-1) =

W“ + h/m)(1+ (1 — 1)/m) - - 1 (1 — (1 — 1)/m)

x (23:1 ('-;-1)(—1)1-1-1-1 ((1 ((1) — 1) +1)

x (1 + ((2- +j + 1)/ ((g) — 1)) /m)"“"1 — 1(3) (1 + ((1’ +1)/ ((2’) - 1)) /m)m+l))
/(1+ h/m)’"+"‘1

 

 

20

whenOSi<land
M B, _
((m—0!) (((il—1)m+h-l(m+h)m+h—1) "
W163“ + h/m)(1+ (h —1)/m)...(1_(,_1)/m)
x (1+ (1/ ((1?) — 1)) /m)m-l—1/(1 + h/m)m+h—1

when i = I. If we let n ——) 00, we have W -—>

2:-.. (i) (—""“§?"l"')i (an) (52)“ (1)11”?

(eW—1)'_ ((1((:)—1)+1)eW—1(::))

(1111—11) (711—) “’5 ‘1”. ) (2:-.. (z) (71W) (eI/(111—1)-1)‘-‘"1
((1((::) — 1) +1)e1/<<1>-1> —1(g)))

A little more work on the sum and use the fact that h = b(l— 1) shows that W —>

where
A _( (151-1 _1_ el/((:)"1))
(Z)

.1‘_ el/((:)_1) (d—k)! )1
C = eCW—l — — __ _ .
( 1 (1) ) (1((1) — 1)

If we sum all the W from I = 2 up to 00, we have the following limit:

 

Of

 

and

' o: ,dJC . g ,d,k)
11m.._,oo Z T 61211,)" I ) = 2:2 llInn—mo fl gin) =

2131(1/ (W - 1)) (at-n) ((W — (2.)) (7??) +.1/((:)—1)A)1c1—1

 

21

Since

 

2:2 (‘1—71 “(T70 ) [Cl 1 _ ‘11? 2:2 ((1—11

We have the limit of the sum is

 

“me 2°: 117(1m..=dk)
(1/ (eWB:)1)) ((JWJ _ (3)) (226%) +el/((Z)-1)A) .1. (19% — 1) .

(2.27)
Similarly, if we use (2. 26), we can find the limit of 2&2 M and the limit is:

 

 

1..-... 11.51:“ = 21° 1..-... 1.21: =
(1/ (Jill—1 — 1)) ((Jfl—l _ (3)) (’71???) ”MUD-1)...) 2:2(717 (1.7—r1 )101 1
Since
21:.(..1..)1c:1-—1—12.°:.(.—.-—— ...) a)“ = 1((s+1)e% —1),
therefore
1...... 115111 =
(1) (.(1): -1» ((.GF _ (3)) (7C?) +.11((1)—1).) ,1. ((g + p.11 -1) ,

Notice that f1(m, d, 1:) ~ Z...1 only, therefore the average number of (d, k)-trees in
. . . °3 1 m,d,k °3 1 m,d,k
a (d, k)-forest, when n 18 big, d = (b+1)a and k = ba, 18 W = 22%.
By using (2.27) and (2.28), we find the limit is:

20:. lf1(m,d,k) _
Zl=2fl(m1d1k) —

((1111111))11

((W—1)) [(W—1()] [7.37;]..1/«11-12) .(.a_.) (“9)
(($10.84).

(11—)

We summarize these results in the theorem and corollary below.

 

 

22

Theorem 2.3 When 11 = (b + 1)a and k = ba where a,b are natural numbers, the

average number of (d, k)-trees in a (d, k)-forest is asymptotic to
((5,- + 1) e5 — 1)

(.._.)

Corollary 2.4 The average number of d-dimensional HP-hypertrees in a d-

 

(2.30)

where

dimensional HP-forest is asymptotic to

«...,. ~11
(em-1)

_l__ el/(d-l) 1 d_1
C‘(e"‘1‘ d )(ew—u) '

In particular, the average number of 3—dimensional HP-hyptrees in a 3—dimensional

 

where

HP-forest is 2.0008

Now, let us consider the general case. When d, k and I fixed, we observe that
(d, k)-forest with 1 components does not exists at all natural number n > (d — k) + kl.
When forest with 1 components exists at a particular n, then it doesn’t exist at 71+ 1,
n+2, ..., n+ (d-k) —1 and then it exists at n+(d—k). Also, forest with l+1
components doesn’t exist at n, n + 1, . . . , n + k — 1 and it exists at n + k. From this
observation, we can group the number of components that the forests exist at the
same size of the hypergraph into a single group. A little calculation shows that we

have g “4‘ many groups. Note that the special case we discussed above is the case

“(d-hi)

when 975%,?) = 1. If we pick the smallest number of components within each group

to represent that group and write it as lq, q = 1,2,. . ., m, then I. = q. Now,
we can find the average number of components of (d, k)-forests within each group one

by one.

23

 

For a particular group 1., we define ,8(n, q) = "15,511.2352? -1 where n is a natural
number such that (d, k) — forest with 1,, components exists and n = m1(d — k) + qu.
Consider a forest with l components, m edges and size n that belongs to the same
group. We have n = m(d — k) + kl = m1(d — k) + 1d,, and so m1 = m + h where

h r and r is certain positive integer. With this setup, we can follow in the

_ k
_ ng(d—k,k)

same way as in the special case above and we found that, when n —> oo,

oo .
Zr=00rr=1 hmfl—WO g: —)

(V ( " 1)) ((1 — (1)) (egf) +.1/(<:)—1)A) (fit-1%)). x

3% mm'
00 1 1 _A. (d—k ! —
Zr=00rr=l ( mr+lQ—l)(lq_1)) (((W)TY) ((k!) (e k —l ) )

and

 

 

oo - l
Zr=00rr=l huh-’00 3% —)

(14.111: .. 1)) ((112 _ 3)) (7.11:) ..1/1111—11.) (.,1.—1(,,.,

I:

We 1, 11—111
2:00rrzl (— dik 1 -1 ( “’1" l) (g) ( -1
mam—.3111“ la.-.) «WW 1 1.

where A is defined in the special case and the sums start at r = 1 when q = 1 and at

11 " r
) an) “3‘3““

 

 

r = 0 when q > 1.

With the help of the above formulas, Theorem 2.3 and Theorem 2.2, we get the
Table 2.1.

The average number of trees in a edge rooted (d, k)-forast can also be obtained by

a similar approach.

24

Table 2.1: Average Number of Components in a (d, k)-forest

 

 

 

 

 

 

(d,k) q limit value n=12 n=13
(3,1) 1 3.000602687 Q 1.580972649
2 2.001205156 2.001203732 Z
(3,2) 1 2000838869 1004255875 1005977298

(4,1) 1 4000000964 2 1

2 2.000004686 Z Z

3 3000001874 3 3
(4,2) 1 2.000656280 1.414027545 Z
(4,3) 1 2000007175 1000034210 1000052513

 

 

 

 

 

 

 

2.4 Enumeration of 3—trees

In the first section of this chapter we defined d-trees. Here we will use egfs of various
rooted cases to enumerate 3-trees.

A I-rooted 3-tree has as its root a single unlabeled, non-cutting vertex. Let an be
the number of l-rooted 3-tree with 71 labeled vertices. Then a0 = 1, a1 = 0 and a2 = 1.
Let y1 = 2:0 ani—Z be the egf of l-rooted 3—trees and t(z) be the egf of unrooted

n 71—!

labeled trees. Note that t(:r) = 2:1 nn‘z‘fi. Let T(z, y) = flag—'3! = 2:2 aux—firm
Then T (x, y) is a kind of egf of unrooted labeled trees where the degree of y gives the
number of edges in a tree with order n. Notice that T(a:,y) counts only trees with
order at least 2.

A 2-rooted 3—tree has as its root 2 ordered, unlabeled vertices of an edge and there
is exactly one edge that contains both the root vertices. Let b. be the number of
2-rooted 3-trees with n labeled vertices and let y2 = 2:10 (911% be the egf of 2-rooted
3-trees. Then we have the following lemma.

Lemma 2.5 The egfs yl and y; for l-rooted 3-trees and 2-rooted 3-trees satisfy the

following two equations.

— we!" (2.32)

y2 = zey‘ezy’ = :1:e"‘+2"2 (2.33)

Proof : Consider the case of l-rooted 3—trees. If we take all the edges incident with the
root vertex together and remove from them the root vertex, we get an edge set of an
ordinary unrooted labeled tree. Therefore, we can construct a l-rooted 3-tree by first
adding an ordinary labeled tree to the root vertex (i.e. add the root vertex to all the
edges of an ordinary tree), and then we add other l-rooted 3-trees, one by one to the
vertices of the tree (we can order the vertices and edges of the tree by using the labels
of the vertices). Then we add 2-rooted 3—trees to the edges of the tree one by one (the
edges and their two end vertices are ordered). The end result is a l-rooted 3—tree.
This implies that, to get the egf yl, we just have to subsitute are"1 to a: and e” to y
into the egf T(:c, y). Therefore, we have y1 = T(:re”‘,e”’) = 513%) — me“. For 2-
rooted 3-trees, we can construct them by first starting with a special hyperedge. This
edge has one labeled vertex and two unlabeled vertices. The two unlabeled vertices
are ordered. The order of the unlabeled vertices can be used to induce an order to the
sides of the edge, in particular, the two sides with the labeled vertex. Now we add
2-rooted 3-trees to the two sides with the labeled vertex, one by one. Then we add
l-rooted 3—trees to the labeled verex, identify the roots with the labeled vertex. The
end result is a 2-rooted 3—tree. This process shows us that the egf 3’2 can be obtained
by multiplying :1: with e'1'l and em. Therefore, we have y2 = :remezl’2 = “111412112. B
Let F be the egf of 3—tress rooted at a vertex. Then we can write the egf F =

2:0 anal, in terms of y, and y2,
Lemma 2.6 Let F be the egf of rooted 3-trees, then we have
F = $6“ (2.34)

Proof : If we arrange many l-rooted trees together and identify the roots as a single

26

root vertex, the egf of this structure is ey‘. Now we fill the unlabeled root vertex with
a label. We get a rooted 3-tree. It’s egf is reel“. [:1
Now, we solve the equations (2.32), (2.33) and extract the coefficients of (2.32),

(2.33) and (2.34), we have the following formulas:

 

d" 311 __ n n ..
( w ).=o _ Z (T)A,,,B,,,. no. (2.30)

r=0

 

 

(1111112) =nD. (2.36)
1:" :1:=0
11111?
= ,, 2.
(11411).-. c 1 37)

where the AW, BM, 07, and D" are given below.

First we have

n-r! En? ' kj
A — Z(W(— 1) z:i=1kil‘lj= _l,jk¢0(%g) ) n>r20 (238)

1 r=n.

The summation is over all partitions (k1, k2, . . . , kn-..) of n — r such that each 1:,- for
i = 1, 2, . . . , n — r is a nonnegative integer and 2;:{2'1121 = n - r.

Second comes

2 (Hf=1r (1'!) 1111163131 19‘2“ {=1W)2H;=1,k,¢o(bj)kj) n 2 r > 0
0 r = 0

with (2.39)

1(2 (341317.114414-141- “Qt—m) )) 121>1

1 j=1.

Bn,r =

The summation in BM is over all partitions (k1, k2, . . . , hr) of r such that each k.- for

i = 1,2,. ,r is a nonnegative integer and 2,1 _, ik,— —- r. The summation in b is over

27

Table 2.2: Number of 1-rooted, 2-rooted, rooted 3—trees and unrooted 3-trees.
n 1-rooted 3—trees 2—rooted 3—trees rooted 3-trees unrooted 3-trees

 

 

1 0 1 1 1
2 1 4 0 0
3 6 39 3 1
4 82 584 24 6
5 1515 11985 425 85
6 36951 312522 9450 1575
7 1112083 9898168 269892 38556

all partitions (h1,h2,...,hj..1) ofj — 1 such that each h,- for i = 1,2,...,j — 1 is a

j-l

nonnegative integer and 2,.:1 ihg = j — 1.

Next we have

. k1
(n—l)! n—l (fly 1
2: (11:23 (I!) ”:1! Hj=1,kj¢0 ( 1) ) n > 1

C" = (2.40)
1 n = 1.
The summation is over all partitions (161,192, . . . ,k,,_1) of n — 1 such that each It,- for
i = 1,2,. . . ,n — 1 is a nonnegative integer and 22:11 iki = n — 1.
And finally
deer—11144)) 1....

1 n=1.

The summation is over all partitions (k1, k2, . . . , kn_1) of n — r such that each It,- for

n—l

i=12ki= n— 1.

i = 1,2,. . . ,n — 1 is a nonnegative integers and 2
We used these formulas to calculate the entries in Table 2.2.
To extend this approach to enumerate 4-tress would clearly require substantially

more effort.

28

CHAPTER 3

Threshold problems for random

hypergraphs

There are several important problems that have been solved for graphs but not for
hypergraphs. Two of these ask for probabilistic thresholds for monotone preperties
of random hypergraphs and both involve hypertrees.

The first seeks an approximation to the number of edges in a random hypergraph
sufficient to insure that, with high probability, it has a spanning hypertree. We
will focus in the simplest unsolved cases, which deal with spanning (3, 1)-trees and
(3, 2)-trees. We provide upper and lower bounds for these approximations.

The second problem concerns maximum matchings in hypergraphs. We want
to estimate the number of edges in a random hypergraph sufficient to insure that,
with high probability, it has a spanning set of independent edges. As above, the
simplest case involves 3-uniform hypergraphs. We have also determined bounds for
this threshold. We have two methods for determining upper bounds. First we used an
algorithmic approach. But a better bound can be found following Krivelevich [Kr97]
and this makes use of a special class of hypertrees.

There is another asymptotic problem for hypergraphs that should be mentioned

29

here. The Turan number, t3(n, 4), is the maximum number of edges in a 3-uniform
hypergraph of order n that has no complete hypergraph of order 4. ’I‘uran conjectured

that
t (n 4) 5 n (3 1)
3 1 9 3 ' '
A simple construction shows that the right side of 3.1 is a lower bound for t3(n, 4).

Professor Erd6s liked this problem so much that he posted a bounty of $1000 for its

solution. We have no progress to report on this question.

3. 1 Random hypergraphs

We define H (n, d, p) as the probability space of all labelled d-uniform hypergraphs
with vertex set V = {1,...,n}. A hypergraph H = (V, E) E H(n,d,p) has prob-
ability P(H) = p'El(1 — p) (3)—IEI. We called p the edge probability and, of course,
0 < p < 1. Thus each subset {111,112, . . . , ya} 6 (E) is chosen independently to be an
edge of a random hypergraph H with probability p.

Suppose Q g H (n, d, p) is a hypergraph pr0perty. We say that a random hyper—
graph H E H (n, d,p) has Q with high probability (whp) or almost surely (as) if the
probability of Q tends to 1 as it approaches infinity.

It is well-known that if Q is a monotone prOperty, then there exists a threshold

function pt such that
Ofiflao
P (Q) -> p‘
1 IL
1 if 1111 —+ 00

Note that the limits indicted by the arrows are all taken as it approaches infinity.

We illustrate with a threshold for connectedness in random d—uniform hypergraphs
found in [PaR85]. Recall from section 1.1 that a hypergraph H is connected if there is

a u — u path between any two vertices u and 11. Clearly connectedness is a monotone

property. Therefore a threshold function exists. It was determined in [PaR85] that

30

pt = (—:§—_ll—!logn is a threshold for connectness. In fact, the following much stronger

result is proved in [PaR85]. Let C g H (n, d, p) be the pr0perty of connectedness.
Theorem 3.1 If the edge probability is p = %§}l—!(lnn + z), where :1: is fixed, then
P(C) -) e“_3 (3.2)

For definitions and random graph methods not explained here, the reader can

consult an array of books, such as [B085], [Pa85], [A892] and [JaLR90].

3.2 Spanning trees in random hypergraphs

Suppose Q E H (n, d, p) is the hypergraph property that H 6 Q has a spanning
(d, k)-tree. Then clearly Q is monotone and so there is a threshold function. In this
section, we will establish upper and lower bounds for these thresholds when d = 3.

First observe that it follows from theorem 3.1 above that if the edge probability
1s

2!
p = -n—2(lnn - can), where 111,, —) +00, (33)

then P(Q) —> 0. That is, almost surely the random hypergraph is not connected and
hence has no spanning (3,1)-tree, (3, 2)-tree or mixed 3—tree. Hence "3'; 1n n is a lower
bound on the spanning tree threshold for all of these types of trees.

Now we focus on the upper bound for spanning (3,1)-trees. Our approach is
algorithmic. We assume that 19 >> 3% and so whp there are many edges. Here is how
the algorithm works. We pick an edge, say {u, u, w}, at random and form a (3,1)-tree
T to start with. Then we try to find another edge {u, 2:, y} where {2.3 y}fl{u, u, w} = 0.
We extend the (3,1)-tree T with the new edge and get a new, bigger (3, 1)-tree T. We
repeat this step until this (3,1)-tree reaches a size that depends on 0 < c < 1. Then
we add new edges made from a pair of the remaining vertices and any vertex of the

(3, 1)-tree under construction. Here is a more concrete description of the algorithm.

31

Greedy Algorithm for a Spanning (3,1)-tree

 

INPUT a uniform hypergraph H and an edge {u, v, w} of H
Choose 0 < c < 1
T +—— {{u,v,w}}
S +—— {w}
WHILE |V(T)| < e|V(H)| DO
31 «- V(H) — V(T)
Pick w E S
REPEAT
Pick an E 51
$2 (— SI - {51:1}
REPEAT
pick 2:2 6 32
52 (~— 32 — {2:2}
UNTIL {w,:1:1,:1:2} E E(H) OR 32 = 0
IF {w,:1:1,:c2} E E(H) THEN T <—— T U{{w,$1,a:2}}
S (— {1:1}
51 +— 51 — {2:1}
UNTIL {w,:1:1,:z:2} E E(H)
R (— V(H) - V(T)
WHILE R 91 0 DO
Pick yl E R
R1 (— R — {yl}
T1 4—— V(T)
REPEAT
PiCk .712 E R1

32

R1 +— R1 " {312}
pick ‘1) 6 T1
T1 (—— T1 — {v}
UNTIL {y1,y2,v} E E(H)
T *— TU {ll/1,312,111}
R (_— V(H) — V(T)
OUTPUT T

This algorithm terminates and outputs a spanning (3, 1)-tree T of the random
hypergraph H if it can find one. Notice that after we expended the first input edge
to a (3,1)-tree of size e|V(H)| in the first half of the algorithm, the input hypergraph
H loses randomness and therefore the probability of successful adding edges in the
second half of the algorithm is not easy to compute. To overcome the difficulty and
analyze the algorithm, we need to use a trick that is well-known to probabilists. We
will use two colors, blue and green, for the edges of our random graphs. Thus we
express the edge probability p as p = p1 + p2 - plpg, where p1 is the probability of
having a blue hyperedge between three vertices of H and p,» is the probability of having
a green hyperedge. In fact, this setup enables us to decompose the 3-uniform random
hypergraph H into the union of two 3-uniform random hypergraphs H1 and H2, where
H1 6 H (n, 3,p1) has all the random blue hyperedges of H and H2 6 H (n,3,p2) has
all the random green hyperedges. If we use only H1 in the first half and use only H2
in the second half of our algorithm, we can find a spanning (3,1)-tree of H without
losing randomness.

Let H E H(n,p, 3) with p = p1 +172 —p1p2. Let H, E H(n,3,p1) be the random
blue hypergraph, H2 6 H (n, 3, p2) be the random green hypergraph where H is the

union of H1 and H2. Let r = €|V(H)l, r odd. In many of the proofs we deal with

33

quantites such as e|V(H)| where e > 0 is very small but e|V(H)| is very large. Rather
than using the round-off notation, we treat c|V(H)| as an integer itself. The validity
of the proofs still holds. Let T = {{u, u, w}} C E(Hl), that is, T contains the blue
edge we used to start the algorithm.

The probability of adding a new blue edge {w, 1:1, 1:2} to T is
1 — (1 — 110033). (3.4)

Next we search for another blue edge {115,111,312} with {y1,y2} n {u, v,w,a:1,:132} = 0.

The probability for success in our second attempt is
1 — (1 — p)("3‘). (3.5)

We repeat this step until |V(T)| = r. The probability of successfully constructing a

blue (3,1)-tree T of odd order r in this way is
1:31

2 r—3

n (1- 11 4.111111) > (1— 114111-11) 1 . 13.11

i=1

 

Note that the lower bound above does not approach 1 as n —) 00 when r = n.
So we terminate this part of the algorithm for r = en, with e to be determined later.
And now we continue to extend our tree T in a slightly different way.

In the second half of the algorithm, we switch to H2. First we pick a vertex 21
in R = V(Q) — V(T). The probability that 2; belongs to an green edge of the form
{21,22,23} with 22 E V(T) and 23 E R is 1 — (1 — p2)'(""‘1). The probability that

this step can be repeated until the tree spans all vertices is

 

n-r—2
fl (1 — (1 — p1)"+2‘)<"-1-<11’+1>>) > (1 — (1 — p1)<"-'1’>2)“. (3.7)
5:0
From 3.6 we have F3
(1 — 11— p1)<"“:"1)) 1
r-3

 

> (1 — e-11(""5"’)) ’
> 1 — (L33) (e-v1("“5"’)).

(3.8)

34

In order for

 

1- (’33) (641101-1140) _11 (3.9)

“—(7—3) _ n—r
when n ——> 00, we must have 336‘“ 2 l ——> 0. Let 'g—le p‘( 2 ) = 1+. where
210(m) 2111 r—3) 1
“’11 —* 00- NOW P1 = 7:17.27):- 3 1n—1r-2» N 0&1“)-

110111 3.7 we have

n—r

(1_ (1 -..111-111) 1
> (1 — e-P12<11-2>)"—3" (3.10)

> 1— 111—1) 1e-11111-11).

In order for

 

1- (n g r) (ea-1112014)) —> 1 (3.11)

when n —) 00, we need ("—2—”) e‘P’(2"‘4) —-> 0. If we let (9ft) e‘mlzn‘” = 51; where

n (n—r)wn
1.11,, —) 00, then p2 = l—gfifi—l 2 fiffi ~ 0 ("’7“). Now, if we combine all the blue
edges and green edges we collected, we get a spanning (3,1)-tree of H and we have

p = 191 + p2 — plpg ~ 0 (’33). This result is summarized in the following theorem.

"1

Theorem 3.2 If the edge probability of a random hypergraph H in H (n, 3, p) is p Z
G + c) 19:5, then whp H has a spanning (3, 1)-tree. Hence the threshold for a spanning
(3,1)-tree is 0 (11?).

By modifying the algorithm above, we obtain an upper bound for the Spanning
(3,2)-tree threshold. Let H 6 H (n, 3,p) be the 3-uniform random hypergraph. We
start with an edge in H, then we extend it as a (3, 2)-tree by adding a new edge with
exactly one new vertex 2:1 outside the (3, 2)-tree. Suppose the edge we just added to
the (3, 2)-tree is {u,v,:1:1}, then what we do next is to find another edge of the form
{u, $1,132} or {11,31,272} where 312 is a new vertex outside our current (3, 2)-tree. We
keep on expanding our (3, 2)-tree till our hypertree’s size reaches r = e|V(H)|, where

0 < e < 1. Then we expand our (3, 2)-tree in a different way. We add the remaining

35

vertices, one by one, to the hypertree by finding an edge with the choosen vertex and
two vertices from an edge of our current (3, 2)-tree. If this process terminates, we get
a spanning (3, 2)—tree of H. Slightly modify this, we have the following algorithm.

Greedy Algorithm for a Spanning (3, 2)-tree

 

INPUT a uniform hypergraph H and an edge {u,v,w} of H
Choose 0 < c < 1
T +— {{u,v, w}}
T1 +— {u,v}
S +— {w}
WHILE |V(T)| < e|V(H)| DO

51(— V(H) - V(T)

Pick the vertex w E S

Pick a vertex u 6 T1

Pick the remaining vertex v 6 T1 — {u}

REPEAT

Pick 2:1 6 SI
51 (— 31 — {11:1}
UNTIL {w,u,:1:1} E E(H) OR {w,u,:c1} E E(H)
IF {w,u,:c1} E E(H) THEN T (—— TU {{w,u,:c1}}
T1 (— {w,u}
ELSE IF {w,u,:c1} E E(H) THEN T +— T U {{w,u,a:1}}
T1 <—— {w,u}
S (~— {331}

R 1— V(H) — V(T)
WHILE R 7e 0 DO

Pick yl E R

36

T1 (_— T
REPEAT Pick {11,11,111} 6 T1
T1 (— T1 -{{U,'U,1.U}}

UNTIL {u,v,y1} E E(H) OR {u,w,y1} E E(H) OR {v,w,y1} E E(H)
IF {u,v,y1} E E(H) THEN T (— TU {{u,u,y1}}

ELSE IF {u,w,y1} E E(H) THEN T +— TU {{u,w,y1}}

ELSE IF {1), w,y1} E E(H) THEN T +— TU {{v,w,y1}}

R <—— V(H) — V(T)
OUTPUT T

We follow the same trick to analyze the algorithm and decompose H 6 H (n, 3, p)

into the union of two random hypergraphs H1 6 H (n, 3, p1) and H2 6 H (n,3, p2).

Where p = p1 + p2 — 171192. H1 is the blue random hypergraph and H2 is the green

random hypergraph.

The probability of success in the first part with blue edge probability p1 is

(1 - (1 - p1)3(""3)) II

1:: (1 " (1 — Film—(2%»)

2 11:13 (1 _ (1 _ p1)2(n—(2+i)))

2 1_ (T __ 3)(1_ p1)2(n-—-r-+-1)

r-3
21- W-

r—3 _ _L
We need W - 1.1,.

——-) 0 and we find that this occurs when p1 ~ 0(13—n" .

Therefore, if p1 ~ 0(1911), whp the first part will succeed.

I"

37

The probability for second part to succeed with green edge probability p2 is

[In-T: (1 __ (1 _ p2)(2(r+i—l)—3))
.2 111:: (1— 11 — paw-3’)
> (1 — (1 — p2)(2r_3))(n-r)
2 (1 — (means—'1
2 1 — (n — r)e"’2(2"3).

L

Now we need (71 — r)e"”(2"3l -—) 0. As before, we let (n — r)e’m(2"'3) = 1.1,.

where 112,, ——) 00 and solve for p2. We find p2 ~ 0 (g—n"). Therefore, if p2 ~ 0 (92-59),
whp the second part succeeds.
Since H E H (n, 3,p) is the union of the blue random hypergraph and green

random hypergraph with p 2 p1 + p2 ~ 0 (13%"), we have the following theorem.

Theorem 3.3 If the edge probability of a random hypergraph H in H (n, 3, p) is p _>_
(é + e) l—"—"— then whp H has a spanning (3, 2)-tree. Hence the threshold for a spanning

n ’

(3, 2)-tree is 0 (9%).

Since a (3, 2)-spanning tree is also a spanning mixed 3-tree, the upper bound of

the threshold for the former also serves as a bound for the latter.

Theorem 3.4 If the edge probability of a random hypergraph H in H (n, 3, p) is p Z
G +6 ‘33, then whp H has a spanning mixed 3-tree. Hence the threshold for a

spanning mixed 3-tree is 0 ("‘7”).

Our approach would also work on (d, k)-trees, d 2 4, but much more effort would
be required. Furthermore, we would still have only crude uppper and lower bounds

for the threshold.

38

3.3 Maximum matchings in hypergraphs

A subgraph of a hypergraph which is regular of degree 1 is called a matching. A
complete matching is a matching that spans all vertices. We also call a complete
matching a I-factor. Having a 1-factor is a monotone prOperty. Erdéis and Rényi
established the corresponding random graph threshold [ErR66]. Perhaps it is not a
surprise that this threshold coincides with the event that the minimum degree is at
least 1, i.e. 6 2 1. For all even n let F. g H (n, 2,p) be the set of graphs of order n

with a 1-factor. Next define the edge probability:
pn = lnn+c,,. (3.12)

Then, if c,l —-) —00, the second moment method shows that almost surely there
are vertices of degree 0, i.e. P(6 _>_ 1) ——-+ 0. But P(Fn) _<_ P(J 2 1), hence
also P(Fn) ——+ 0. So almost surely a random graph does not have a l-factor when

c,1 ——+ -—oo. So much for the trivial portion of the next theorem.

Theorem 3.5 (Erdfis and Rényi) With the edge probability defined by
pa = lnn + cu, the probability that the random graph in H (n, 2, p) has a I-factor has

the same limiting value as P(6 Z 1), namely:

0 if c” -+ —00
P052 1)—’ e""-c ifcn—-)c

1 if c,, -2 +00
The hard part of the proof requires serious graph theory, namely Tutte’s famous
l-factor theorem [T1147], which characterizes graphs with complete matchings. Paul
Catlin used to prove Tutte’s theorem using Hall’s matching theorem, so perhaps the
latter is the basis for matching theorems in graphs. At any rate, graph theory is
availiable when called for in the proof of Theorem 3.5 or for proving strengthened

versions involving hitting times [8085].

39

Now an interesting thing happens when this problem is generalized to random
3-uniform hypergraphs in H (n, 3,p). The new problem is far more difficult! This
phenomennon often happens when moving from graphs to hypergraphs. For example,
recall that finding a maximum matching in a graph can be done in polynomial time,
whereas the corresponding problem for 3—uniform hypergraphs is in NP [GaJ 79].

Let us consider the matching problem in terms of uniform random hypergraphs.
Let Q" g H (n, 3,p). A complete matching M of H 6 Q. is a collection of isolated

edges of H that span all n vertices of H. An easy calculation shows that if
pn2 = 21nn + to”, can —2 +00, (3.13)

then almost surely every vertex belongs to at least one edge. This provides a lower
bound for the threshold for a complete matching.

Schmidt and Shamir [ScS83] found an upper bound for this threshold (for r-
uniform hypergraphs) with an insightful application of the second moment method.
On translating from their probability model to ours and taking r = 3 we found that
if

pnit = wn —) oo (3.14)
then almost all 3-uniform hypergraphs have a complete matching.

Erdfis was preaching about this problem as early as 1985. Evidently it originated
with Schmidt and Shamir who passed it along to Uncle Paul.

There are other versions of it but they all lead only to upper and lower bounds
for the threshold. The root of the problem seems to be the absence of a suitable
description or characterization of factorizations in triangles or tripartite matchings.

There is another important, relevant result that must be mentioned. It shows that
a large matching can still be found when the edge probability is slightly smaller than
that of (3.14). Using a closely related probability model for r-uniform hypergraphs, de

la Vega [Ve82] found that a necessary and sufficient condition for a random hypergraph

40

to have a matching that spans all but o(n) vertices is

12111-1 = 1.1., —> oo. (3.15)

The proof of the necessity is a straightforward argument using Chebyshev’s in—
equality. But the sufficiency makes nice use of Markov chains to show that a greedy
algorithm will produce a big matching if given enough edges. Note that the edge
probability in (3.15) is indeed smaller than that of (3.14)

There is a simple way to get a upperbound of the threshold. Although the up-
perbound is not as good as the above upperbounds, this method is easy to follow
and it relates the problem to the threshold of complete matching of random bipartite
graphs. Here is how we construct the complete matching. Given an order n 3-uniform
random hypergraph H with edge probability p. We divide the vertex set V(H) into 3
equal size vertex set V1, V2 and V2,. Therefore, we have |V1| = |V2| = |V3| = g. Next,
we arbitrary pair up vertices in V1 with vertices in V2. Now, we have a set of vertex
pairs. Let us call this set V}. Note that |V3| = |VI1| = g. Ifwe treat the elements in V.
as vertices, then we can construct a new random bipartite graph G with vertex sets
V3 and V4 and edge probability p. An edge in G that joins a vertex {u, v} 6 V4 and
a vertex w 6 V3 can be viewed as an edge {u, v,w} in H. Therefore the probability
that G has a complete matching is an upperbound of the probability that H has
a complete matching. It’s already known that the threshold of complete matching
in random bipartite graph is of o (1%) (See [Bo85]). Therefore, we concludes that
the threshold of complete matching in 3—uniform hypergraph is bounded above by

9:7“ + 111,, where w” -—1 00. We have the following theorem.

Theorem 3.6 A 3-uniform hypergraph H E H (n,3, 13:7") whp contains a complete

matching if 3 divides n.

In his paper [Kr97], Michael Krivelevich introduced a new random graph algorithm to

find a new and improved upper bound for the threshold of a triangle factor in a random

41

graph. We find that this new algorithm for random graphs can be modified and be
used to improve the upper bound in theorem 3.6. In the following sections, we shall
provide the modified version of his algorithm and use it to find a better upper bound
of the threshold of complete matching in 3-uniform random hypergraphs. Eventually,

the algorithm leads to the following theorem.

Theorem 3.7 A 3—unif0rm random hypergraph H E H (n, 3, 57867n’g) whp con-

tains a complete matching, assuming 3 divides n.

In order to describe our random hypergraph algorithm, we need some basic hyper-
graph structures. These hypergraph structures play the central role in constructing

a complete matching of a random 3—uniform hypergraph.

3.3.1 Hypergraph Ho and Ho-hypertree

The hypergraph Ho has 4 vertices v0, v1,v2,v3 and 2 edges (v0, v1, v2) and (v1,v2, v3).
The vertices v0, v3 are called removable, while the vertices v1, v2 are called the kernel
of Ho.

You can see here that the hypergraph H0 is not a matching over it’s vertices.
However, if we remove any one of the removable vertices, we get an edge (complete
matching over the three vertices). A hypergraph Ho can be extended naturally to
a tree like structure together with a set of vertices. We call this tree like structure
Ho-hypertree and the set of vertices set of removable vertices. The following is the

recursive definition of Ho-hypertrees and its set of removable vertices:

42

(1) A hypergraph H0 is an HO-hypertree with the set of removable vertices
R = {v0, v3};

(2) If T = (V, E) is an Ho-hypertree with the set of removable vertices R and
H is a copy of Ho with the set of removable vertices {110, u3} and kernel
{u1,u2} so that V(H) flV(T) = V(H) OR = {uo}, then the graph
T’ = (V’,E’), with V’ = V(T)UV(H) and E’ = E(T)UE(H), is an
Ho-hypertree with the set of removable vertices R’ = R(T) U{u3};

(3) Every Ho-hypertree can be obtained from hypergraph Ho by applying (2).

Notice that an Ho-hypertree has the following properties.

Proposition 3.8 If T = (V, E) is an Ho-hypertree with its set of removable vertices
R, we have

(1) |V(T)| "=" 1 (mod 3).

12) 11112 M

(3) For every v E R, the hypergraph T — {v} contains a complete matching.

Proof : We prove the above pr0perties by induction. Let T be an Ho—hypertree and
m be the number of Ho hypergraphs in T. When m = 1, T is an Ho hypergraph.
So |V(T)| = 4, |R| = 2 and T satisfies the three pr0perties. Suppose for any T with
m = k, k 2 1 satisfies the above properties. For any T with m = k + 1, T is obtained
by identifing a removable vertex of a new Ho hypergraph H1 as one of the removable
vertices of an Ho-hypertree T1 with m = 1:. Therefore |V(T)| = |V(T1)| + 3 and
|R(T)| = [R(T1)| + 1. Since T1 satisfies prOperties (1) and (2), therefore |V(T)| E
1 (mod 3) and |R(T)| Z 111,111 + 1 Z Mféllfl 2 [$111. Suppose 110 is the removable
vertex of H1 that is identified as one of the removable vertices of T1. Let v E R(T).
If v 6 R(Tl), then T — {v} contains a matching that covers T1. If that matching
contains v0, than H1 - v0 is an hyperedge that covers all the vertices of H1 other than

v0 and is independent of the matching of T1. So we found a complete matching of

43

T — {v}. If the matching of T1 in T — {v} does not contain v0, then u = v0 and we
add the hyperedge H1 — 110 to the matching to get a complete matching of T — {v}. If
v ¢ R(Tl), then the hyperedge H1 — {v} and a matching in T1 -— {on} form a complete
matching of T — {v}. Therefore, T satisfies all three pr0perties. By induction, we
proved pr0position 3.8. E]

Like hypergraph H0, if we take away a removable a vertex from a Ho-hypertree,

the resultant subgraph has a complete matching.

3.3.2 A matching that covers all vertices

As a base to construct a proof for Theorem 3.7, the following pr0position guarantees

us to have a matching to start with, provided that the edge probability is big enough.

Proposition 3.9 Whp every set of at least n"95 vertices of a random 3—uniform
hypergraph H E H (n, 3, p), where p = Cn'i for any absolute constant C > 0, contains

an edge.

Proof: Given a subset V0 of the vertex set V(H) with size [Vol = n0'95. The

Probability that the subgraph of H spanned by V0 contains no edge, is
”1.3 l.
P [G has no edge] = (1 — p)(”;°|) < e'poll’l’l) < {£30202 = e_e(0 3’ a) = e_e(" 35).
(3.16)

Therefore, the probability of the existance of a size n0'95 vertex set that contains no

edge is bounded above by

”0.95

( n )P[G has no edge] 5 2"e"e("l'35) = 0(1). (3.17)

9

Hence, whp every subgraph of H with size no' 5 contains an edge. [:1

Corollary 3.10 For any constant C > 0, a random 3-uniform hypergraph H e
H ("131?) With P = 071’s} whp contains a matching, covering all but at most n"95

vertices.

44

Proof: The matching can be constructed by picking edges one by one from sub-
graphs of H with size n0'95. We can continue this process till we have less than n”5
not covered by the picked edges. D

After we find a matching to start with, our algorithm tries to find a Ho-forest.

This forest can be used to expand the size of our matching. The follwing proposition

and lemmas show us the forest exists.

Proposition 3.11 Let p0 = 77n‘g. Then whp for every triple of disjoint subsets
U’, U”, W of the vertex set of a random hypergraph H E H (n, (1, p0), satisfying IU'I Z
%,|U”| 2 %, |W| 2 g, there exists in H a copy of the hypergraph Ho, having it’s

kernel vertices in W, one of its removable vertices in U’ and the other one in U”.

Proof: Given U’, U” and W satisfy the above conditions. WLOG, we may assume

that |U’] = 1%, |U”| = g and [W] = ’31. The probability that no such H0 exist is

' [WI 7: n
P[no such H0] = (1 — p2)lU ”mm 2 ) < e‘fidglpz < 6‘3". (3.18)

Hence the probability that there exists U’, U” and W with no such kind of H0 is
bounded above by

(11711) (15111) (lg/OHM 3“" H11 3 (2")311‘" = 11(1)- 1319)

Therefore whp every triple U’, U”, W has a copy of Ho with it’s kernel vertices in
W, one removable vertices in U’ and the other one in U”. D

Note that the constant 77 guarantees us that (3.18) holds.

Lemma 3.1 If p0 = 77n‘i, then for every integer k, satifying 4 S k S and

on:

k E 1 (mod 3), a random hypergraph H E H (n,3, p0) whp contains [5%] vertex

disjoint copies of Ho-hypertrees, each having I: vertices.

Proof. Let p0 = 77n"%, k fixed with 4 S k g g and k E 1 (mod 3). Suppose we

already have t many Ho-hypertrees of size k where 0 g t < %. It’s sufficient for us to

45

find one Ho-hypertree of size I: from the remaining vertices. Consider the following
algorithm. At step i, it generates a family of Ho-trees ‘3'.— = {T1, . . . ,Tm} where T1,
1 g l S m, are vertex disjoint Ho—hypertrees. Associated with each member T1 of “T,-
is a vertex subset U (T1) Q V(Tz). Let Vo be the set of vertices of the t already found
Ho-hypertrees. Let V1 = V(H) — V}; be the set of the remaining vertices.
Algorithm to find an Ho-hypertree
INPUT V1 and any % vertices {v1, . . .,v%} from V,
NF-{UILISlS-E
V1— V1 —-{v1,...,v%}
‘3’, +— {T1,...,T%}
1111:11— {11}, 1513 1,-1
i +— 1
WHILE NOT EXISTS T; E (T.- with [T1] = 11: DO
Find G = {uo, u1,u2,u3}, a copy of Hg with no (one of the removable vertex)
in U’ = UT67,U (T), the other removable vertex 113 in an arbitrary subset U”
of V1 - UTEyiV(T) of size % and {u1, ug} C V1 — UT67,V(T) U U”
T,- (— T, U G and U(TJ-) +— U(T,-) U {uo,u3} where T,- 6 '1'; such that
110 E U (T1)
IF I Urey, V(T)] > g THEN ‘J’; <—— 2”, — {Ti} where T} is of minimum size in ‘3',
‘J’ ,-+1 +— ‘3'.-
i = i + 1
OUTPUT T; where |T1| = k

Notice that the average size of the Ho-trees increases when i increase. Within
the WHILE 100p, the size of U’ is at least 135 because of pr0position 3.8 and at any

time I UTe‘T.- V(Tll 2 '3 A1801 “/1 - Oren-V(T) U U," 2 § because I Uretr. V(Tll

46

is always being kept no more than g by the IF statement. Therefore, all conditions
of proposition 3.11 are satisfied and so whp, this algorithm increases the size of a
Ho-hypertree in the family (7,. Each time, the increment of the size is 3. Therefore,
we cannot miss the size I: and the WHILE 100p terminates within finite number of
iteration and output a desire Ho-hypertree. C)

With the help of above pr0positions and lemmas, we are able to prove the following

lemma. This lemma leads to Theorem 3.7.

g

Lemma 3.2 Define sequences {pfiffiio and {dfio by p0 = 77n’g, p; = 130+(fé)2 191-1—
_3_

(921201914 forl 2 1; and e; = 0.95 — 0.05l forl _>_ 0. Then for every integerl

satisfying 0 S l S 18, a random hypergraph H E H (n, 3,121) whp contains a family of

vertex disjoint hyperedges covering all but at most n" vertices.

Proof. We are going to prove the lemma by induction on I. For the base I = 0,
we have 6; = 0.95 and the lemma is true by corollary 3.10. Suppose it’s true up to
l— 1 where l _>_ 1. Note that 1 — p; = (1 - po)(1 — (§)%p;_1. This allows us to treat
the random hypergraph H as a union of two random hypergraphs H1 6 H (n, 3,120)
and H2 6 H(n, 3, (§)%p1_1). Also, p; = 9(n‘g) for every 1 S l 5 18. Consider
the hypergraph H1. Let m1 = [n‘l-IJ and 1712 be the smallest integer satisfying
mg 2 2ml + n“ and m1 + 7712 E 0 (mod 3). Rather than using the round-off notation,
we use m1 = n‘H, m2 = 2n“"1 + n“ . The validity of the proof still holds. Now we let
I: be the largest integer such that kmg g g and k E 1 (mod 3). Since k ~ i;—;-i, all
the conditions of lemma 3.1 are satisfied. According to lemma 3.1 H1 whp contains
[g] 2 m2 vertex disjoint Ho-hypertrees, each having 1: vertices. We pick only m2 of
these subgraphs and denote this family by To = {T1, . . . , Tm}. Let V0 = Ufil (Tj)
be the set of vertices of ‘J'o’s members and V1 = V -— V0 be the set of vertices not

covered by the Ho-hypertrees. Since IVOI = [£64], we have |V1| 2 £153.

47

Now we shift our attention to H2. Consider the subgraph of H2 that is spanned by
the vertex set V1. This subgraph has size at least 5?" and edge probability (g) % p;_1.
Therefore, this subgraph satisfies the conditons of this lemma (lemma 3.2). By the
induction hypothesis, this subgraph whp contains a matching that covers all but at
most |Vll“-l < m1 vertices. Let us pick just enough edges from the matching to
cover exactly m1 vertices of V1 and call this edge set 3'0. It can be done because
km 5 m2 (mod 3) (as k E 1 (mod 3)) and so m1 +km2 E m1+m2 E 0 (mod 3).
We denote the set of vertices of V1, not yet covered by 9'0, by W = {121, . . . ,vml}.

Now, we want to find edges in H2 that has one vertex in W, one vertex in the
removable vertex set of an Ho-hypertree in ‘3' and the last vertex in the removable
vertex set of another Ho-hypertree in 0'. If we can find, for each vertex in W, an
edge like that and the Ho-hypertrees involved are different for each edge, then we
can expand the covering 30 with edges from H1 and H2. Therefore we define the
following process. At the beginning of step i, where l S i _<_ m1, we have a subfamily
‘J',-_1 g 70, |‘J',-_1| = mg — 2(i — 1), and a family of edges 35-1 2 9’0. We try to find an
edge {v,,u1,u2}, where ul 6 R(T,,) and U2 6 R(T, ), T1"',~,,T,~2 E 75-1,3'1 #jg. Ifsuch
an edge exists, then we add it to 9'-_1, obtaining 9",;1. Since ul and 112 are removable
vertices of T,-l and T,-,, both subgraphs T,, — {ul} and T,-, — {U2} contain complete
matchings on their vertices. We add these matchings to 3",_1, thus obtaining 57",. The
subgraph T,-l and T,-2 are then removed from ‘3' ,-_1, resulting in a new family ‘3}.

We claim that whp this process can be performed successfully for m1 steps. To
prove this, we consider the edges of H2. At step i of the above process the family
‘J’,_1 contains at least m2 — 27m 2 n“ subgraphs. Choose m2 — 2m1 subgraphs from
3",_1 arbitrarily and denote them by T1, . . . ,Tm,_2m,. Note that zgfm‘ |V(T,-)| =
k(mg-2m1) = 9(n0'95). By pr0position 3.8, we have |R(T,-)| Z mgfll, so |R(T,)| 2 g,

and thus |R(T,-)| = 9(n1“‘-l) for every 1 Sj 3 m2 — 2m1.

48

Given T,, and T,-,, the probability that an edge {v.-,u1, 112} doesn’t exists is
3 5 2
(1 — (g) 5 191—1) (3) . Therefore the probability that the process fails at step i where
(”*3""‘)(%)’

3
1 S i g ml is (1 — (g) 5 171—1) . So, the probability that the process gives

W‘s-9'01 1t. 2 m1
us a matching is (1— (1— (§)%p1_1)( 2 )(3) ) . We have

(1 — (1 — (9%....) (Mammy)
> 1— m1 (1— (g)%pI—l)(mg-22"“)G)2

> 1— mle-(g) g”1'"("WV-22"“)(§)2_

Because ("u—22"“) (5)2 = CUB—(EM) = 9 ((n0'95)2) = 9 (71”), m1 = n“-1 and

3 l8

p;_1= 9 (n‘g), we get
1 _ mle—(%)9m—x(m2-.W)(§)’

~1— 9 n‘l—l
C(g)anos

”0.95

2 1— 9 C(g)ano.4

Therefore, whp the process finds the desired edges.

After the process terminated, we have a family ‘J'm, = {T1, . . . ,Tm,_2m,} of Ho-
hypertrees. Deleting a removable vertex v,- 6 R(T,) from every T, E Tm“ we have a
matching in each T,. We add all these edges to 9),". Now 3",, covers all vertices of V
except the deleted removable vertices {u1, . . . , um,_2m,} from (Tm. Since 2m2 -—2m1 =
n“, 3m, is the matching we want to get. [:1

Proof of Theorem 3.7. Refer to lemma 3.2 and consider a random graph H E
H(n, 3,1919) and represent it as a union of H1 6 H(n, 3,po) and H2 6 H(n, 3, (g) % p13).
Follow lemma 3.2’s construction, we have, whp, H2 contains a matching that covers
5

all but at most 120‘05 vertices. Define ml to be the largest integer not exceeding n”

and satisfying m1 5 0 (mod 3), and define m2 = 2m1. Now, we follow a similar process

49

as the one in lemma 3.2, but in this time, instead of choosing 2 Ho-hypertrees from a
set of mg — 2m1 Ho-hypertrees as in lemma 3.2, we arbitrary assign 2 Ho-hypertrees
to every uncovered vertices and then we follow the old process. At this time, we have
|R(T,-)| 2 g = 9(n1“‘-‘) = 9(n0'95) for every T,- E 3'. Now, the probability that we

fail to find a desired edge in one of the step is given by (1 — (g) i}: p13) (5) . Therefore,

the probability we succeed is

~1—e ——,—n
(g) no.4

So, whp the process finds the desired edges and then we get, at this time, a complete
matching of H.

:1
In order to estimate p19, we consider the fact that pg = pa + (92121-1 —

s i (am—1
(g) POPI—l g pa + (§)’p¢_1 for every I 2 1. Therefore p; _<_ —“—;—— P0 or

(t) -1
9 §(20)_1 3 3
P19 _<_ 11L}— (77n‘5) S 578671775. E]
( ) 1

9 _
5

50

BIBLIOGRAPHY

51

BIBLIOGRAPHY

[AcI93] R. Acharya and D. Ibaroudene, Linear hypertree for multidimensional image
representation, Inform. Sci. 68 (1993) 123-154.

[An82] S. Antonuicci, Sur les colorations généralisées des hyperarbres et sur les mul-
ticolorations des graphes, Riv. Mat. Univ. Parmaa) 8 (1982) 235-242.

[A892] N. Alon and J.H. Spencer, The Probabilistic Method, Wiley (1992).
[Be70] C. Berge, Graphs et Hypergraphes, Dunod (1970).

[Be73] C. Berge, Introduction A: La The’orie Des Hypergraphes, Les Presses De
L’Université De Montreal (1973).

[Be87] C. Berge, Hypergraphs : Gombinatorics of Finite Sets, North-Holland (1989).

[BeM69] L.W. Beineke and J .W. Moon, Several Proofs of the Number of Labeled
2-Dimensi0nal Trees, Proof Techniques in Graph Theory, Academic New York,
(1969).

[BeP69] L.W. Beineke and RE. Pippert, The number of labelled k-dimensional trees,
Journal of Combinatorial Theory 6 (1969) 200—205.

[BiLW76] N.L. Biggs, E.K. Lloyd and R.J. Wilson, Graph Theory 1736-1936, Oxford
University Press (1976).

[B084] V. Boonyasombat, Degree sequences of connected hypergraphs and hypertrees,
Graph theory, Singapore 1983 236-247, Lecture Notes in Math., 1073, Springer,
Berlin-New York, 1984.

[B085] B. Bollobés, Random Graphs, Academic Press (1985).

[BrCD95] A. Brandstadt, V. D. Chepoi and F. F. Dragan, The algorithmic use of hy-
pertree structure and maximum neighbourhood orderings, Graph-theoretic con-
cepts in computer science (Herrsching, 1994) 65—80, Lecture Notes in Compt.
Sci., 903, Springer, Berlin, 1995.

52

[BrCD98] A. Brandstiidt, V. D. Chepoi and F. F. Dragan, The algorithmic use of hy-
pertree structure and maximum neighbourhood orderings, Discrete A ppl. Math.
82 (1998) 43—77.

[BrD94] A. Brandstéidt, Andreas and F. F. Dragan, Dominating cliques in graphs
with hypertree structure, 735-746, Lecture Notes in Comput. Sci., 775, Springer,
Berlin (1994) 735—746.

[BrD96] A. Brandstadt and F. F. Dragan, r-dominating cliques in graphs with hy-
pertree structure, Discrete Math. 162 (1996) 93-108.

[Dr99] F. Drewes, A characterization of the sets of hypertrees generated by
hyperedge-replacement graph grammars, Theory Comput. Syst. 32 (1999) 159-
208.

[ErR59] P. Erdiis and A. Rényi, On random graphs I, Publ. Math. Debrecen 6 (1959)
290—297.

[ErR60] P. Erd6s and A. Rényi, On the evolution of random graphs, Publ. Math.
Inst. Hung. Acad. Sci. 5 (1960) 17-61.

[ErR61a] P. Erdéis and A. Rényi, On the evolution of random graphs, Bull. Inst.
Internat. Statist. 38, 4 (1961) 343-347.

[ErR61b] P. Erdfis and A. Rényi, On the strength of connectedness of a random
graph, Acta Math. Acad. Sci. Hangar. 12 (1961) 261-267.

[ErR64] P. Erdfis and A. Rényi, On random matrices, Magyar Tad. Akad. Mat. Ku-
tato’ Int. Ko'zl. 8 (1964) 455-461.

[ErR66] P. Erdéis and A. Rényi, On the existance of a fractor of degree one of a
connected random hypergraph, Acta Math. Acad. Sci. Hangar. 17 (1966) 359-
368.

[ErR68] P. Erdiis and A. Rényi, On random matrices II, Studio Sci. Math. Hungar.
3 (1968) 459-464.

[GaJ79] M. R. Garey and D. S. Johnson, Computers and Intractability: a guide to
the theory of NP-completeness, W. H. Freeman, New York (1979)

[Gi78] M. Gionfriddo, Hypergraphs lacking significant r-cycles and K -hypertrees,
Riv. Mat. Univ. Parma (4) 4 (1978) 259-268.

53

[Gr91] D. Grieser, Counting complements in the partition lattice, and hypertrees, J.
Combin. Theory Ser. A 57 (1991) 144-150.

[GrH93] D. A. Grable and F. M. H0ppe, Permutation hypertrees in probability, Ars
Combin. 35 (1993) 135-142.

[HaP68] F. Harary and E. M. Palmer, On acyclic simplicial complexes, Mathematika
15 (1968) 115-122.

[HaP73] F, Harary and E. M. Palmer, Graphical Enumeration, Academic, New York
(1973).

[Hu50] K. Husimi, Note on Mayer’s Theory of Cluster Integrals, J. Chem. Phys. 18
(1950) 682-684.

[1501] T. Ishihara, Enumeration of hypergraphs, Europe J. Combinatorics 22 (2001)
503-509.

[J aLR90] S. J anson, T. Luczak and A. Ruciriski, An exponential bound for the prob-
ability of nonexistence of a Specified subgraph in a random graph, Random
Graphs ’87 (1990) 73-87.

[Ka82] M. Karoriski, Random hypertrees, allocations and partitions, Graphs and
other combinatorial topics (Pargue, 1982) 159—162, Teubner-Texte Math. 59,

Teubner, Leipzig, 1983.

[KaN91] M. Karoriski and K. Nowicki, On the entr0py of vertex degree distributions
in a random hypertree, Advances in graph theory 215-226, Vishwa, Gulbarga,
1991.

[K099] V. F. Kolchin, Branching processes and random hypertrees, Diskret. Mat. 11
(1999), 8-23 translation in Discrete Appl. Math. 9 (1999) 7-23.

[Kr97] M. Krivelevich, Triangle Factors in Random Graphs, Combinatorics, Proba-
bility and Computing 6 (1997) 337-347.

[Li86] G. Z. Liu, A theorem on the factors of r-hypertrees, Adv. in Math. (Beijing)
15 (1986) 381-383.

[LiZ88] B. L. Liu and X. K. Zhang, The enumeration theory of hypertrees. 1, Chinese
Quart. J. Math. 3 (1988) 78-82.

[LjS74] V. N. Ljamin and B. I. Selivanov, Hypertrees with a given number of end
vertices and edges, Kombinatornyi’ Anal. Byp. 3 (1974) 68-71.

54

[LjS74b] V. N. Ljamin and B. I. Selivanov, Random hypertrees and hyperforests,
Mat. Zametki 15 (1974) 641-650.

[M70] J. W. Moon, Counting Labelled Trees, Canadian Mathematical Monographs
(1970).

[NiP99] J. Nieminen and M. Peltola, Hypertrees, Appl. Math. Lett. 12 (1999) 35-38.

[NiV00] A. Niculitsa and V. Voloshin, About uniquely colorable mixed hypertrees,
Discuss. Math. Graph Theory 20 (2000) 81-91.

[Pa73] E. M. Palmer, On the number of n-plexes, discrete Math. 6 (1973) 377-390.
[Pa85] E. M. Palmer, Graphical Evolution, John Wiley & Sons, 1985.

[PaR85] E. M. Palmer and R. W. Robinson, Connectivity of a random m-graph,
Revue Roumaine De Mathe’matiques Pures Et Applique’es , XXX N.3 (1985)
229-232.

[P3879] E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest,
Journal of Combinatorial Theory, Series B 27 (1979) 109-121.

[80883] J. Schmidt and E. Shamir, A threshold for perfect matchings in random
d-pure hypergraphs, Discrete Math. 45 (1983) 287-295.

[Se75] B. I. Selivanov, Additional remarks on homogeneous hypertrees and hy-
perforests, Combinatorial and Asymptotic Analysis, Krasnojarsk. Gos. Univ,
Krasnoyarsk (1975) 137-146.

[SOT 00] M. Sonntag and H. Teichert, Sum numbers of hypertrees, Discrete Math.
214 (2000) 285-290.

[T086] I. Tomescu, Hypertrees and Bonferroni inequalities, J. Combin. Theory Ser.
B 41 (1986) 209-217.

[T092] 1. Tomescu, Ordered h—hypertrees, Discrete Math. 105 (1992) 241-248.

[T0Z94] I. Tomescu and M. Zimand, Minimum spanning hypertrees, Discrete Appl.
Math. 54 (1994) 67-76.

[T1147] W. T. Tutte, The factorizations of linear graphs, J. London Math. Soc. 22
(1947) 107—111.

55

[Ve82] W. Fernandez de la Vega, Sur la cardinalité maximum des couplages
d’hypergraphes aléatorires uniformes, Discrete Math. 40 (1982) 315- 318.

[Yu00] R. Yuster, Decomposing hypergraphs into simple hypertrees, Combinatorica
20 (2000) 119—140.

56

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

[1]][1|][[[[[[I[][[1]][1]

335 6