Tipus de document
Treball de fi de màsterData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/230506
Loose cycles in the budget-constrained random hypergraph process
Títol de la revista
Autors
Director/Tutor
Contribució addicional
ISSN de la revista
Títol del volum
Resum
We consider a model of a controlled random graph process introduced by Frieze, Krivelevich and Michaeli. In this model, the edges of the complete graph $K_n$ are ordered randomly and then revealed, one by one, to a player called Builder. She must decide, immediately and irrevocably, whether to purchase an edge. The observation time is bounded by the parameter $t$, and the total budget of purchased edges is bounded by the parameter $b$. Frieze, Krivelevich and Michaeli prove that Builder has a strategy to create a copy of a cycle of length $\ell$ with high probability if $b \gg \max\{n^{k+2/\ell}t^{-1+1/\ell}, n/\sqrt{t}\}$, and this is optimal. We deconstruct their proof and use it as a blueprint for proving an analogous result for loose cycles in uniform hypergraphs. We also show that when $t \gg n^2$, Builder can construct a loose cycle of length $\ell$ with high probability purchasing exactly $\ell$ edges.
Descripció
Treballs finals del Màster en Matemàtica Avançada, Facultat de Matemàtiques, Universitat de Barcelona: Any: 2026. Director: Alberto Espuny Díaz
Recurs relacionat
Matèries (anglès)
Citació
Col·leccions
Citació
ANDRIESSE, Eros. Loose cycles in the budget-constrained random hypergraph process. [consulted: 28 of October of 2026]. Available at: https://hdl.handle.net/2445/230506