Weakly Norming Graphs are Edge-Transitive
- PDF / 417,394 Bytes
- 4 Pages / 442.205 x 665.008 pts Page_size
- 22 Downloads / 149 Views
COMBINATORICA
Bolyai Society – Springer-Verlag
WEAKLY NORMING GRAPHS ARE EDGE-TRANSITIVE ALEXANDER SIDORENKO Received April 2, 2020 Revised April 9, 2020 Let H be the class of bounded measurable symmetric functions on [0, 1]2 . For a function h ∈ H and a graph G with vertex set {v1 , . . . , vn } and edge set E(G), define Z Z Y h(xi , xj ) dx1 · · · dxn . tG (h) = · · · {vi ,vj }∈E(G)
Answering a question raised by Conlon and Lee, we prove that in order for tG (|h|)1/|E(G)| to be a norm on H, the graph G must be edge-transitive.
Let H be the class of bounded measurable symmetric functions on [0, 1]2 , and H+ be the subclass of nonnegative functions in H. The functions from H+ with values in [0, 1] are known as “graphons” (see [6]). For a function h ∈ H and a graph G with vertex set {v1 , . . . , vn } and edge set E(G), the homomorphism density from G to h is defined as Z Z Y tG (h) = · · · h(xi , xj ) dx1 · · · dxn . {vi ,vj }∈E(G)
Hatami [3] and Lovász [6, Chapter 14.1] posed the problem of determining when tG (h) provides a (semi-)norm on H. A graph G is called norming if |tG (h)|1/|E(G)| is a semi-norm, and weakly norming if tG (|h|)1/|E(G)| is a norm. Every norming graph is weakly norming. Lee and Schülke [5] demonstrated that G is (weakly) norming if and only if the functional tG (·) is strictly convex on (nonnegative) functions h ∈ H. Conlon and Lee [1, Section 6] proposed some conjectures characterizing norming and weakly norming graphs. Mathematics Subject Classification (2010): 05C22, 05C60; 15A60
2
ALEXANDER SIDORENKO
Every weakly norming graph is necessarily bipartite (see [3, 6]). Thus, it is possible to define norming and weakly norming graphs using asymmetric functions h (as was done by Hatami in [3]). It is easy to see that every (weakly) norming graph in the asymmetric setting is (weakly) norming in the symmetric setting as well. For this reason, we will restrict our attention to the symmetric case. All known examples of norming and weakly norming graphs are edgetransitive (see [1–6]). Thus, it is natural to ask if every edge-transitive bipartite graph is weakly norming, and if every weakly norming graph is edgetransitive (see [1, Section 6]). The first question was recently answered in the negative by Král’ et al. [4] who proved that toroidal grids C2k C2k with k ≥ 3 are not weakly norming. In this note, we provide the positive answer to the second question. Theorem 1. Every weakly norming graph is edge-transitive. To prove Theorem 1, we need a few results from [2], [3], and [6]. Theorem 2 ([2, Theorem 1.2]). A graph is weakly norming if and only if all its non-singleton connected components are isomorphic and weakly norming. Let E(G) = {e1 , e2 , . . . , ek }, el = {vi(l) , vj(l) }. Let h1 , h2 , . . . , hk ∈ H. Define Z tG (h1 , h2 , . . . , hk ) =
···
Z Y k
hl (xi(l) , xj(l) ) dx1 · · · dxn .
l=1
We clearly have tG (h, h, . . . , h) = tG (h). Theorem 3 ([6, Theorem 14.1]). G is weakly norming if and only if for any h1 , h2 , . . . , hk ∈ H+ , tG (h1 , h2 , . . . , hk )k ≤
k Y
t
Data Loading...
