Cut-norm and entropy minimization over weak* limits

0504394 - MÚ 2020 RIV US eng J - Journal Article
Doležal, Martin - Hladký, Jan
Cut-norm and entropy minimization over weak* limits.
Journal of Combinatorial Theory. B. Roč. 137, July (2019), s. 232-263. ISSN 0095-8956. E-ISSN 1096-0902
R&D Projects: GA ČR GA16-07378S
Institutional support: RVO:67985840
Keywords : cut-norm * graphon * Lovász–Szegedy theorem weak* limits
OECD category: Pure mathematics
Impact factor: 1.306, year: 2019
Method of publishing: Limited access
http://dx.doi.org/10.1016/j.jctb.2018.12.010

We prove that the accumulation points of a sequence of graphs G 1 ,G 2 ,G 3 ,… with respect to the cut-distance are exactly the weak ⁎ limit points of subsequences of the adjacency matrices (when all possible orders of the vertices are considered) that minimize the entropy over all weak ⁎ limit points of the corresponding subsequence. In fact, the entropy can be replaced by any map W↦∬f(W(x,y)), where f is a continuous and strictly concave function. As a corollary, we obtain a new proof of compactness of the cut-distance topology.
Permanent Link: http://hdl.handle.net/11104/0296034