Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.00427 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913513293742080 |
|---|---|
| author | Louis, Anand Newman, Alantha Ray, Arka |
| author_facet | Louis, Anand Newman, Alantha Ray, Arka |
| contents | We consider the problem of linearly ordered (LO) coloring of hypergraphs. A hypergraph has an LO coloring if there is a vertex coloring, using a set of ordered colors, so that (i) no edge is monochromatic, and (ii) each edge has a unique maximum color. It is an open question as to whether or not a 2-LO colorable 3-uniform hypergraph can be LO colored with 3 colors in polynomial time. Nakajima and Živný recently gave a polynomial-time algorithm to color such hypergraphs with $\widetilde{O}(n^{1/3})$ colors and asked if SDP methods can be used directly to obtain improved bounds. Our main result is to show how to use SDP-based rounding methods to produce an LO coloring with $\widetilde{O}(n^{1/5})$ colors for such hypergraphs. We show how to reduce the problem to cases with highly structured SDP solutions, which we call balanced hypergraphs. Then, we discuss how to apply classic SDP-rounding tools to obtain improved bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00427 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved linearly ordered colorings of hypergraphs via SDP rounding Louis, Anand Newman, Alantha Ray, Arka Data Structures and Algorithms We consider the problem of linearly ordered (LO) coloring of hypergraphs. A hypergraph has an LO coloring if there is a vertex coloring, using a set of ordered colors, so that (i) no edge is monochromatic, and (ii) each edge has a unique maximum color. It is an open question as to whether or not a 2-LO colorable 3-uniform hypergraph can be LO colored with 3 colors in polynomial time. Nakajima and Živný recently gave a polynomial-time algorithm to color such hypergraphs with $\widetilde{O}(n^{1/3})$ colors and asked if SDP methods can be used directly to obtain improved bounds. Our main result is to show how to use SDP-based rounding methods to produce an LO coloring with $\widetilde{O}(n^{1/5})$ colors for such hypergraphs. We show how to reduce the problem to cases with highly structured SDP solutions, which we call balanced hypergraphs. Then, we discuss how to apply classic SDP-rounding tools to obtain improved bounds. |
| title | Improved linearly ordered colorings of hypergraphs via SDP rounding |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.00427 |