Steiner triple systems with high discrepancy
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913959518404608 |
|---|---|
| author | Gishboliner, Lior Glock, Stefan Sgueglia, Amedeo |
| author_facet | Gishboliner, Lior Glock, Stefan Sgueglia, Amedeo |
| contents | In this paper, we initiate the study of discrepancy questions for combinatorial designs. Specifically, we show that, for every fixed $r\ge 3$ and $n\equiv 1,3 \pmod{6}$, any $r$-colouring of the triples on $[n]$ admits a Steiner triple system of order $n$ with discrepancy $Ω(n^2)$. This is not true for $r=2$, but we are able to asymptotically characterise all $2$-colourings which do not contain a Steiner triple system with high discrepancy. The key step in our proofs is a characterization of 3-uniform hypergraphs avoiding a certain natural type of induced subgraphs, contributing to the structural theory of hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23252 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Steiner triple systems with high discrepancy Gishboliner, Lior Glock, Stefan Sgueglia, Amedeo Combinatorics In this paper, we initiate the study of discrepancy questions for combinatorial designs. Specifically, we show that, for every fixed $r\ge 3$ and $n\equiv 1,3 \pmod{6}$, any $r$-colouring of the triples on $[n]$ admits a Steiner triple system of order $n$ with discrepancy $Ω(n^2)$. This is not true for $r=2$, but we are able to asymptotically characterise all $2$-colourings which do not contain a Steiner triple system with high discrepancy. The key step in our proofs is a characterization of 3-uniform hypergraphs avoiding a certain natural type of induced subgraphs, contributing to the structural theory of hypergraphs. |
| title | Steiner triple systems with high discrepancy |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.23252 |