Two remarks on graph norms

DOI10.1007/S00454-021-00280-WzbMATH Open1485.05175arXiv1909.10987OpenAlexW3130482887MaRDI QIDQ2118224FDOQ2118224

Jan Hladký, Joonkyung Lee, Frederik Garbe

Publication date: 22 March 2022

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $pgeqe(H)$, denoted by $t(H,W)$. One may then define corresponding functionals $|W{|}_H:=|t(H,W){|}^{1/e(H)}$ and $|W{|}_{r(H)}:=t(H,|W|{)}^{1/e(H)}$ and say that $H$ is (semi-)norming if $|.{|}_H$ is a (semi-)norm and that $H$ is weakly norming if $|.{|}_{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 $|.{|}_H$, we prove that $|.{|}_{r(H)}$ is not 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 an error in the original statement of the aforementioned theorem by Hatami.

Full work available at URL: https://arxiv.org/abs/1909.10987

Recommendations

• Graph norms and Sidorenko's conjecture
• Norms and perfect graphs
• scientific article
• Norm-graphs: Variations and applications
• Some remarks on the theory of graphs
• scientific article; zbMATH DE number 7561533
• A note on projective norm graphs
• Perfect graphs and norms
• Extremal norms of graphs and matrices
• scientific article; zbMATH DE number 3924817

zbMATH Keywords

graph limitsgraphonsgraph norms

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Density (toughness, etc.) (05C42) Graph theory (05C99)

Cites Work

• Limits of dense graph sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quasi-random graphs
• Graph norms and Sidorenko's conjecture
• Finite reflection groups and graph norms
• The step Sidorenko property and non-norming edge-transitive graphs
• Relating the cut distance and the weak* topology for graphons
• Sidorenko's conjecture for blow-ups

Cited In (3)

• On graph norms for complex‐valued functions
• A note on projective norm graphs
• Domination inequalities and dominating graphs

This page was built for publication: Two remarks on graph norms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118224)