Cut distance identifying graphon parameters over weak* limits

0494763 - ÚI 2019 US eng V - Research Report
Doležal, Martin - Grebík, Jan - Hladký, Jan - Rocha, Israel - Rozhoň, Václav
Cut distance identifying graphon parameters over weak* limits.
Cornell University, 2018. 21 s. arXiv.org e-Print archive, arXiv:1809.03797 [math.CO].
R&D Projects: GA ČR GJ16-07822Y; GA ČR GF17-33849L; GA ČR(CZ) GJ18-01472Y
Institutional support: RVO:67985807 ; RVO:67985840
Keywords : graphon * graph limit * cut norm * weak* convergence * norm graphs
OECD category: Pure mathematics
https://arxiv.org/abs/1809.03797

The theory of graphons comes with the so-called cut distance. The cut distance is finer than the weak* topology. Dole\v{z}al and Hladk\'y [arXiv:1705.09160] showed, that given a sequence of graphons, a cut distance accumulation graphon can be pinpointed in the set of weak* accumulation points as minimizers of the entropy. Motivated by this, we study graphon parameters with the property that their minimizers or maximizers identify cut distance accumulation points over the set of weak* accumulation points. We call such parameters cut distance identifying. Of particular importance are cut distance identifying parameters coming from subgraph densities, t(H,⋅). It turns out that this concept is closely related to graph norms. In particular, we prove that a connected graph H is step Sidorenko (a concept very similar to t(H,⋅) being cut distance identifying) if and only if it is weakly norming. This answers a question of Kr\'al', Martins, Pach and Wrochna [arXiv:1802.05007]. Further, we study convexity properties of cut distance identifying graphon parameters, and find a way to identify cut distance limits using spectra of graphons.
Permanent Link: http://hdl.handle.net/11104/0287832