On graph norms for complex‐valued functions

DOI10.1112/JLMS.12604MaRDI QIDQ6134515zbMATH OpenOpenAlexFDO

Authors Joonkyung Lee, Alexander Sidorenko

Publication date 22 August 2023

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

edge-transitive graphnorming graphweakly norming graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Abstract: For any given graph $H$, one may define a natural corresponding functional $|.{|}_H$ for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions, once $H$ is paired with a $2$-edge-colouring $alpha$ to assign conjugates. We say that $H$ is real-norming (resp. complex-norming) if $|.{|}_H$ (resp. $|.{|}_{H,alpha}$ for some $alpha$) is a norm on the vector space of real-valued (resp. complex-valued) functions. These generalise the Gowers octahedral norms, a widely used tool in extremal combinatorics to quantify quasirandomness. We unify these two seemingly different notions of graph norms in real- and complex-valued settings. Namely, we prove that $H$ is complex-norming if and only if it is real-norming and simply call the property norming. Our proof does not explicitly construct a suitable $2$-edge-colouring $alpha$ but obtains its existence and uniqueness, which may be of independent interest. As an application, we give various example graphs that are not norming. In particular, we show that hypercubes are not norming, which resolves the last outstanding problem posed in Hatami's pioneering work on graph norms.

Recommendations

• Two remarks on graph norms
• Finite reflection groups and graph norms
• Graph norms and Sidorenko's conjecture
• Perfect graphs and norms
• \(L_p\) regular sparse hypergraphs: box norms

Cites work

• A new proof of Szemerédi's theorem
• All self-complementary symmetric graphs
• An algebraic characterization of finite symmetric tournaments
• Convex graphon parameters and graph norms
• Edge-transitive homogeneous factorizations of complete uniform hypergraphs
• Finite reflection groups and graph norms
• Graph norms and Sidorenko's conjecture
• Graph theory
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Large networks and graph limits
• Limits of dense graph sequences
• On the interval containing at least one prime number
• On vertex symmetric digraphs
• Positive graphs
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Self-complementary symmetric graphs
• Semi-transitive graphs
• The step Sidorenko property and non-norming edge-transitive graphs
• Two remarks on graph norms
• Weakly norming graphs are edge-transitive

Cited in

(3)

• Finite reflection groups and graph norms
• Extended commonality of paths and cycles via Schur convexity
• Domination inequalities and dominating graphs

This page was built for publication: On graph norms for complex‐valued functions

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