Robust Hamiltonicity
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917880251023360 |
|---|---|
| author | Joos, Felix Lang, Richard Sanhueza-Matamala, Nicolás |
| author_facet | Joos, Felix Lang, Richard Sanhueza-Matamala, Nicolás |
| contents | We study conditions under which a given hypergraph is randomly robust Hamiltonian, which means that a random sparsification of the host graph contains a Hamilton cycle with high probability. Our main contribution provides nearly optimal results whenever the host graph is Hamilton connected in a locally robust sense, which translates to a typical induced subgraph of constant order containing Hamilton paths between any pair of suitable ends.
The proofs are based on the recent breakthrough on Talagrand's conjecture, which reduces the problem to specifying a distribution on the desired guest structure in the (deterministic) host structure. We find such a distribution via a new argument that reduces the problem to the case of perfect matchings in a higher uniformity.
As applications, we obtain asymptotically optimal results for perfect tilings in graphs and hypergraphs both in the minimum degree and uniformly dense setting. We also prove random robustness for powers of cycles under asymptotically optimal minimum degrees and degree sequences. We solve the problem for loose and tight Hamilton cycles in hypergraphs under a range of asymptotic minimum degree conditions. This includes in particular $k$-uniform tight Hamilton cycles under minimum $d$-degree conditions for $1\leq k-d \leq 3$. In all cases, our bounds on the sparseness are essentially best-possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15262 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Robust Hamiltonicity Joos, Felix Lang, Richard Sanhueza-Matamala, Nicolás Combinatorics 05D15, 05D40, 05C35, 05C65, 05C70, 05C45 G.2.2 We study conditions under which a given hypergraph is randomly robust Hamiltonian, which means that a random sparsification of the host graph contains a Hamilton cycle with high probability. Our main contribution provides nearly optimal results whenever the host graph is Hamilton connected in a locally robust sense, which translates to a typical induced subgraph of constant order containing Hamilton paths between any pair of suitable ends. The proofs are based on the recent breakthrough on Talagrand's conjecture, which reduces the problem to specifying a distribution on the desired guest structure in the (deterministic) host structure. We find such a distribution via a new argument that reduces the problem to the case of perfect matchings in a higher uniformity. As applications, we obtain asymptotically optimal results for perfect tilings in graphs and hypergraphs both in the minimum degree and uniformly dense setting. We also prove random robustness for powers of cycles under asymptotically optimal minimum degrees and degree sequences. We solve the problem for loose and tight Hamilton cycles in hypergraphs under a range of asymptotic minimum degree conditions. This includes in particular $k$-uniform tight Hamilton cycles under minimum $d$-degree conditions for $1\leq k-d \leq 3$. In all cases, our bounds on the sparseness are essentially best-possible. |
| title | Robust Hamiltonicity |
| topic | Combinatorics 05D15, 05D40, 05C35, 05C65, 05C70, 05C45 G.2.2 |
| url | https://arxiv.org/abs/2312.15262 |