论文标题
繁殖式条件，用于扩展三倍的颜色
Ryser Type Conditions for Extending Colorings of Triples
论文作者
论文摘要
In 1951, Ryser showed that an $n\times n$ array $L$ whose top left $r\times s$ subarray is filled with $n$ different symbols, each occurring at most once in each row and at most once in each column, can be completed to a latin square of order $n$ if and only if the number of occurrences of each symbol in $L$ is at least $r+s-n$.我们证明了呈液体类型的结果，可以扩展3-均匀的超图的部分着色。令$ x，y $为有限套件，$ x \ subsetneq y $和$ | y | \ equiv 0 \ pmod 3 $。我们什么时候可以将$λ\ binom {x} {3} $的（适当）着色扩展（地面上的所有三元组$ x $，每个三个三元组都重复$λ$ times）到$ vinom {y binom {y} {y} {3} $的颜色？有必要在$ \ binom {x} {3} $中至少$ | x | -2 | y |/3 $中的每种颜色的三重三重数。使用HyperGraph Setachments（Combin。prob。Comput。21（2012），483--495），我们就列表着色完整的多编码建立了必要且充分的条件。使用Häggkvist-Janssen的Bound（Combin。prob。Comput。6（1997），295--313），我们表明每种颜色的三重三重数至少为$ | x |/2- |/6 $就足够了。最后，我们通过证明$ | y | \ geq 3 | x | $，那么任何$ q $ - $λ\ binom {x} {3} $的任何$ q $ - 彩色可以嵌入$λ\ binom {x} $ | y | -1} $λ\ bin， $ q \leqλ\ binom {| y | -1} {2}-λ\ binom {| x |} {3}/\ lfloor {| x |/3} \ rfloor $。
In 1951, Ryser showed that an $n\times n$ array $L$ whose top left $r\times s$ subarray is filled with $n$ different symbols, each occurring at most once in each row and at most once in each column, can be completed to a latin square of order $n$ if and only if the number of occurrences of each symbol in $L$ is at least $r+s-n$. We prove a Ryser type result on extending partial coloring of 3-uniform hypergraphs. Let $X,Y$ be finite sets with $X\subsetneq Y$ and $|Y|\equiv 0 \pmod 3$. When can we extend a (proper) coloring of $λ\binom{X}{3}$ (all triples on a ground set $X$, each one being repeated $λ$ times) to a coloring of $λ\binom{Y}{3}$ using the fewest possible number of colors? It is necessary that the number of triples of each color in $\binom{X}{3}$ is at least $|X|-2|Y|/3$. Using hypergraph detachments (Combin. Probab. Comput. 21 (2012), 483--495), we establish a necessary and sufficient condition in terms of list coloring complete multigraphs. Using Häggkvist-Janssen's bound (Combin. Probab. Comput. 6 (1997), 295--313), we show that the number of triples of each color being at least $|X|/2-|Y|/6$ is sufficient. Finally we prove an Evans type result by showing that if $|Y|\geq 3|X|$, then any $q$-coloring of any subset of $λ\binom{X}{3}$ can be embedded into a $λ\binom{|Y|-1}{2}$-coloring of $λ\binom{Y}{3}$ as long as $q\leq λ\binom{|Y|-1}{2}-λ\binom{|X|}{3}/\lfloor{|X|/3}\rfloor$.
