Transcript Israel Combinatorics Seminar, Winter 2001

Integer and fractional
packing of graph families
Raphael Yuster
1
Definitions and notations
• Let F be any (finite or infinite) family of
finite graphs.
The F-packing number of a graph G,
denoted ν(F,G), is the maximum number of
edge disjoint elements of F in G.
• The fractional version is denoted ν*(F,G).
Trivially, ν*(F,G) ≥ ν(F,G).
• Example:
ν*({K3} , K4) = 2
ν ({K3} , K4) = 1
• It is NP-Hard to compute ν(F,G) even when
F is a single (nontrivial) graph, say K3.
• Computing ν*(F,G) can be done in
polynomial time if F is finite (LP).
2
Main result and its algorithmic
consequences
• Our main result: If G has n vertices then
ν*(F,G) - ν(F,G) =o(n2).
• Corollary:
ν(F,G) can be approximated to within an
o(n2) additive factor in polynomial time.
• Our proof supplies a randomized algorithm
that finds a packing of size ν(F,G) – o(n2) in
polynomial time. The degree of the
polynomial depends only on F if F is finite.
3
Previous research
• The case where F={H} was first proved by
Haxell and Rödl (Combinatorica 2001).
Their 25 page proof is very difficult. The
main problem lies in the fact that their
method requires proving that there is a
fractional packing which is only slightly less
than optimal, and which assigns to every
copy of H either 0 or a value greater than τ
for some τ > 0 which is only a function of H.
There does not seem to be an easy way to
generalize their proof to the “family” case.
• Our proof is mostly probabilistic and is much
simpler than the HR proof, and can easily be
adapted to the “family” case.
• For “simplicity” we shall only demonstrate
our proof for F={Kk}.
4
Tools used
• The regularity lemma:
For every γ>0, there is an integer M(γ)>0
such that for every graph G of order n > M
there is a γ-regular partition of the vertex set
of G into m classes, for some 1/γ < m < M.
• A “randomlike behavior lemma”
Let δ and ζ be positive reals.
There exist γ = γ(δ, ζ, k) and T=T(δ, ζ, k)
such that the following holds.
Let W be a k-partite graph with vertex classes
V1,…,Vk and |Vi|=t >T. Furthermore, each
(Vi,Vj) is a γ-regular pair with density > δ.
Then, there exists a spanning subgraph W'
with at least (1-ζ)|E(W)| edges such that for
all e  E(W'), if e  E(Vi,Vj) then
|c(e) - tk-2 (∏d(s,p))/d(i,j)| < ζ tk-2
Where c(e) is the number of Kk containing e
5
k=3
Example
d(1,3)=d(2,3)= ½
V1
V2
e
V3
6
Tools used – cont.
• The Frankl- Rödl hypergraph matching
theorem:
For an integer r > 2 and a real β > 0 there
exists a real μ > 0 so that if an r-uniform
hypergraph on q vertices has the following
properties for some d:
(i) (1- μ)d < deg(x) < (1+ μ)d for all x
(ii) deg(x,y) < μd for all distinct x and y
then there is a matching of size at least
(q/r)(1-β).
7
The proof
• Let ε > 0. We shall prove there exists
N=N(k,ε) such that for all n > N, if G is an
n-vertex graph then ν*(Kk,G) - ν(Kk,G) < εn2.
• A consistent “horrible” parameter selection:
δ=ε/4
β=ε/4
μ=μ(β,k2) of Frankl- Rödl
ζ= 0.5μδk2
γ=γ(δ, ζ ,k) T=T(δ, ζ ,k) as in previous lemma
M=M(γε/k2) as in regularity lemma
N= sufficiently large w.r.t. these parameters
• Fix an n-vertex graph G with n > N vertices.
Let ψ be a fractional packing with
w(ψ)= ν*(Kk,G) = αn2> εn2.
8
The proof cont.
• Apply regularity lemma to G and obtain a
γ‘-regular partition with m' parts, where
γ‘=γε/(8k2) and 1/γ' < m' < M(γ').
• Each part has n/m’ vertices but the problem is
that there could be many bad copies of Kk
with two vertices in the same vertex class (we
want to avoid this).
We refine the partition by randomly
partitioning each part into 8k2/ε parts.
The refined partition is now γ-regular.
What we gain: with positive probability the
contribution of the still remaining bad copies
to w(ψ) is less than εn2/16.
We may now assume that there are no bad
copies.
Let V1,…,Vm be the vertex classes of the
refined partition.
9
The proof cont.
• Let G* be the spanning subgraph of G
consisting of the edges with endpoints in
distinct vertex classes of the refined partition
that form a γ-regular pair with density > δ.
• Let ψ* be the restriction of ψ to G* (namely,
to those Kk that “survived”). It is easy to see
ν*(Kk,G*) ≥ w(ψ*) > w(ψ)- δn2 ≥ (α-δ)n2
• Let R denote the m-vertex supergraph.
We define a fractional packing ψ' of R as
follows:
For each H=Kk in R with H={u1,…,uk}
ψ’(H)= w(ψ* | [Vu1,…Vuk]) m2 / n2
important observations:
ψ’ is proper
ν*(Kk,R) ≥ w(ψ’) = w(ψ*)m2/n2 ≥ (α-δ)m2
10
Example
Three vertex classes with n/m=5 in G*,with two
K3 copies inside them having weights 1/2 and 1/3
1/2
1/3
The vertices corresponding to these classes
in R. The weight of the K3 is (1/2+1/3)/52
1/30
11
The proof cont.
• We use ψ' to define a random coloring of the
edges of G*. Our “colors” are the copies of
Kk in R:
Suppose H is a Kk copy in R that contains the
edge (i,j). Each e  E(Vi,Vj) is colored “H”
with probability ψ’(H)/d(i,j).
– The choices made by distinct edges of G*
are independent.
– The random coloring is probabilistically
sound as the sum of ψ’(H) taken over all
Kk copies H containing (i,j) is at most
d(i,j) ≤ 1.
– Some edges might stay uncolored.
12
Example
Two K3 containing (i,j) with d(i,j)=1/5
2/25
i
j
3/25
In E(Vi,Vj)
Prob(- - -) = 2/5
Prob(___ ) = 3/5
Vi
Vj
13
The proof cont.
• Let H be a Kk-copy in R with ψ'(H) > m1-k.
W.l.o.g. H={1,…,k}. Let WH=G*[V1,…,Vk].
– WH satisfies the conditions of the
randomlike behavior lemma.
– Let W'H be the spanning subgraph of WH
whose existence is guaranteed by the
lemma.
– Let XH denote the random spanning
subgraph of W'H consisting only of the
edges whose “color” is “H”.
– For an edge e  E(XH), let cH(e) denote
the set of Kk copies in XH that contain e.
Put r=k(k-1)/2. A crucial lemma is:
• With probability > 1-m3/n, for all e  E(XH)
| cH(e) - tk-2 ψ'(H)r-1 | < μ tk-2 ψ'(H)r-1
14
The proof cont.
• We also need a lower bound for the number
of edges of XH:
With probability at least 1-1/n,
|E(XH)|
> r(1-2ζ) ψ’(H) n2 / m2
• Since there are at most mk copies of Kk in R
we have that with probability at least
1-mk/n - mk+3/n > 0
all copies H of Kk in R with ψ'(H) > m1-k
satisfy the statements of the last two lemmas.
We therefore fix such a coloring.
15
The proof cont.
• Let H be a Kk in R with ψ'(H) > m1-k.
We construct an r-uniform hypergraph LH:
– The vertices of LH are the edges of XH.
– The edges of LH are the edge sets of the
copies of Kk in XH
• Our hypergraph satisfies the FR theorem with
d=tk-2 ψ'(H)r-1. (Notice that the co-degree of
any two vertices of is less than tk-3)
• By FR we have (q/r)(1-β) edge disjoint Kk in
XH. As q > r(1-2ζ) ψ’(H) n2 / m2 we have
(1-β) (1-2ζ) ψ’(H) n2 /m2 ≥ (1-2β)ψ’(H)n2 /m2
•
Recall that w(ψ') ≥ m2(α-δ). Since the
contribution of copies with ψ’(H) ≤ m1-k to
w(ψ') is < m, summing the last inequality
over all H with ψ’(H) > m1-k we have at least
(α-ε)n2 edge disjoint Kk in G.
16