Finite reflection groups and graph norms

DOI10.1016/J.AIM.2017.05.009MaRDI QIDQ2362589zbMATH OpenOpenAlexFDO

Authors David Conlon, Joonkyung Lee

Publication date 10 July 2017

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.05784, https://resolver.caltech.edu/CaltechAUTHORS:20190812-162957357

zbMATH Keywords

graph normsquasirandomnessSidorenko's conjecture

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Given a graph $H$ on vertex set $1,2,cdots,n$ and a function $f:[0,1{]}^{2}ightarrowmathbbR$, define �egin{align*} |f|_{H}:=leftvertint prod_{ijin E(H)}f(x_i,x_j)dmu^{|V(H)|} ightvert^{1/|E(H)|}, end{align*} where $mu$ is the Lebesgue measure on $[0,1]$. We say that $H$ is norming if $|cdot{|}_H$ is a semi-norm. A similar notion $|cdot{|}_{r(H)}$ is defined by $|f{|}_{r(H)}:=||f|{|}_H$ and $H$ is said to be weakly norming if $|cdot{|}_{r(H)}$ is a norm. Classical results show that weakly norming graphs are necessarily bipartite. In the other direction, Hatami showed that even cycles, complete bipartite graphs, and hypercubes are all weakly norming. We demonstrate that any graph whose edges percolate in an appropriate way under the action of a certain natural family of automorphisms is weakly norming. This result includes all previously known examples of weakly norming graphs, but also allows us to identify a much broader class arising from finite reflection groups. We include several applications of our results. In particular, we define and compare a number of generalisations of Gowers' octahedral norms and we prove some new instances of Sidorenko's conjecture.

Recommendations

• Two remarks on graph norms
• Graph norms and Sidorenko's conjecture
• On graph norms for complex‐valued functions
• Weakly norming graphs are edge-transitive
• Convex graphon parameters and graph norms

Cites work

• A correlation inequality for bipartite graphs
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• A new proof of Szemerédi's theorem
• Abstract Regular Polytopes
• An approximate version of Sidorenko's conjecture
• Combinatorics of Coxeter Groups
• Graph minors. III. Planar tree-width
• Graph norms and Sidorenko's conjecture
• scientific article; zbMATH DE number 53657 (Why is no real title available?)
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Inequalities for functionals generated by bipartite graphs
• Large networks and graph limits
• Limits of dense graph sequences
• On a Turán problem in weakly quasirandom 3-uniform hypergraphs
• Positive graphs
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• S-functions for graphs
• Some advances on Sidorenko's conjecture
• The homomorphism domination exponent
• Two approaches to Sidorenko's conjecture
• Weak quasi-randomness for uniform hypergraphs

Cited in

(41)

• The step Sidorenko property and non-norming edge-transitive graphs
• On the local approach to Sidorenko's conjecture
• Edges not in any monochromatic copy of a fixed graph
• Convex graphon parameters and graph norms
• Threshold Ramsey multiplicity for paths and even cycles
• Two remarks on graph norms
• Cut distance identifying graphon parameters over weak* limits
• Non-bipartite \(k\)-common graphs
• Weakly norming graphs are edge-transitive
• Inequalities for doubly nonnegative functions
• Impartial digraphs
• On positive hypergraphs
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Sidorenko's conjecture for blow-ups
• Extended root graphs for complex reflection groups
• Forcing quasirandomness with triangles
• On the extremal number of subdivisions
• scientific article; zbMATH DE number 7559121 (Why is no real title available?)
• Popular progression differences in vector spaces II
• Lower bounds for integral functionals generated by bipartite graphs.
• On tripartite common graphs
• Quasirandomness in hypergraphs
• Graph norms and Sidorenko's conjecture
• On some graph densities in locally dense graphs
• Toward characterizing locally common graphs
• Extremal results on feedback arc sets in digraphs
• On graph norms for complex‐valued functions
• A Property on Monochromatic Copies of Graphs Containing a Triangle
• On the Turán number of the hypercube
• Extended commonality of paths and cycles via Schur convexity
• Off-diagonal commonality of graphs via entropy
• Domination inequalities and dominating graphs
• The sparse regularity method with Schatten norms and entropy
• When entropy meets Turán: new proofs and hypergraph Turán results
• Sidorenko hypergraphs and random Turán numbers
• Non-trivial squares and Sidorenko's conjecture
• Common pairs of graphs
• Local aspects of the Sidorenko property for linear equations
• Common graphs with arbitrary chromatic number
• Disconnected common graphs via supersaturation
• A reverse Sidorenko inequality

This page was built for publication: Finite reflection groups and graph norms

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