ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 111-117
https://doi.org/10.26493/1855-3974.1317.745
(Also available at http://amc-journal.eu)
Weight choosability of oriented hypergraphs
Marcin Anholcer *
Faculty of Informatics and Electronic Economy, Poznan University of Economics and Business, al. Niepodleglosci 10, 61-875 Poznan, Poland
Bartlomiej Bosek
Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, ul. Prof. S. Lojasiewicza 6, 30-348 Krakow, Poland
Jaroslaw Grytczuk t
Faculty of Mathematics and Information Science, Warsaw University of Technology, ul. Koszykowa 75, 00-662 Warsaw, Poland
Received 4 February 2017, accepted 22 May 2018, published online 19 September 2018
The 1-2-3 conjecture states that every simple graph (with no isolated edges) has an edge weigthing by numbers 1,2, 3 such that the resulting weighted vertex degrees form a proper coloring of the graph. We study a similar problem for oriented hypergraphs. We prove that every oriented hypergraph has an edge weighting satisfying a similar condition, even if the weights are to be chosen from arbitrary lists of size two. The proof is based on the Combinatorial Nullstellensatz and a theorem of Schur for permanents of positive semi-definite matrices. We derive several consequences of the main result for uniform hypergraphs. We also point on possible applications of our results to problems of 1-2-3 type for non-oriented hypergraphs.
Keywords: Oriented hypergraphs, 1-2-3 conjecture, combinatorial nullstellensatz, list weighting. Math. Subj. Class.: 05C15, 05C65, 05C78
* Corresponding author.
t Supported by the Polish National Science Center, decision nr DEC-2012/05/B/ST1/00652. E-mail addresses: m.anholcer@ue.poznan.pl (Marcin Anholcer), bosek@tcs.uj.edu.pl (Bartlomiej Bosek), j.grytczuk@mini.pw.edu.pl (Jaroslaw Grytczuk)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
100
Ars Math. Contemp. 16 (2019) 97-109
1 Introduction
The famous 1-2-3 conjecture, posed by Karonski, Luczak, and Thomason [8], states that every simple graph (with no isolated edges) has an edge weighting with integers 1,2,3 such that no two adjacent vertices get the same weighted degrees. This innocently looking problem remains open for more than ten years, despite serious attacks based on various techniques, including the celebrated Combinatorial Nullstellensatz of Alon [1] (see [2, 10, 12]). The best result up to now [6] confirms the conjecture when the set of allowable weights includes also 4 and 5. There were also many variants considered involving lists, orientations, and most recently hypergraphs (see [2, 3, 5, 7]). It is known, for instance, that any oriented graph has a weighting with numbers 1 and 2 only, such that the resulting weighted degrees are different for every pair of adjacent vertices [2, 9].
In this paper we consider the list version of the 1-2-3 conjecture for oriented hypergraphs. A hypergraph H on the set of vertices V is a family E of non-empty subsets of V, called the edges of H. A hypergraph H is k-uniform if each of its edges has size exactly k. So, a 2-uniform hypergraph is just a simple graph. Let IH denote the incidence graph of a hypergraph H, that is, a bipartite graph with color classes V and E, whose edges are of the form ve, with v e V, e e E, whenever v e e.
Now, by an orientation of a hypergraph H we mean any function ^: E(IH) ^ C assigning non-zero complex "signs" to the edges of the graph IH. The cumulated degree of a vertex v e V is defined by
Dv ^(ev).
If the range of the mapping ^ is confined to the set {-1, +1}, or more generally, to the set of complex roots of unity, then we get a natural generalization of traditional orientation of a simple graph. The orientation ^ is conveniently represented by the oriented incidence matrix X = [^ev] of dimension |E| x |V|, where ^ev = ^(ev) if ev G E(IH), and ^ev = 0, otherwise. By an oriented hypergraph we mean a hypergraph H together with some fixed orientation
Suppose now that each edge e e E of an oriented hypergraph (H, is assigned a complex weight we. Then the resulting weighted degree of a vertex v e V is computed as
Wv	^evWe.
e3v
For each e e E we now define
We = £ ^v Wv , vGe
where x* denotes the complex conjugate of x. Observe that in case of a usual oriented graph, We is exactly the difference between weighted degrees of both ends of e. We say that the weighting w is virtuous if for each edge e e E we have
We = 0.
Suppose that a list of complex numbers Le is assigned to each e e E. We say that an oriented hypergraph H is t-weight choosable if for any lists satisfying |Le| > t we are able to choose weights we e Le so that w is a virtuous weighting of H. Our main theorem extends the results of [2] and [9] in the following way.
M. Anholcer et al.: Weight choosability of oriented hypergraphs
113
Theorem 1.1. Every oriented hypergraph is 2-weight choosable.
In the next section we will give an algebraic proof of this theorem based on the Combinatorial Nullstellensatz. It is inspired by the approach applied in [9]. In the last section we will speculate on possible consequences of this result for non-oriented hypergraphs, in particular, to the recent intriguing conjecture of Karotiski, Kalkowski, and Pfender [7].
2 Proof of the main result
First recall the celebrated Combinatorial Nullstellensatz of Alon [1].
Theorem 2.1 (Alon). Let K be an arbitrary field, and let F = F (x1,x2,..., xn) be a polynomial in K[x1,x2,..., xn]. Suppose that the total degree of f is n=1 ti, where each ti is a nonnegative integer, and suppose that the coefficient of\{rn=1 x-i is nonzero. If S1,S2,... ,Sn are subsets of K, with |Si| > ti, thenthereare s1 G S1, s2 G S2, ..., sn G Sn so that
F (B1,B2,...,sn)=0.
Let A = (aij )nxn be a square matrix with complex entries. Recall that the permanent of A is defined by:
n
per(A) = £ \\ai^[i),
aeSni=1
where Sn denotes the group of permutations of the set {1, 2,..., n}. This is seemingly almost the same as the determinant of A, only the signs of permutations a are ignored. The following classic result of Schur [11] gives a relation between permanent and determinant of a Hermitian matrix.
Theorem 2.2 (Schur). If A is a positive semi-definite Hermitian matrix, then per(A) > det(A), with equality if and only if A is diagonal or A has a zero row.
Proof of Theorem 1.1. Let H be a hypergraph with n vertices, m edges, and fixed orientation Assume that a list Le with two complex numbers has been assigned to each edge e g E of H, as well as a complex variable xe. Let us define
for each vertex v g V of H, and
^ ^ Mev xe
e3v
Pe 'y ] Mev Pv
for each e G E. Finally, let us define the complex multivariate polynomial
Ph = n Pe.
e •
eEE
We see that H is 2-weight choosable if
Ph (Wei ,We2 , . . .,Wem ) = 0
Pv
100
Ars Math. Contemp. 16 (2019) 97-109
for some choice of weights we G Le, with e G E.
Each monomial in PH has total degree m. We are going to show that the coefficient of
n Xe
eEE
is nonzero. This will finish the proof by Theorem 2.1. Let us expand PH. We have:
Pe "y ] Mev Pv "y ] Mev ^ ] Mfv xf ^ ] Mev ^ ] Mf v xf .
vEe	vEe f3v	v£e f£E
The sums in the last expression are independent, thus we can write
Pe = 53 Mev Mfv xf = 53 53M*ev Mfv xf .
vEe f EE	f EE vGe
Let
mef = 53 MevMfv .
vEe
Let M be the m x m matrix consisting of the mef. From the above definition it follows that M = XX*, where X is the oriented incidence matrix of H, and X* is its conjugate transpose. We have
Pe = 53 mef Xf > fEE
and
Ph = R Pe = H E mef Xf.
eEE	eEE fEE
It follows that the coefficient of
n xe
eE E
is equal to per(M). So, it is enough to prove that per(M) = 0 (see the permanent lemma in [1]). To get this we will apply Schur's theorem. First notice that for any complex vector z we have
zMz* = zXX*z* = zX(zX)* = |zX|2 .
As the last number is real and non-negative, M is positive semi-definite. Notice also that by assumption H has no empty edges and Mev =0 for all v G e. Therefore all entries on the main diagonal of M are strictly positive real numbers. In particular, M has no zero row. Hence, if M is not diagonal, then by Schur's theorem we get
per(M) > det(M) > 0.
If M is diagonal, then
per(M) = det(M) = R mee > 0.
eEE
This completes the proof.	□
M. Anholcer et al.: Weight choosability of oriented hypergraphs
113
3 Some applications for uniform hypergraphs
We give two applications of Theorem 1.1 extending some results from [2, 5] and [9]. For simplicity we confine ourselves to uniform hypergraphs with specific orientations defined as follows. Let k > 2 be a fixed positive integer and let Uk denote the multiplicative group of k-th complex roots of unity. If e is a primitive root in Uk, then we may write Uk = {1, e, e2,..., ek-1}.
Let H be a k-uniform hypergraph. Consider a canonical orientation of H given by the mapping ^: E(IH) ^ Uk such that ^(eu) = ^(ev) for every edge e G E and any two vertices u, v G e. Notice that for k = 2 we get the traditional orientation of a simple graph. Recall that a coloring of the vertices of a hypergraph is proper if no edge is monochromatic.
Corollary 3.1. Every canonically oriented k-uniform hypergraph H has an edge weighting with numbers 1, 2 such that weighted vertex degrees give a proper coloring of H.
Proof. Let H be a given k-uniform hypergraph and let ^ be any canonical orientation of H. Assign the lists Le = {1,2} to all edges of H. Then by Theorem 1.1 there exists a virtuous edge weighting w such that we G {1, 2} for every e G E. We claim that this weighting satisfies the assertion of the corollary. Suppose on the contrary that this is not the case, and that there is some edge e = {v1, v2,..., vk} such that all weighted degrees Wv* are equal:
*	Wv! = • • • = Wvfc = W.
This implies that
kk We = ^ M(evi)*Wv* = W ^ M(evi)* = 0, i=i i=i
since
k
^ M(evi)* = 1 + e + ••• + ek-1 = 0. i= 1
This contradicts the virtue of the weighting w.	□
Corollary 3.2. Every k-uniform hypergraph H has a canonical orientation such that cumulated vertex degrees give a proper coloring of H.
Proof. Let H be a given k-uniform hypergraph and let ^ be any of its canonical orientations. Assign the list Le = {1,e} to every edge e G E. Then by Theorem 1.1 there exists a virtuous edge weighting w such that we G {1, e} for every e G E. Consider now a new orientation ^ defined by ^'(ev) = ^(ev)we for every edge ev of the incidence graph IH. We claim that this orientation satisfies the assertion of the corollary. Suppose on the contrary that this is not the case, and that there is some edge e = {v1, v2,..., vk} with all cumulated degrees Dv* equal in orientation
Dvt = • • • = Dvfc = D.
This implies that also weighted degrees Wv* are equal to D, since
Wv* = M(evi)we = ^'(evi) = Dv* = D.
e3v*	e3v*
100
Ars Math. Contemp. 16 (2019) 97-109
In consequence, we get
k
We =	)WVi = D^(evi)*=0,
=1
which contradicts the fact that w is virtuous.	□
4 Discussion
We conclude the paper with pointing on some possible applications of our results to non-oriented problems of "1-2-3" type. Actually, the original 1-2-3 conjecture can be stated in a setting similar to virtuous weightings of oriented hypergraphs. To see this consider a bipartite graph B on bipartition classes X and Y with some signing ^: E(B) ^ {-1, +1}. Let w : X ^ Z be a weighting of one part of B. Then for every vertex y G Y we may define the induced weight of y by
Wy =	w(x)^(xy),
xeN (y)
where N(y) denote the set of neighbors of y. A weighting w is called half-virtuous if Wy = 0 for every y G Y .A natural problem is to find for a given signed graph B, the least integer k such that B has a half-virtuous weighting with w(x) G {1, 2,..., k} for each x g X .It is not hard to see that 1-2-3-conjecture is equivalent to the statement that certain signed bipartite graphs arising from simple graphs have half-virtuous weightings with weights in the range {1,2,3}. Consider a simple graph G and the related bipartite graph BG on bipartition classes X = Y = E(G), with xy G E(BG) whenever x and y are incident edges of G. An appropriate signing ^ is defined so that for a fixed y G Y, the edges xy, x'y G E(BG) have the same sign if and only if x and x' are incident in G to the same end of y. A half-virtuous weighting of BG is then equivalent to a weighting of the edges of G with different sums over edges incident to opposite ends of any given edge.
It is also possible that our results could be useful in a recently introduced version of the 1-2-3 conjecture for (non-oriented) hypergraphs [7]. Let H be a k-uniform hypergraph and let w denote a weighting of its edges. For every vertex v define its weighted degree by
Wv =53 we.
Recall that a proper coloring of H is a coloring of its vertices such that no edge is monochromatic. A hypergraph H is r-weight colorable if there is a weighting w : E(H ) ^ {1,2,..., r} such that the weighted degrees Wv form a proper coloring of H. The following conjecture is stated in [4] (see also [7]).
Conjecture 4.1. Every k-uniform hypergraph (k > 2) with no isolated edges is 3-weight colorable.
The conjecture holds for random uniform hypergraphs in a stronger sense that even non-weighted degrees give a proper coloring, as proved recently in [4]. Another strong support for validity of the conjecture is given in [7], where it is proved that every nontrivial hypergraph (not only uniform) is (2,3)-weight colorable. This means that a proper
M. Anholcer et al.: Weight choosability of oriented hypergraphs
113
coloring of a hypergraph is obtained by using weights {1,2, 3} for the edges, and weights {1, 2} for the vertices, with weighted vertex degrees computed by a formula:
This statement in restriction to simple graphs was formerly proved by Kalkowski in his PhD thesis. Then the result was extended to the list version by Wong and Zhu [12] who applied the Combinatorial Nullstellensatz. This encourages us to conclude the paper with the following general conjecture.
Conjecture 4.2. Every k-uniform hypergraph (k > 2) with no isolated edges is 3-weight choosable.
References
[1]	N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), 7-29, doi:10. 1017/s0963548398003411.
[2]	T. Bartnicki, J. Grytczuk and S. Niwczyk, Weight choosability of graphs, J. Graph Theory 60 (2009), 242-256, doi:10.1002/jgt.20354.
[3]	O. Baudon, J. Bensmail and É. Sopena, An oriented version of the 1-2-3 conjecture, Discuss. Math. Graph Theory 35 (2015), 141-156, doi:10.7151/dmgt.1791.
[4]	P. Bennett, A. Dudek, A. Frieze and L. Helenius, Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs, Electron. J. Combin. 23 (2016), #P2.46, http://www. combinatorics.org/ojs/index.php/eljc/article/view/v2 3i2p4 6.
[5]	M. Borowiecki, J. Grytczuk and M. Pilâniak, Coloring chip configurations on graphs and digraphs, Inform. Process. Lett. 112 (2012), 1-4, doi:10.1016/j.ipl.2011.09.011.
[6]	M. Kalkowski, M. Karonski and F. Pfender, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J. Comb. Theory Ser. B 100 (2010), 347-349, doi:10.1016/j.jctb.2009.06.002.
[7]	M. Kalkowski, M. Karonski and F. Pfender, The 1-2-3-conjecture for hypergraphs, J. Graph Theory 85 (2017), 706-715, doi:10.1002/jgt.22100.
[8]	M. Karonski, T. Luczak and A. Thomason, Édge weights and vertex colours, J. Comb. Theory Ser.B 91 (2004), 151-157, doi:10.1016/j.jctb.2003.12.001.
[9]	M. Khatirinejad, R. Naserasr, M. Newman, B. Seamone and B. Stevens, Digraphs are 2-weight choosable, Electron. J. Combin. 18 (2011), #P21, http://www.combinatorics.org/ ojs/index.php/eljc/article/view/v18i1p21.
[10]	J. Przybylo and M. Wozniak, Total weight choosability of graphs, Electron. J. Combin. 18 (2011), #P112, http://www.combinatorics.org/ojs/index.php/eljc/ article/view/v18i1p112.
[11]	I. Schur, Uber endliche Gruppen und Hermitesche Formen, Math. Z. 1 (1918), 184-207, doi: 10.1007/bf01203611.
[12]	T.-L. Wong and X. Zhu, Évery graph is (2, 3)-choosable, Combinatorica 36 (2016), 121-127, doi:10.1007/s00493-014-3057-8.