°c 1998 Kluwer Academic Publishers. Manufactured in The Netherlands.
On the Number of Group-Weighted Matchings
JEFF KAHN∗
Dept. of Mathematics and RUTCOR, Rutgers University, New Brunswick, NJ 08903 ROY MESHULAM
Dept. of Mathematics, Technion, Haifa 32000, Israel Received January 10, 1996; Revised January 23, 1997
Abstract. Let G be a bipartite graph with a bicoloration{A,B},|A| = |B|, and letw: E(G)→K where K is a finite abelian group with k elements. For a subset S⊆E(G)letw(S)=Q
e∈Sw(e). A perfect matching M⊆E(G)is aw-matching ifw(M)=1.
It is shown that if deg(a)≥d for all a∈A, then either G has now-matchings, or G has at least(d−k+1)!
w-matchings.
Keywords: bipartite matching, digraph, finite abelian group, group algebra, Olson’s Theorem
1. Introduction
Let G be a bipartite graph with a bicoloration{A,B},|A| = |B|. Let E(G) ⊆ A×B denote the edge set of G, and let m(G)denote the number of perfect matchings of G.
Let K be a (multiplicative) finite abelian group|K| =k, and letw: E(G) → K be a weight assignment on the edges of G. For S⊆E(G)letw(S)=Q
e∈Sw(e).
A perfect matching M of G is aw-matching ifw(M)= 1. We shall be interested in m(G, w), the number ofw-matchings of G.
M. Hall (see exercise 7.15 in [9]) showed that if m(G)≥ 1 and if deg(a)≥ d for all a∈ A, then m(G)≥d! .
Hall’s result is the case k =1 of the following Theorem. The case k =2 was proved in [1].
Theorem 1.1 Letw: E(G)→K. If m(G, w)≥1 and deg(a)≥d for all a ∈ A,then m(G, w)≥(d−k+1)! .
Theorem 1.1 is tight when K = Ck, the cyclic group of order k. More generally, for a finite abelian group K, let s =s(K)denote the maximal s for which there exists a sequence x1, . . . ,xs ∈ K such thatQ
i∈I xi 6=1 for all∅ 6= I ⊆[s]= {1, . . . ,s}. The problem of determining s(K)was suggested by Davenport (see [11]) and addressed by a number of authors [3, 5, 10, 11].
∗Supported in part by NSF and BSF.
Let d ≥s=s(K)and let G =Kd,d denote the complete bipartite graph on [d]×[d].
Letw: E(Kd,d)→ K be given byw(i,j)=1 if i = j or i ≥ s+1, andw(i,j)=xi
otherwise, where x1, . . . ,xs are as above. Then m(G, w)=(d−s)! .
This construction suggests the following conjecture (which contains Theorem 1.1 since it’s easy to see that s(K)≤k−1).
Conjecture 1.2 ([1]) Letw: E(G)→K. If m(G, w)≥1 and deg(a)≥d for all a∈ A, then m(G, w)≥(d−s(K))! .
In Section 2 we utilize the complex group algebra of K to prove Theorem 1.1. In Section 3 we discuss a possible approach to Conjecture 1.2 when K is a p-group (the nice point here is the reduction to Conjecture 3.2 via Claim 3.3), and observe a connection with a conjecture of Griggs and Walker [8].
2. Proof of Theorem 1.1
The main ingredient of the proof of Theorem 1.1 is the following result on group-weighted digraphs.
Theorem 2.1 Let D =(V,E)be a simple digraph and letϕ: E → K. If deg+(v) ≥ k for all v ∈ V, then there exist vertex-disjoint directed cycles C1, . . . ,Cl such that Ql
i=1
Q
e∈Ciϕ(e)=1.
Proof: It is, of course, enough to prove the Theorem when deg+(v) = k for all v. LetC[K] denote the complex group algebra of K, Mn×k(C[K])the n×k matrices over C[K] and Mn(C[K])= Mn×n(C[K]). (For group algebras see e.g., [12].) For a matrix Q=(qi j)∈ Mn(C[K])and x ∈C[K], let S(Q,x)= {σ ∈ Sn:Qn
i=1qiσ(i) =x}(where Snis the symmetric group).
Assume now that V = [n] and associate with D the matrix Q = (qi j) ∈ Mn(C[K]) given by qii =1 for all 1≤i ≤n, qi j=ϕ(i,j)if(i,j)∈E , and qi j =0 otherwise.
Claim 2.2 There exists a matrix C =(ci j)∈Mn(C)with ci i =1 for all 1≤i ≤n,such that the matrix R=(ri j)∈ Mn(C[K])given by ri j=ci jqi jsatisfies det R=0 inC[K].
Proof: Letχ1, . . . , χkdenote the complex characters of K. For 1≤i ≤n let N+(i)= {j :(i,j)∈ E}.
With any n×k matrix H =(hjl)∈Mn×k(C)and 1≤i ≤n, we associate a k×k matrix Hiindexed by N+(i)×[k] and given by Hi(j,l)=χl(qi j)hjlfor j ∈N+(i) , 1≤l≤k.
We may clearly choose an H ∈ Mn×k(C)such that rank Hi =k for all 1≤i ≤n. The non-singularity of Hi implies that there exists a vector(ci j: j ∈ N+(i))such that for all 1≤l≤k
hil= − X
j∈N+(i)
ci jHi(j,l)= − X
j∈N+(i)
ci jχl(qi j)hjl. (1)
Now define cii =1 and ci j =0 if i 6= j and(i,j)6∈ E , and let R =(ri j)=(ci jqi j)∈ Mn(C[K]).
Then (1) implies that for all 1≤l ≤k, 06=(h1l, . . . ,hnl)Tis a nullvector of the matrix χl(R)=(χl(ri j))∈ Mn(C). It follows thatχl(det R)=det(χl(R))=0 for all 1≤l≤k,
hence det R=0 inC[K]. 2
Claim 2.2 implies that 0=det R=X
x∈K
à X
σ∈S(Q,x)
Sg(σ) Yn i=1
ciσ (i)
! x.
Since the identity permutation id belongs to S(Q,1)andQn
i=1ci i=1, it follows that there exists id 6= σ ∈ S(Q,1). Then E0 := {(i, σ (i)): i 6= σ(i)}is a non-empty union of vertex-disjoint directed cycles, say E0=Sl
i=1Ci, and Yl
i=1
Y
e∈Ci
ϕ(e)=Y
qiσ(i)=1. 2
Theorem 1.1 now follows from Theorem 2.1 as in [1]: Let G be a bipartite graph on {A,B},|A| = |B| =n andw: E(G)→K. For a∈ A let UG(a, w)denote the set of all edges incident with a which participate inw-matchings of G, and|UG(a, w)| =uG(a, w).
The following result clearly implies Theorem 1.1 by induction on d.
Theorem 2.2 If G has aw-matching then there exists an a ∈ A such that uG(a, w) ≥ degG(a)−k+1.
Proof: Let M = {(a1,b1), . . . , (an,bn)}be aw-matching of G. With no loss of generality we may assume thatw(ai,bi)= 1 for all i . (Otherwise for each i and e3 ai, multiply w(e)byw−1(ai,bi).)
Construct a directed graph D on {1, . . . ,n}by taking (i,j) ∈ E(D) iff (ai,bj) ∈ E(G)\UG(ai, w), and letϕ: E(D) → K be defined byϕ(i,j) = w(ai,bj). Suppose for a contradiction that the assertion of the theorem is false, so that deg+(v) ≥ k for allv ∈ V(D). It then follows from Theorem 2.1 that D contains vertex-disjoint cycles C1, . . . ,ClwithQl
i=1
Q
e∈Ciϕ(e)=1. Let V0 =Sl
i=1V(Ci)and define a permutationσ on V0byσ(v1)=v2if(v1, v2)∈Sl
i=1E(Ci). Then the perfect matching M0= {(ai,bi): i 6∈V0} ∪ {(ai,bσ (i)): i ∈V0}
is aw-matching. So, since(ai,bσ (i)) 6∈ UG(ai, w)for any i ∈ V0, we have the desired
contradiction. 2
3. An approach to the p-group case
Let K=Cpe1× · · · ×Cpet be an abelian p-group, and letZp[K] denote the group algebra of K overZp. Let Ip(K)= {P
x∈Kaxx∈Zp[K] :P
x∈Kax=0}, the augmentation ideal
ofZp[K]. It was shown by Olson [11], and independently Kruyswijk (see [2]), that Ip(K) is nilpotent of degreePt
i=1(pei −1)+1, and that this implies s(K)=Pt
i=1(pei−1). For S⊆Zp[K] let Mn(S)denote the set of n×n matrices with entries in S. For l≤n−1 let UK(n,l)denote the set of matrices Q=(qi j)∈Mn(K∪ {0})such that for each i ∈[n], qii =1 and Q(i):= {j 6=i : qi j6=0}has cardinality l.
By the proof of Theorem 1.1, Conjecture 1.2 for the p-group K will follow from the following analogue of Claim 2.2.
Conjecture 3.1 For any Q=(qi j)∈UK(n,s(K)+1)there exists a matrix C =(ci j)∈ Mn(Zp)with cii=1 for 1≤i ≤n, such that R=(ri j)=(ci jqi j)∈ Mn(Zp[K])satisfies det R=0 inZp[K].
We next formulate another, perhaps more natural, conjecture which implies Conjec- ture 3.1.
LetA =(A1, . . . ,An)be an ordered family of subsets of [n] such that i 6∈ Ai for all 1≤ i ≤n. Let Wp(A)denote the affine space of all matrices C =(ci j)∈ Mn(Zp)such that cii=1, and ci j=0 whenever i 6= j and j6∈ Ai.
Conjecture 3.2 If|Ai| ≥l for all 1≤i ≤ n, then Wp(A)contains a matrix of rank at most n−l.
To show that Conjecture 3.2 implies Conjecture 3.1 we need
Claim 3.3 Let Q=(qi j)∈ Mn(K)and C=(ci j)∈Mn(Zp). If rank C ≤n−s(K)−1, then R=(ri j)=(ci jqi j)∈ Mn(Zp[K])satisfies det R=0.
Proof: Let B ∈ Mn(Zp)be a non-singular matrix such that the first s(K)+1 rows of BC are zero. Then with B R = (ti j) ∈ Mn(Zp[K]), it follows that ti j ∈ Ip(K)for all 1≤i ≤s(K)+1,1≤ j ≤n. Since Ip(K)is nilpotent of degree s(K)+1 it follows that det B R=P
σ∈SnSgσQn
i=1tiσ (i)=0, hence det R=0. 2
Conjecture 3.2⇒ Conjecture 3.1 Suppose Q = (qi j) ∈ UK(n,s(K)+1), and let A=(Q(1), . . . ,Q(n)). By Conjecture 3.2 there exists a C ∈Wp(A)such that rank C ≤ n−s(K)−1. Let Q0=(qi j0)∈Mn(K)be given by qi j0 =qi jif qi j ∈K and qi j0 an arbitrary element of K otherwise. Clearly R0 :=(ci jqi j0) =(ci jqi j) = R, therefore by Claim 3.3
det R=det R0=0. 2
Remarks.
1. The cases l=1,n−1 of Conjecture 3.2 are trivial. We have proved the cases l=2,n−2 by a graph theoretical argument similier to Proposition 4.1 in [1].
2. Again letA=(A1, . . . ,An)with i6∈ Aifor all i . It is easy to see that the existence of a matrix of rank at most n−l in Wp(A)is equivalent to the existence of vectorsvi ∈Zlp, i∈[n], satisfying
(a) vi ∈ hvj : j∈ Aiifor all i , and
(b) hvi : i∈[n]i =Zlp(whereh·iis linear span).
(The n×l matrix H whose rows are thevi’s will then satisfy M H=0 for an appropriate M ∈Wp(A).) So Conjecture 3.2 is equivalent to the statement that suchviexist whenever
|Ai| =l for all i .
For an l-uniform hypergraphF = {F1, . . . ,Fm}on [n], sayFhas property Gpif there exists a matrix H ∈ Mn×l(Zp)such that the l×l minors of H corresponding to the Fi’s are all non-singular. IfAas above is l-uniform and has property Gpwith corresponding H , then the rows of H satisfy (a), (b), giving Conjecture 3.2 forA. (For example, since property Gp clearly does hold for any fixed n and large enough p, the same follows for Conjecture 3.2.)
Of course, we cannot expect (and do not need) property Gp in general; still, sufficient conditions for the property are of interest. A conjecture of Griggs and Walker [8] says that for any n and A ⊂Zn, the hypergraph{A+i : i ∈ Zn}has property G2. (This was motivated by, and would imply, a conjecture proposed in [4, 6].) For|A| =3, the Griggs- Walker Conjecture was proved by F¨uredi et al. [7], who actually showed property G2 for an arbitrary 3-uniform, 3-regularF.
For general l, such a generalization does not hold, but we believe the following, less extreme relaxation may be correct.
Conjecture 3.4 IfFis l-uniform on [n] and for each t and distinct F1, . . . ,Ft ∈F,
|F1∩ · · · ∩Ft| ≤max{k−t+1,0}, and
|F1∪ · · · ∪Ft| ≥min{k+t−1,n}, thenFhas property Gp.
This contains (via the Cauchy-Davenport Theorem) the Griggs-Walker conjecture when n is prime, and would presumably shed some light on the general case as well.
References
1. R. Aharoni, R. Meshulam, and B. Wajnryb, “Group weighted matching in bipartite graphs,” J. Alg. Combin.
4 (1995), 165–171.
2. P.C. Baayen, “Een combinatorisch probleem voor eindige Abelse groepen,” Math. Centrum Syllabus 5, Colloquium Discrete Wiskunde Caput 3, Math. Centre Amsterdam, 1968.
3. R.C. Baker and W.M. Schmidt, “Diophantine problems in variables restricted to the values 0 and 1,” J. Number Theory 12 (1980), 460–486.
4. F.R.K. Chung, P. Frankl, R. Graham, and J.B. Shearer, “Some intersection theorems for ordered sets and graphs,” J. Combinatorial Theory Ser. A 48 (1986), 23–37.
5. P. van Emde Boas and D. Kruyswijk, “A combinatorial problem on finite abelian groups III,” Z.W. 1969-008 (Math. Centrum, Amsterdam).
6. R. Faudree, R. Schelp, and V.T. S´os, “Some intersection theorems on two-valued functions,” Combinatorica 6 (1986), 327–333.
7. Z. F¨uredi, J.R. Griggs, R. Holzman, and D.J. Kleitman, “Representations of families of triples over G F(2),”
J. Combinatorial Theory Ser. A 53 (1990), 306–315.
8. J. Griggs and J. Walker, “Anticlusters and intersecting families of subsets,” J. Combinatorial Theory Ser. A 51 (1989), 90–103.
9. L. Lov´asz, Combinatorial Problems and Exercises, North-Holland, New York, 1979.
10. R. Meshulam, “An uncertainty inequality and zero subsums,” Discrete Math. 84 (1990), 197–200.
11. J.E. Olson, “A combinatorial problem on finite abelian groups I,” J. Number Theory 1 (1969), 8–10.
12. D.S. Passman, The Algebraic Structure of Group Rings, Wiley-Interscience, New York, 1977.
