A Caltech Library Service

Finite reflection groups and graph norms

Conlon, David and Lee, Joonkyung (2017) Finite reflection groups and graph norms. Advances in Mathematics, 315 . pp. 130-165. ISSN 0001-8708. doi:10.1016/j.aim.2017.05.009.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Given a graph H on vertex set {1, 2, • • •, n} and a function f : [0, 1]^2 → ℝ, define [equation; see abstract in PDF for details], where μ is the Lebesgue measure on [0, 1]. We say that H is norming if ∥•∥_H is a semi-norm. A similar notion ∥•∥_r(H) is defined by ∥f∥_r(H) := ∥|f|∥_H and H is said to be weakly norming if ∥•∥_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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:© 2017 Elsevier Inc. All rights reserved. Received 1 December 2016; accepted 16 May 2017; available online 13 June 2017. Conlon research supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. Lee supported by the ILJU Foundation of Education and Culture. Part of this work was carried out while the authors participated in the LMS-CMI Research School on Regularity and Analytic Methods in Combinatorics at the University of Warwick and also while the second author was visiting KIAS. The second author would like to thank Seung Jin Lee for suggestions of references and helpful discussions on algebraic combinatorics. We would also like to thank Alexander Sidorenko for some helpful remarks on an earlier version of this paper.
Funding AgencyGrant Number
European Research Council (ERC)676632
ILJU Foundation of Education and CultureUNSPECIFIED
Subject Keywords:Graph norms; Sidorenko’s conjecture; Quasirandomness
Record Number:CaltechAUTHORS:20190812-162957357
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97809
Deposited By: Melissa Ray
Deposited On:13 Aug 2019 17:26
Last Modified:16 Nov 2021 17:34

Repository Staff Only: item control page