For a graph H, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions W in L p , p ≥ e ( 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 neither 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 a negligence in the original statement of the aforementioned theorem by Hatami.

Department of Mathematics University College London Gower Street London WC1E 6BT UK

Institute of Mathematics of the Czech Academy of Sciences Žitná 25 115 67 Prague Czechia

Zobrazit více v PubMed

Chung FRK, Graham RL, Wilson RM. Quasi-random graphs. Combinatorica. 1989;9(4):345–362. doi: 10.1007/BF02125347. DOI

Conlon D, Lee J. Finite reflection groups and graph norms. Adv. Math. 2017;315:130–165. doi: 10.1016/j.aim.2017.05.009. DOI

Conlon, D., Lee, J.: Sidorenko’s conjecture for blow-ups. Discrete Anal. (to appear)

Doležal, M., Grebík, J., Hladký, J., Rocha, I., Rozhoň, V.: Cut distance identifying graphon parameters over weak* limits (2018). arXiv:1809.03797

Hatami H. Graph norms and Sidorenko’s conjecture. Israel J. Math. 2010;175:125–150. doi: 10.1007/s11856-010-0005-1. DOI

Král’ D, Martins TL, Pach PP, Wrochna M. The step Sidorenko property and non-norming edge-transitive graphs. J. Combin. Theory Ser. A. 2019;162:34–54. doi: 10.1016/j.jcta.2018.09.012. DOI

Lovász, L.: Graph homomorphisms: open problems (2008). https://web.cs.elte.hu/~lovasz/problems.pdf

Lovász, L.: Large Networks and Graph Limits. American Mathematical Society Colloquium Publications, vol. 60. American Mathematical Society, Providence (2012)

Lovász L, Szegedy B. Limits of dense graph sequences. J. Combin. Theory Ser. B. 2006;96(6):933–957. doi: 10.1016/j.jctb.2006.05.002. DOI

Thomason, A.: Pseudorandom graphs. In: Random Graphs