Two remarks on graph norms

DOI10.1007/S00454-021-00280-WMaRDI QIDQ2118224zbMATHOpenAlexFDO

Authors Frederik Garbe, Jan Hladký, Joonkyung Lee

Publication date 22 March 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph limitsgraphonsgraph norms

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• Finite reflection groups and graph norms
• Graph norms and Sidorenko's conjecture
• Large networks and graph limits
• Limits of dense graph sequences
• Quasi-random graphs
• Relating the cut distance and the weak* topology for graphons
• Sidorenko's conjecture for blow-ups
• The step Sidorenko property and non-norming edge-transitive graphs

Cited in

(7)

• Convex graphon parameters and graph norms
• Domination inequalities and dominating graphs
• Graph norms and Sidorenko's conjecture
• Weakly norming graphs are edge-transitive
• Finite reflection groups and graph norms
• A note on projective norm graphs
• On graph norms for complex‐valued functions

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)