On high discrepancy $1$-factorizations of complete graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912286056120320 |
|---|---|
| author | Ai, Jiangdong He, Fankang Im, Seonghyuk Lee, Hyunwoo |
| author_facet | Ai, Jiangdong He, Fankang Im, Seonghyuk Lee, Hyunwoo |
| contents | We proved that for every sufficiently large $n$, the complete graph $K_{2n}$ with an arbitrary edge signing $σ: E(K_{2n}) \to \{-1, +1\}$ admits a high discrepancy $1$-factor decomposition. That is, there exists a universal constant $c > 0$ such that every edge-signed $K_{2n}$ has a perfect matching decomposition $\{ψ_1, \ldots, ψ_{2n-1}\}$, where for each perfect matching $ψ_i$, the discrepancy $\lvert \frac{1}{n} \sum_{e\in E(ψ_i)} σ(e) \rvert$ is at least $c$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17176 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On high discrepancy $1$-factorizations of complete graphs Ai, Jiangdong He, Fankang Im, Seonghyuk Lee, Hyunwoo Combinatorics We proved that for every sufficiently large $n$, the complete graph $K_{2n}$ with an arbitrary edge signing $σ: E(K_{2n}) \to \{-1, +1\}$ admits a high discrepancy $1$-factor decomposition. That is, there exists a universal constant $c > 0$ such that every edge-signed $K_{2n}$ has a perfect matching decomposition $\{ψ_1, \ldots, ψ_{2n-1}\}$, where for each perfect matching $ψ_i$, the discrepancy $\lvert \frac{1}{n} \sum_{e\in E(ψ_i)} σ(e) \rvert$ is at least $c$. |
| title | On high discrepancy $1$-factorizations of complete graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.17176 |