Abstract 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.

Given integers $k,j$ with $1\le j \le k-1$, we consider the length of the longest $j$-tight path in the binomial random $k$-uniform hypergraph $H^k(n,p)$. We show that this length undergoes a phase transition from logarithmic length to linear and determine the critical threshold, as well as proving upper and lower bounds on the length in the subcritical and supercritical ranges. In particular, for the supercritical case we introduce the \tt Pathfinder algorithm, a depth-first search algorithm which discovers $j$-tight paths in a $k$-uniform hypergraph. We prove that, in the supercritical case, with high probability this algorithm will find a long $j$-tight path.

We consider the complexity of the Hamilton cycle decision problem when restricted to k-uniform hypergraphs H of high minimum codegree delta(H). We show that for tight Hamilton cycles this problem is NP-hard even when restricted to k-uniform hypergraphs H with delta(H) >= n/2 - C, where n is the order of H and C is a constant which depends only on k. This answers a question raised by Karpinski, Rucinski and Szymanska. Additionally we give a polynomial-time algorithm which, for a sufficiently small constant epsilon > 0, determines whether or not a 4-uniform hypergraph H on n vertices with delta(H) >= n/2 - epsilon * n contains a Hamilton 2-cycle. This demonstrates that some looser Hamilton cycles exhibit interestingly different behaviour compared to tight Hamilton cycles. A key part of the proof is a precise characterisation of all 4-uniform hypergraphs H on n vertices with delta(H) >= n/2 - epsilon * n which do not contain a Hamilton 2-cycle; this may be of independent interest. As an additional corollary of this characterisation, we obtain an exact Dirac-type bound for the existence of a Hamilton 2-cycle in a large 4-uniform hypergraph.