A note on polynomials and f -factors of graphs
Hamed Shirazi Jacques Verstra¨ete
Dept of Combinatorics & Optimization Dept of Mathematics & Statistics University of Waterloo McGill University
Waterloo, Ontario, Canada Montreal, Quebec, Canada [email protected] [email protected]
Submitted: May 12, 2008; Accepted: Jun 10, 2008; Published: Jun 20, 2008 Mathematics Subject Classification: 05C07
Abstract
Let G= (V, E) be a graph, and let f : V →2Z be a function assigning to each v ∈ V a set of integers in {0,1,2, . . . , d(v)}, where d(v) denotes the degree of v in G. Lov´asz [5] defines an f-factor of G to be a spanning subgraph H of G in which dH(v) ∈f(v) for all v ∈ V. Using the combinatorial nullstellensatz of Alon [2], we prove that if |f(v)| > d12d(v)e for all v ∈ V, then G has an f-factor. This result is best possible and verifies a conjecture of Addario-Berry, Dalal, Reed and Thomason [1].
1 Introduction
In this paper, we are interested in the existence off-factors of graphs, where the term “f- factor” has a more general meaning than the traditional one. Let G= (V, E) be a graph, and let f be a function assigning to each v ∈V a set f(v) of integers. Lov´asz [5] defines an f-factor of G (sometimes called a generalized f-factor [5]) to be a subgraph of G in which d(v)∈f(v) for all v ∈ V. In the case |f(v)| = 1, Tutte’s f-factor theorem gives a necesary and sufficient condition for the existence of an f-factor of G. No necessary and sufficient condition for anf-factor exists when we allow|f(v)| ≥2, even when |f(v)|= 2 for allv ∈V, since the decision problem of determining whether a graph has anf-factor is known to be algorithmically hard in this case. On the other hand, Lov´asz [5] showed that if no two consecutive integers in f(v) differ by more than two, then there is a necessary and sufficient condition for an f-factor. We prove the following sufficient condition for f-factors, which verifies a conjecture in Addario-Berry, Dalal, Reed and Thomason [1]:
Theorem 1 Let G= (V, E) be a graph and suppose that f satisfies
|f(v)|>dd(v)/2e for every v ∈V. Then G has an f-factor.
Consider a complete bipartite graphK2n,2nwheref(v) ={0,1,2, . . . , n}for all vertices in one part and f(v) ={n, n+ 1, . . . ,2n} for all vertices in the other, except one vertex v∗ which hasf(v∗) ={n+ 1, n+ 2, . . . ,2n}. This graph has nof-factor and the condition of Theorem 1 fails only for v∗.
Alon, Friedland and Kalai [3] showed that in any graph G = (V, E) with more than (p−1)|V| edges, where pis a prime power, we have a subgraph in which all the degrees are positive multiples of p (this subgraph certainly need not be a spanning subgraph).
For example, every 2p−1-regular graph contains a p-regular subgraph whenpis a prime power. More generally, we can ask for a subgraph where the degrees are in prescribed sets.
With this in mind, we define apartialf-factorof a graph G= (V, E) to be an ˜f-factor of G where ˜f(v) =f(v)∪ {0} for all v ∈V, and a partial f-factor of G isnon-trivial if it is non-empty. Our next result is a sufficient condition for a graph to have a partialf-factor:
Theorem 2 Let G= (V, E) be a graph, and let f satisfy
|E|>X
v∈V
|f(v)c\{0}|
where f(v)c={0,1,2, . . . , d(v)}\f(v). ThenG contains a non-trivial partial f-factor.
We remark that Theorem 2 can be extended easily to hypergraphs, in fact the same sufficient condition as displayed in Theorem 2 works to give an f-factor of a hypergraph G = (V, E). The theorem, even in this generality, is best possible. Take, for instance, a hypergraph G= (V, E) consisting of a set of hyperedges joined at a common vertex, say a. So all the vertices have degree one except a which has degree|E|. Assign f(a) ={0}
and f(b) ={0,1}for anyb ∈V\{a}. Then Gclearly has no non-trivial partial f-factors,
and X
v∈V
|f(v)c\{0}|=|E|.
Theorem 1 can also be extended to hypergraphs, but the appropriate condition on |f(v)|
then depends on the upper rank of the hypergraph – that is, the size of the largest hyperedge.
The proofs of Theorems 1 and 2 involve the use of the combinatorial nullstellensatz [2].
2 Proof of Theorems 1 and 2
The total degree of a polynomial g ∈ F[X1, X2, . . . , Xn] is the largest value of t1 +t2 +
· · ·+tn, taken over all monomials of the form X1t1X2t2 . . . Xntn with non-zero coefficient in g. We shall make use of the combinatorial nullstellensatz [2] to prove Theorems 1 and 2:
Theorem 3 (Combinatorial Nullstellensatz) Let g ∈ F[X1, X2, . . . , Xn] be a poly- nomial, and suppose the coefficient of the monomial Qn
i=1Xiti in g is non-zero, where t1 +t2 +· · · +tn is the total degree of g. Then, for any sets S1, S2, . . . , Sn ⊂ F with
|S1|> t1, |S2|> t2, . . . ,|Sn|> tn, there exists x∈S1×S2× · · · ×Sn such that g(x)6= 0.
The nullstellensatz is an elegant tool for existential proofs. The general theme for applying the nullstellensatz is to first define a polynomial whose non-vanishing points correspond to the object we are looking for. This is in general easy to do. Then the hard part is to prove algebraically or combinatorially that some appropriate largest degree monomial in our polynomial has non-zero coefficient.
Proof of Theorem 1. Consider the polynomial overR defined by g = Y
v∈V
Y
c∈f(v)c
X
e3v
Xe−c
where f(v)c={0,1,2, . . . , d(v)}\f(v). We claim that there exists a largest degree mono- mial in g of the form aQ
e∈EXete wherete∈ {0,1}for all e∈E and a >0. The degree of g is exactly
X
v∈V
|f(v)c|.
To find a monomial of the required form, we observe that every graph on V has an orientation such that the outdegree of every vertex v ∈ V is at least b12d(v)c. This can be seen by orienting an eulerian tour in the graph G∗ obtained from G by adding a new vertex and joining it to all vertices of G of odd degree. Therefore it is possible to assign to each v ∈ V a set E(v) of edges containing v such that |E(v)| = |f(v)c| and, for all distinct u, v∈V,
E(u)∩E(v) =∅.
Then Y
v∈V
Y
e∈E(v)
Xe
is a monomial of the required degree in g. By the combinatorial nullstellensatz, there exists x ∈ {0,1}|E| such that g(x) 6= 0. Now F = {e ∈E : xe = 1} is the edge set of an f-factor ofG.
Proof of Theorem 2. Consider the polynomial overR defined by
g = Y Y
c−P
e3vXe
−Y
(1−X ).
Then g(0) = 1−1 = 0. By the inequality of the theorem, the total degree of the first term in g is
X
v∈V
|f(v)c\{0}| < |E|
so we conclude that the largest degree monomial in g is precisely (−1)|E|+1Q
e∈EXe. By the combinatorial nullstellensatz, there exists a non-zerox∈ {0,1}|E|such thatg(x)6= 0.
This implies that the first term in g is not zero at x, and so P
v3exe ∈f(v)∪ {0} for all v ∈V. If
F = {e ∈E :xe = 1}, then F is the edge set of a non-trivial partialf-factor of G.
3 Concluding Remarks
We mention a possible direction for extending the results of Theorem 1 and Theorem 2.
Alon, Friedland and Kalai [3] proved that for any prime power p, every graph of average degree more than 2p−2 contains a non-empty subgraph all of whose vertices have degree zero modulo p. As a natural extension of their result, given a graph G = (V, E) and a function f : V → Z, we can ask for a subgraph H = (W, F) such that W 6= ∅ and the degree of a vertex w in H is congruent modulo p to f(w), for all w ∈W (we might call this apartial f-factor mod p). We ask whether such a subgraph is guaranteed to exist in a graph with sufficiently large (but constant) average degree – even the case f(v) = q for all v ∈ V appears to be challenging. The question of finding sufficient conditions for a subgraph in which the degree ofv isf(v) modulo pfor every vertex v ∈V (we might call such a subgraph anf-factor modp) appears to be interesting. Note that such a subgraph exists if and only if
Y
v∈V
1− X
e3v
Xe−f(v)
!p−1
is nonzero for some {0,1}-evaluation of the variables. When the average degree is 2p−2 analogous to the proof of Theorem 1 we can show that if the number of orientations with the outdegree of each vertexp−1 is not zero modpthen anf-factor modpexists for any f. In particular in a (2p−2)-regular graph if the number of eulerian orientations is not a multiple of p then for any function f, an f-factor mod p exists. In case of a bipartite (2p−2)-regular graph if we define f :V →Z to be 1 on some vertex and 0 on all others, then an f-factor mod pdoes not exist, and so we get the following result.
Theorem 4 For any prime p, the number of eulerian orientations in a bipartite(2p−2)- regular graph is zero modulo p.
References
[1] Addario-Berry, L; Aldred, R; Dalal, K; Reed, B. Vertex Colouring Edge Partitions.
Journal of Combinatorial Theory B Volume 94, Issue 2 (2005) 237-244
[2] Alon, N. Combinatorial Nullstellensatz. Recent trends in combinatorics (M´atrah´aza, 1995). Combin. Probab. Comput. 8 (1999), no. 1-2, 7–29.
[3] Alon, N; Friedland, S; Kalai, G. Regular subgraphs of almost regular graphs. J. Com- bin. Theory Ser. B 37 (1984), no. 1, 79–91.
[4] Karo´nski, M; Luczak, T; Thomason, A. Edge weights and vertex colours. J. Combin.
Theory Ser. B, 91 (2004) 151–157.
[5] Lov´asz, L. Generalized factors of graphs. Combinatorial theory and its applications, II (Proc. Colloq., Balatonf¨ured, 1969), pp. 773–781. North-Holland, Amsterdam, 1970.
