Toward a Three-dimensional Counterpart of Cruse's Theorem
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912585032400896 |
|---|---|
| author | Bahmanian, Amin |
| author_facet | Bahmanian, Amin |
| contents | Completing partial latin squares is NP-complete. Motivated by Ryser's theorem for latin rectangles, in 1974, Cruse found conditions that ensure a partial symmetric latin square of order $m$ can be embedded in a symmetric latin square of order $n$. Loosely speaking, this results asserts that an $n$-coloring of the edges of the complete $m$-vertex graph $K_m$ can be embedded in a one-factorization of $K_n$ if and only if $n$ is even and the number of edges of each color is at least $m-n/2$. We establish necessary and sufficient conditions under which an edge-coloring of the complete $λ$-fold $m$-vertex 3-graph $λK_m^3$ can be embedded in a one-factorization of $λK_n^3$. In particular, we prove the first known Ryser type theorem for hypergraphs by showing that if $n \equiv 0 \;(\bmod\; 3)$, any edge-coloring of $λK_m^3$ where the number of triples of each color is at least $m/2-n/6$, can be embedded in a one-factorization of $λK_n^3$. Finally we prove an Evans type result by showing that if $n \equiv 0 \;(\bmod\; 3)$ and $n\geq 3m$, then any $q$-coloring of the edges of any $F\subseteqλK_m^3$ can be embedded in a one-factorization of $λK_n^3$ as long as $q\leq λ\binom{n-1}{2}-λ\binom{m}{3}/\left\lfloor m/3 \right\rfloor$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_09100 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Toward a Three-dimensional Counterpart of Cruse's Theorem Bahmanian, Amin Combinatorics 05B15, 05C70, 05C65, 05C15 Completing partial latin squares is NP-complete. Motivated by Ryser's theorem for latin rectangles, in 1974, Cruse found conditions that ensure a partial symmetric latin square of order $m$ can be embedded in a symmetric latin square of order $n$. Loosely speaking, this results asserts that an $n$-coloring of the edges of the complete $m$-vertex graph $K_m$ can be embedded in a one-factorization of $K_n$ if and only if $n$ is even and the number of edges of each color is at least $m-n/2$. We establish necessary and sufficient conditions under which an edge-coloring of the complete $λ$-fold $m$-vertex 3-graph $λK_m^3$ can be embedded in a one-factorization of $λK_n^3$. In particular, we prove the first known Ryser type theorem for hypergraphs by showing that if $n \equiv 0 \;(\bmod\; 3)$, any edge-coloring of $λK_m^3$ where the number of triples of each color is at least $m/2-n/6$, can be embedded in a one-factorization of $λK_n^3$. Finally we prove an Evans type result by showing that if $n \equiv 0 \;(\bmod\; 3)$ and $n\geq 3m$, then any $q$-coloring of the edges of any $F\subseteqλK_m^3$ can be embedded in a one-factorization of $λK_n^3$ as long as $q\leq λ\binom{n-1}{2}-λ\binom{m}{3}/\left\lfloor m/3 \right\rfloor$. |
| title | Toward a Three-dimensional Counterpart of Cruse's Theorem |
| topic | Combinatorics 05B15, 05C70, 05C65, 05C15 |
| url | https://arxiv.org/abs/2209.09100 |