Graded discrepancy of graphs and hypergraphs
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_ | 1866918303097683968 |
|---|---|
| author | Chen, Yanling Huang, Shuping Zeng, Qinghou |
| author_facet | Chen, Yanling Huang, Shuping Zeng, Qinghou |
| contents | This paper studies the following question of Bollobás and Scott: Let $G$ be a graph with $n$ vertices and $p\binom{n}{2}$ edges. What is the smallest $c(p, n)$ such that there is an ordering $v_1, \ldots, v_n$ of the vertices in $G$ with $\left|e(\{v_1, \ldots, v_i\})-p\binom{i}{2}\right|\leq c(p, n)$ for all $i\in \{1,\ldots,n\}$ ? We obtain upper and lower bounds for $c(p,n)$ that are both linear in $n$. Furthermore, we generalize the result to $k$-uniform hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21690 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graded discrepancy of graphs and hypergraphs Chen, Yanling Huang, Shuping Zeng, Qinghou Combinatorics This paper studies the following question of Bollobás and Scott: Let $G$ be a graph with $n$ vertices and $p\binom{n}{2}$ edges. What is the smallest $c(p, n)$ such that there is an ordering $v_1, \ldots, v_n$ of the vertices in $G$ with $\left|e(\{v_1, \ldots, v_i\})-p\binom{i}{2}\right|\leq c(p, n)$ for all $i\in \{1,\ldots,n\}$ ? We obtain upper and lower bounds for $c(p,n)$ that are both linear in $n$. Furthermore, we generalize the result to $k$-uniform hypergraphs. |
| title | Graded discrepancy of graphs and hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.21690 |