Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912044368789504 |
|---|---|
| author | Molloy, Michael Pralat, Pawel Sorkin, Gregory B. |
| author_facet | Molloy, Michael Pralat, Pawel Sorkin, Gregory B. |
| contents | We study the 2-offer semirandom 3-uniform hypergraph model on $n$ vertices. At each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creating a hyperedge of size 3. We show a strategy that constructs a perfect matching, and another that constructs a loose Hamilton cycle, both succeeding asymptotically almost surely within $Θ(n)$ steps. Both results extend to $s$-uniform hypergraphs. The challenges with hypergraphs, and our methods, are qualitatively different from what has been seen for semirandom graphs. Much of our analysis is done on an auxiliary graph that is a uniform $k$-out subgraph of a random bipartite graph, and this tool may be useful in other contexts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00559 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model Molloy, Michael Pralat, Pawel Sorkin, Gregory B. Combinatorics We study the 2-offer semirandom 3-uniform hypergraph model on $n$ vertices. At each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creating a hyperedge of size 3. We show a strategy that constructs a perfect matching, and another that constructs a loose Hamilton cycle, both succeeding asymptotically almost surely within $Θ(n)$ steps. Both results extend to $s$-uniform hypergraphs. The challenges with hypergraphs, and our methods, are qualitatively different from what has been seen for semirandom graphs. Much of our analysis is done on an auxiliary graph that is a uniform $k$-out subgraph of a random bipartite graph, and this tool may be useful in other contexts. |
| title | Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.00559 |