Weight choosability of oriented hypergraphs - Anholcer, Marcin (Ars mathematica contemporanea, 2019)
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 I. Schur Math. Z. 1, 184--207 (1918) 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: 1-2-3 conjecture; 1-2-3 domneva; combinatorial nullstellensatz; kombinatorični izrek o položaju ničel; list weighting; oriented hypergraphs; orientirani hipergrafi; ponderiranje seznama