Transcript Every H-decomposition of Kn has a nearly resolvable

Every H-decomposition of Kn has
a nearly resolvable alternative
• Wilson: e(H) | n(n-1)/2 and gcd(H) | n-1 n>>
then there exists an H-decomposition of Kn.
• There may be many distinct H-decompositions
of Kn which vary in their properties.
• Example: H=Kk k | n k-1 | n-1 n>> then
there exists a resolvable Kk dec. of Kn. This is
a theorem of Ray-Chaudhuri & Wilson. There
are also non-resolvable ones.
• There is no analog of the theorem of RC & W
for general graphs H. In fact it is not true for
some H. (e.g. H=K1,t where t > 2 is odd).
• The resolution number c(H,n):
let L be an H-dec. of Kn. c(L) is the chromatic
number of the intersection graph of L.
c(H,n) = minL c(L).
• By RC & W c(Kk,n) = (n-1)/(k-1) iff
n=k mod k(k-1) and n >>.
• Trivially, c(H,n) (n-1)h/(2m) where
m=|e(H)|. Equality holds iff there is a
resolvable H-decomposition.
The main result
• Let H be a fixed graph with h vertices and m
edges. Then:
c(H,n) =(1+o(1))(n-1)h/(2m).
• The o(n) term is, in fact, of the form nb where
b < 1. The error term cannot be omitted.
Outline of proof
• First, we show that if Kn is H-dec. then it can
also be decomposed into H-decomposable
cliques whose sizes are bounded.
– This follows from a theorem of Wilson regarding
pairwise balanced designs, together with an
additional simple set-theoretic argument.
• We also need to use the powerful theorem of
Pippenger & Spencer regarding the chromatic
index of uniform hypergraphs:
• Let h and C be positive integers and let a<1
and e <1be positive reals. There exists
N0=N0(h,C,a,e) and 0 < b=b(h,C,a,e) < 1
such that the following holds: If S is an huniform hypergraph with n>N0 vertices and:
– There exists d > en such that for every
vertex x |deg(x)-d| < da.
– Any two vertices appear together in at most
C edges.
Then, q(S) < d+db.
• Every H-dec. defines an h-uniform hypergraph
whose edges correspond to the vertices of
each member of the decomposition. Clearly,
the chromatic index of this hypergraph is what
we need to bound. We need to show there is an
H-dec. whose hypergraph satisfies the
conditions of P & S with d=(n-1)h/(2m).
• We need the following large deviation result:
– For every a>0 there exists t=t(a) such that if t >T
and X1 , . . . , Xt are t mutually independent discrete
r.v. taking values between 0 and a and m is the
expectation of X= X1 + . . . + Xt then:
prob[|X- m|>t0.51] < t -2.
Proof is a simple use of Azuma’s inequality.
Combining it all together
• Let F=F(H) be a finite set of integers with the
property that if Kn is H-dec. then Kn is also
decomposable into H-decomposable cliques
whose sizes belong to F. Define C=(k-1)/d(H)
where k is the largest integer in F. Define
e=h/(3m) < 1. Let a=0.6, and let band N0 be
as in P & S.
• For each f  F let Lf be a fixed H-dec. of Kf .
let Yf be the r.v. corresponding to the number
of members of Kf containing a randomly
selected vertex. Note that Yf is discrete and
0 < Yf < k.
• We show that if n >> and Kn is Hdecomposable then c(H,n) < d+db where
d=(n-1)h/(2m).
• Let L* be a decomposition of Kn into
H-decomposable cliques whose sizes belong
to F. Each Q  L* is isomorphic to some Kf so
there are f! different ways to decompose Q
into copies of H using Lf . for each Q  L* we
randomly and uniformly choose such a
permutation. All |L*| choices are independent.
This defines a random H-dec. of Kn denoted L.
• We show that with positive probability, each
vertex of Kn appears in at least d-daand in at
most d+da members of L. This follows (with a
little work) from the large deviation lemma.
• Any two members of Kn appear together in at
most C members of L.
• The last two claims show that P & S holds for
the hypergraph corresponding to L, with
positive probability.
A conjecture
• The o(n) error term in the result can be
replaced by a constant (which depends only on
H). Namely:
c(H,n) = (n-1)h/(2m) +C(H).
Another small goodie
• For every H there are infinitely many n, for
which there exists an H-dec. L of Kn such that
the intersection graph of L is regular of degree
(n-1)h/(2m). (This is only interesting if H is
not a regular graph).