286 KB15 KB200820252019Anholcer, MarcinBosek, BartłomiejGrytczuk, Jarosławštevilka:1letnik:16str. 111-117ISSN:1855-3966COBISSID_HOST:18703193URN:URN:NBN:SI:doc-KDW545IQenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporanea1-2-3 conjecture1-2-3 domnevacombinatorial nullstellensatzkombinatorični izrek o položaju ničellist weightingoriented hypergraphsorientirani hipergrafiponderiranje seznamaWeight choosability of oriented hypergraphs|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 hypergraphs1-2-3 domneva izjavlja, da za vsak enostaven graf (brez izoliranih povezav) obstaja obtežitev povezav s števili 1, 2, 3, tako da rezultirajoče utežene stopnje vozlišč tvorijo pravilno barvanje grafa. Raziskujemo podoben problem za orientirane hipergrafe. Dokažemo, da ima vsak orientiran hipergraf obtežitev povezav, ki zadošča podobnemu pogoju, tudi če je uteži treba izbirati iz poljubnega seznama dolžine dve. Dokaz je osnovan na kombinatoričnem izreku o položajih ničel in Schurovem izreku za permanente pozitivnih semi-definitnih matrik. Izpeljemo več posledic glavnega rezultata za uniformne hipergrafe. Opozorimo tudi na možne uporabe naših rezultatov pri problemih tipa 1-2-3 za neorientirane hipergrafeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije