Majority Edge Colouring of Hypergraph
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911551781339136 |
|---|---|
| author | Ai, Jiangdong Nan, Feiyu |
| author_facet | Ai, Jiangdong Nan, Feiyu |
| contents | Motivated by recent work on majority edge-colourings of graphs, we initiate the study of the corresponding problem for hypergraphs. First, sharpening the probabilistic argument by a $KL$ large-deviation estimate, we obtain a sufficient minimum-degree condition of order $k^3\log(kr)$ with the sharp large-deviation constant $
I_k:=D\!\left(\frac1k\middle\|\frac1{k+1}\right)=Θ(k^{-3}), $
where $D(\cdot\|\cdot)$ denotes the binary relative entropy. Our main constructive result shows that every hypergraph of rank at most $r$ and minimum degree at least $2rk^2$ admits a $1/k$-majority $(k+1)$-edge-colouring. The proof is based on a hypergraph extension of the key discrepancy lemma used in the graph case.
We also show that the logarithmic dependence on the rank can be determined asymptotically. If $μ_k(r)$ denotes the least minimum-degree threshold that guarantees a $1/k$-majority $(k+1)$-edge-colouring for all hypergraphs of rank at most $r$, then for every fixed $k\ge2$, $
μ_k(r)=\frac{\log r}{I_k}+O_k(\log\log r). $
In particular, the correct logarithmic threshold is of order $k^3\log r$.
Finally, we determine the correct order of the degree--colour trade-off. For integers $k\ge2$, $p\ge1$, and $r\ge2$, let $ν_{k,p}(r)$ denote the least integer $q$ such that every hypergraph of rank at most $r$ and minimum degree at least $kp$ admits a $1/k$-majority $q$-edge-colouring. Then $
ν_{k,p}(r)=Θ_{k,p}(r^{1/p}). $
In particular, minimum degree at least $k^2-k$ guarantees a $1/k$-majority $O_k(r^{1/(k-1)})$-edge-colouring, and this exponent is best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22157 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Majority Edge Colouring of Hypergraph Ai, Jiangdong Nan, Feiyu Combinatorics Motivated by recent work on majority edge-colourings of graphs, we initiate the study of the corresponding problem for hypergraphs. First, sharpening the probabilistic argument by a $KL$ large-deviation estimate, we obtain a sufficient minimum-degree condition of order $k^3\log(kr)$ with the sharp large-deviation constant $ I_k:=D\!\left(\frac1k\middle\|\frac1{k+1}\right)=Θ(k^{-3}), $ where $D(\cdot\|\cdot)$ denotes the binary relative entropy. Our main constructive result shows that every hypergraph of rank at most $r$ and minimum degree at least $2rk^2$ admits a $1/k$-majority $(k+1)$-edge-colouring. The proof is based on a hypergraph extension of the key discrepancy lemma used in the graph case. We also show that the logarithmic dependence on the rank can be determined asymptotically. If $μ_k(r)$ denotes the least minimum-degree threshold that guarantees a $1/k$-majority $(k+1)$-edge-colouring for all hypergraphs of rank at most $r$, then for every fixed $k\ge2$, $ μ_k(r)=\frac{\log r}{I_k}+O_k(\log\log r). $ In particular, the correct logarithmic threshold is of order $k^3\log r$. Finally, we determine the correct order of the degree--colour trade-off. For integers $k\ge2$, $p\ge1$, and $r\ge2$, let $ν_{k,p}(r)$ denote the least integer $q$ such that every hypergraph of rank at most $r$ and minimum degree at least $kp$ admits a $1/k$-majority $q$-edge-colouring. Then $ ν_{k,p}(r)=Θ_{k,p}(r^{1/p}). $ In particular, minimum degree at least $k^2-k$ guarantees a $1/k$-majority $O_k(r^{1/(k-1)})$-edge-colouring, and this exponent is best possible. |
| title | Majority Edge Colouring of Hypergraph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.22157 |