Two-Coloring Triples such that in Each Color Class Every Element is Missed at Least Once
- PDF / 341,637 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 160 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Two-Coloring Triples such that in Each Color Class Every Element is Missed at Least Once Bala´zs Keszegh1 Received: 6 October 2019 / Revised: 6 July 2020 Ó The Author(s) 2020
Abstract We give a characterization of finite sets of triples of elements (e.g., positive integers) that can be colored with two colors such that for every element i in each color class there exists a triple which does not contain i. We give a linear (in the number of triples) time algorithm to decide if such a coloring exists and find one if it does. We also consider generalizations of this result and an application to a matching problem, which motivated this study. Finally, we show how these results translate to results about colorings of hypergraphs in which the degree of every vertex is k less than the number of hyperedges. Keywords Hypergraph Coloring Matching Algorithm
1 Introduction For positive integers k and n we are given a finite multiset of n many k-tuples1 of characters from an alphabet such that every triple consists of three different characters. From now on a ‘set of k-tuples’ always refers to such a finite multiset of k-tuples. We also refer to the characters as elements. Two sets of k-tuples is said to be equivalent if there is a bijection between their alphabets which induces a bijection between the two sets of k-tuples. We do not want to distinguish equivalent sets of k-tuples, thus without loss of generality we can assume that the elements are positive integers from ½m ¼ f1; . . .; mg for some m and each of these m numbers is present in at least one k-tuple. If a k-tuple does not contain the element i we say that the k-tuple avoids i (e.g., f1; 2; 3g avoids 4 but does not avoid 2). 1 A k-tuple simply denotes a set of size k, .e.g., f1; 2; 3g is a 3-tuple, also referred to as a triple. Note that repetition of elements is not allowed and the order of the elements does not matter.
& Bala´zs Keszegh [email protected] 1
Alfre´d Re´nyi Institute of Mathematics and MTA-ELTE Lendu¨let Combinatorial Geometry Research Group, Budapest, Hungary
123
Graphs and Combinatorics
A c-coloring2 of a set of tuples (of numbers from [m]) is a nice c-coloring if for each of the c colors and for every i 2 ½m there is a tuple of that color that avoids i. Similarly, a partial c-coloring of a set of tuples (that is, not all tuples need to be colored) is a nice partial c-coloring if for each of the c colors and for every i 2 ½m there is a tuple of that color that avoids i. Notice that a nice partial c-coloring can always be extended to a nice c-coloring by coloring arbitrarily all the tuples that are uncolored in the partial c-coloring. We are in particular interested in nice two-colorings of triples, that is, our aim is to two-color (with colors red and blue) a set of triples such that for each of the two colors and for every i 2 ½m there is a triple of that color that avoids i. Our main result is a characterization of the sets of triples that admit a nice (partial) 2-colori
Data Loading...
