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
Research Subjects
Frederik Garbe has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Jan Hladký
Institute of Computer Science Czech Academy of Sciences Prague Czechia
1 shared publication - Joonkyung Lee
Department of Mathematics University College London Gower Street WC1E 6BT London UK
1 shared publication - Richard Mycroft
School of Mathematics University of Birmingham UK
1 shared publication
Latest Publications
- Open Access
- 16 February 2021
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 67 (3) , 919-929
Two Remarks on Graph Norms
For a graph H, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions W in $$L^p$$ , $$p\ge e(H)$$ , denoted by t(H, W). One may then define corresponding functionals $$\Vert W\Vert _{H}\,{:}{=}\,|t(H,W)|^{1/e(H)}$$ and $$\Vert W\Vert _{r(H)}\,{:}{=}\,t(H,|W|)^{1/e(H)}$$ , and say that H is (semi-)norming if $$\Vert \,{\cdot }\,\Vert _{H}$$ is a (semi-)norm and that H is weakly norming if $$\Vert \,{\cdot }\,\Vert _{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}$$ , we prove that $$\Vert \,{\cdot }\,\Vert _{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.- 16 February 2021
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 67 (3) , 919-929
Open AccessTwo Remarks on Graph Norms
For a graph H, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions W in $$L^p$$ , $$p\ge e(H)$$ , denoted by t(H, W). One may then define corresponding functionals $$\Vert W\Vert _{H}\,{:}{=}\,|t(H,W)|^{1/e(H)}$$ and $$\Vert W\Vert _{r(H)}\,{:}{=}\,t(H,|W|)^{1/e(H)}$$ , and say that H is (semi-)norming if $$\Vert \,{\cdot }\,\Vert _{H}$$ is a (semi-)norm and that H is weakly norming if $$\Vert \,{\cdot }\,\Vert _{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}$$ , we prove that $$\Vert \,{\cdot }\,\Vert _{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
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.Open AccessHamilton cycles in hypergraphs below the Dirac threshold
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.