FGFrederik Garbe

Frederik Garbe

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Frederik Garbe has a total of 3 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Two Remarks on Graph Norms

    by Frederik Garbe, Jan Hladký, Joonkyung Lee

    For a graph H, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions W in $$L^p$$ L p , $$p\ge e(H)$$ p ≥ e ( H ) , denoted by t(H, W). One may then define corresponding functionals $$\Vert W\Vert _{H}\,{:}{=}\,|t(H,W)|^{1/e(H)}$$ ‖ W ‖ H : = | t ( H , W ) | 1 / e ( H ) and $$\Vert W\Vert _{r(H)}\,{:}{=}\,t(H,|W|)^{1/e(H)}$$ ‖ W ‖ r ( H ) : = t ( H , | W | ) 1 / e ( H ) , and say that H is (semi-)norming if $$\Vert \,{\cdot }\,\Vert _{H}$$ ‖ · ‖ H is a (semi-)norm and that H is weakly norming if $$\Vert \,{\cdot }\,\Vert _{r(H)}$$ ‖ · ‖ r ( H ) is a norm. We obtain two results that contribute to the theory of (weakly) norming graphs. Firstly, answering a question of Hatami, who estimated the modulus of convexity and smoothness of $$\Vert \,{\cdot }\,\Vert _{H}$$ ‖ · ‖ H , we prove that $$\Vert \,{\cdot }\,\Vert _{r(H)}$$ ‖ · ‖ r ( H ) is neither uniformly convex nor uniformly smooth, provided that H is weakly norming. Secondly, we prove that every graph H without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of H when studying graph norms. In particular, we correct a negligence in the original statement of the aforementioned theorem by Hatami.


  • Open Access

    Hamilton cycles in hypergraphs below the Dirac threshold

    by Frederik Garbe, Richard Mycroft

    We establish a precise characterisation of $4$-uniform hypergraphs with minimum codegree close to $n/2$ which contain a Hamilton $2$-cycle. As an immediate corollary we identify the exact Dirac threshold for Hamilton $2$-cycles in $4$-uniform hypergraphs. Moreover, by derandomising the proof of our characterisation we provide a polynomial-time algorithm which, given a $4$-uniform hypergraph $H$ with minimum codegree close to $n/2$, either finds a Hamilton $2$-cycle in $H$ or provides a certificate that no such cycle exists. This surprising result stands in contrast to the graph setting, in which below the Dirac threshold it is NP-hard to determine if a graph is Hamiltonian. We also consider tight Hamilton cycles in $k$-uniform hypergraphs $H$ for $k \geq 3$, giving a series of reductions to show that it is NP-hard to determine whether a $k$-uniform hypergraph $H$ with minimum degree $\delta(H) \geq \frac{1}{2}|V(H)| - O(1)$ contains a tight Hamilton cycle. It is therefore unlikely that a similar characterisation can be obtained for tight Hamilton cycles.