The core in random hypergraphs and local weak convergence
Palestrante: Kathrin Skubch (U. Frankfurt)
Onde e quando: Auditório NUMEC, quinta-feira 4/02, às 14:00 (note a data diferente!)
Resumo:
The degree of a vertex in a hypergraph is defined as the number of edges incident to it. In this paper we study the \(k\)-core, defined as the maximal induced subhypergraph of minimum degree \(k\), of the random \(r\)-uniform hypergraph \({\vec H}_r(n,p)\) for \(r\geq 3\). We consider the case \(k\geq 2\) and \(p=d/n^{r-1}\) for which every vertex has fixed average degree \(d>0\). We derive a multi-type branching process that describes the local structure of the \(k\)-core together with the mantle, i.e. the vertices outside the core.
Universality in random and sparse hypergraphs
Palestrante: Olaf Parczyk (Johann Wolfgang Goethe-Universität)
Onde e quando: Auditório Antonio Gilioli, sexta-feira 15/01 às 14:00.
Resumo:
Finding spanning subgraphs is a well studied problem in random graph theory, in the case of hypergraphs less is known and it is natural to study the corresponding spanning problems for random hypergraphs. We study universality, i.e. when does an r-uniform hypergraph contain any hypergraph on n vertices and with maximum vertex degree bounded by \(\Delta\)?
For \(H^r(n,p)\) we show that this holds for \(p= \omega ((\ln n / n)^{1/\Delta})\) a.a.s. Furthermore we derive from explicit constructions of universal graphs due to Alon, Capalbo constructions of universal hypergraphs of size almost matching the lower bound \(\Omega (n^{r-r/ \Delta})\).
This is joint work with Samuel Hetterich and Yury Person.
Minimum \((k-2)\)-degree conditions for Hamiltonian \(\ell\)-cycles in \(k\)-uniform hypergraphs
Palestrante: Jakob Schnitzer (Hamburg Universität)
Onde e quando: Auditório Antonio Gilioli, sexta-feira 15/01 às 15:20.
Resumo:
We study minimum \((k-2)\)-degree conditions for \(k\)-uniform hypergraphs which ensure the existence of Hamiltonian \(\ell\)-cycles, where \(\ell < k/2\). We show that every \(k\)-uniform hypergraph \(H\) on \(n\) vertices with \(\delta_{k-2}(H) \geq (\frac{4(k-\ell)-1}{4(k-\ell)^2}+o(1)){n\choose 2}\) contains a Hamiltonian \(\ell\)-cycle if \(k-\ell\) divides \(n\). This bound is asymptotically best possible.
This is joint work with Josefran Bastos, Guilherme Oliveira Mota, Mathias Schacht and Fabian Schulenburg.