Improved Bounds for Multicovering Hypergraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917523940704256 |
|---|---|
| author | Babu, Anand Vishwanathan, Sundar |
| author_facet | Babu, Anand Vishwanathan, Sundar |
| contents | The minimum number of bicliques needed to cover the edge set of the complete graph on $n$ vertices is $\lceil \log_2 n \rceil$. The Graham-Pollak theorem states that at least $n-1$ bicliques are required to partition the edge set of the complete graph on $n$ vertices. In this paper, we provide improvements for the generalizations of coverings of graphs and hypergraphs for some specific multiplicities. We also study an extension of the Katona-Szemerédi theorem to $r$-uniform hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_12589 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Improved Bounds for Multicovering Hypergraphs Babu, Anand Vishwanathan, Sundar Combinatorics 05C35, 68R10 The minimum number of bicliques needed to cover the edge set of the complete graph on $n$ vertices is $\lceil \log_2 n \rceil$. The Graham-Pollak theorem states that at least $n-1$ bicliques are required to partition the edge set of the complete graph on $n$ vertices. In this paper, we provide improvements for the generalizations of coverings of graphs and hypergraphs for some specific multiplicities. We also study an extension of the Katona-Szemerédi theorem to $r$-uniform hypergraphs. |
| title | Improved Bounds for Multicovering Hypergraphs |
| topic | Combinatorics 05C35, 68R10 |
| url | https://arxiv.org/abs/2208.12589 |