Packing in a hypergraph - AbsoluteAstronomy.com

In mathematics, a packing in a hypergraph is a partition

Partition of a set

In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

of the set of the hypergraph

Hypergraph

In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...

's edges into a number of disjoint subsets such that no pair of edges in each subset share any vertex. There are two famous algorithms to achieve asymptotically optimal packing in k-uniform hypergraphs. One of them is a random greedy algorithm

Greedy algorithm

A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....

which was proposed by Joel Spencer

Joel Spencer

Joel Spencer is an American mathematician. He is a combinatorialist who has worked on probabilistic methods in combinatorics and on Ramsey theory. He received his doctorate from Harvard University in 1970, under the supervision of Andrew Gleason...

. He used a branching process

Branching process

In probability theory, a branching process is a Markov process that models a population in which each individual in generation n produces some random number of individuals in generation n + 1, according to a fixed probability distribution that does not vary from individual to...

to formally prove the optimal achievable bound under some side conditions. The other algorithm is called Rödl nibble and was proposed by Vojtěch Rödl

Vojtěch Rödl

Vojtěch Rödl is a Czech mathematician, currently the Samuel Candler Dobbs Professor at Emory University, Atlanta, known for his work in combinatorics. He received his PhD from Charles University, Prague in 1976...

et al. They showed that the achievable packing by Rödl nibble is in some sense close to that of the random greedy algorithm.

History

The problem of finding the number of such subsets in a k-uniform hypergraph

Hypergraph

was originally motivated through a conjecture by Paul Erdős

Paul Erdos

Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...

and Haim Hanani in 1963. Vojtech Rödl

Vojtěch Rödl

proved their conjecture asymptotically under certain conditions in 1985. Pippenger and Joel Spencer

Joel Spencer

generalized Rödl's results using a random greedy algorithm

Greedy algorithm

A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....

in 1989.

Definition and terminology

In the following definitions, the hypergraph

Hypergraph

is denoted by

is called k-uniform hypergraph if every edge in

consists of exactly

vertices.

is a hypergraph packing if it is a subset of edges in H such that there is no pair of distinct edges with a common vertex.

is a (,)-good hypergraph if there exists a

such that for all

and

and both of the following conditions hold.

where deg of a vertex denotes the number of edges that contain that vertex and codeg of two distinct vertices denotes the number of edges that contain both vertices.

Theorem

There exists an asymptotic packing P of size at least

for a

-uniform hypergraph under the following two conditions,

All vertices have the degree of in which tends to infinity.
For every pair of vertices shares only common edges.

where

is the total number of vertices. This result was shown by Pippenger and was later proved by Joel Spencer. To address the asymptotic hypergraph packing problem, Joel Spencer proposed a random greedy algorithm. In this algorithm, a branching process is used as the basis and it was shown that it almost always achieves an asymptotically optimal packing under the above side conditions.

Asymptotic packing algorithms

There are two famous algorithms for asymptotic packing of k-uniform hypegraphs which are random greedy algorithm via branching process and Rödl nibble.

Random greedy algorithm via branching process

Every edge

is independently and uniformly assigned a distinct real "birthtime"

. The edges are taken one by one in the order of their birthtimes. The edge

is accepted and included in

if it does not overlap any previously accepted edges. Obviously, the subset

is a packing and it can be shown that its size is

almost surely. To show that, let stop the process of adding new edges at time

. For an arbitrary

, pick

such that for any

-good hypergraph

where

denotes the probability of vertex

survival (a vertex survives if it is not in any edges in

) until time

. Obviously, in such a situation the expected number of

surviving at time

is less than

. As a result, the probability of

surviving being less than

is higher than

. In other words,

must include at least

vertices which means that

.

To complete the proof, it must be shown that

. For that, the asymptotic behavior of

surviving is modeled by a continuous branching process. Fix

and begin with Eve with the birthdate of

. Assume time goes backward so Eve gives birth in the interval of

with a unit density Poisson distribution

Poisson distribution

In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time and/or space if these events occur with a known average rate and independently of the time since...

. The probability of Eve having

birth is

. By conditioning on

the birthtimes

are independently and uniformly distributed on

. Every birth given by Eve consists of

offspring all with the same birth time say

. The process is iterated for each offspring. It can be shown that for all

there exists a

so that with a probability higher than

, Eve has at most

descendants.

A rooted tree with the notions of parent, child, root, birthorder and wombmate shall be called a broodtree. Given a finite broodtree

we say for each vertex that it survives or dies. A childless vertex survives. A vertex dies if and only if it has at least one brood all of whom survive. Let

denote the probability that Eve survives in the broodtree

given by the above process. The objective is to show

and then for any fixed

, it can be shown that

. These two relations complete our argument.

To show

, let

. For

small,

as, roughly, an Eve starting at time

might have a birth in time interval

all of whose children survive while Eve has no births in

all of whose children survive. Letting

yields the differential equation

. The initial value

gives a unique solution

. Note that indeed

.

To prove

, consider a proceture we call History which either aborts or produces a broodtree. History contains a set

of vertices, initially

will have a broodtree structure with

the root. The

are either processed or unprocessed,

is initially unprocessed. To each

is assigned a birthtime

, we initialize

. History is to take an unprocessed

and process it as follows. For the value of all

with

but with no

that has already been processed, if either some

has

and

with

or some

have

with

and

, then History is aborted. Otherwise for each

with

add all

as wombmates with parent

and common birthdate

. Now

is considered processed. History halts, if not aborted, when all

are processed. If History does not abort then root

survives broodtree

if and only if

survives at time

. For a fixed broodtree, let

denote the probability that the branching process yields broodtree

. Then the probability that History does not abort is

. By the finiteness of the branching process,

, the summation over all broodtrees

and History does not abort. The

distribution of its broodtree approaches the braching process distribution. Thus

Rödl nibble

In 1985, Rödl proved Paul Erdős

Paul Erdos

’s conjecture by a method called Rödl nibble. Rodl's result can be formulated in form of either packing or covering problem. For

the covering number denoted by

shows the minimal size of a family

of k-element subsets of

which have the property that every l-element set is contained in at least one

. Paul Erdős

Paul Erdos

et al. conjecture was

.

where

. This conjecture roughly means that a tactical configuration is asymptotically achievable. One may similarly define the packing number

as the maximal size of a family

of k-element subsets of

having the property that every l-element set is contained in at most one

Packing under the stronger condition

In 1997, Noga Alon

Noga Alon

Noga Alon is an Israeli mathematician noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.- Academic background :...

, Jeong Han Kim

Jeong Han Kim

Jeong Han Kim is a South Korean mathematician specializing in combinatorics and computational mathematics. He studied physics and mathematical physics at Yonsei University, and earned his Ph.D in mathematics at Rutgers University...

, and Joel Spencer

Joel Spencer

also supply a good bound for