On a question of Vera T. Sós about size forcing of graphons (Q2678384): Difference between revisions

A graphon is effectively a limit object for random graphs. Formally it is a measurable symmetric function \(W: [0,1]^{2}\rightarrow [0,1]\). The \(k\)-sample from it, \(\boldsymbol{G}(k,W)\), is the random graph on \(k\) vertices obtained by taking \(x_{1},x_{2},\ldots x_{k}\) independent and uniformly distributed on \([0,1]\) and then making \(x_{i}\) adjacent to \(x_{j}\) with probability \(W(x_{i},x_{j})\) independently of all other pairs. Let \(X_{k}(W)\) be the number of edges in \(\boldsymbol{G}(k,W)\).\par Say two graphons \(U,W\) are weakly isomorphic if the random graphs \(\boldsymbol{G}(k,U)\) and \(\boldsymbol{G}(k,W)\) have the same distribution for every \(k\in \boldsymbol{N}\). A graphon parameter is a function from graphons to real vectors or numbers such that if \(U\) and \(W\) are weakly isomorphic we have \(f(W)=f(U)\). A family \((f_{i})_{i\in I}\) of graphon parameters is said to be forcing if \(f_{i}(U)=f_{i}(W)\) for all \(i\in I\) forces \(U\) and \(W\) to be weakly isomorphic. V. T. Sós asked if \((X_{k})_{k\in \boldsymbol{N}}\) is forcing. The constant \(p\)-graphon was shown to be forcing by \textit{E. Csóka}, J. Comb. Theory, Ser. B 116, 306--311 (2016; Zbl 1327.05240)] and independently by J. Fox, T. Łuczak and V. T. Sós herself. \par A natural next thing to look at is 2-step graphons where (without loss) we write \([0,1]=A\cup B\), \(A=[0,a)\). \([a,1]\) and say \(W\) is constant on each of \(A\times A\), \(B\times B\) and \((A\times B)\cup (B\times A)\), but interestingly the authors cannot answer this in general. However they can deal with a certain class of 3-step graphons (Theorem 2 of the paper under review). They also prove, motivated by the question of when finitely many parameters suffice for forcing, that the limit graphon for balanced quasirandom bipartite graphs is forced by the edge distribution of its 5-sample.\par The independence ratio \(\alpha(W)\) of a graphon \(W\) is the supremum (it is in fact a maximum) of the measure of \(A\subseteq [0,1]\) such that \(W\equiv 0\) a.e. on \(A\). The authors show that \(\alpha(W)=\lim_{k\rightarrow\infty}\left( \boldsymbol{P}(X_{k}(W)=0)\right)^{1/k}\). The proof of this result uses a version of the container method.\par They also show that two possible candidates for forcing weak isomorphism, namely the cycle counts and complete bipartite graphs, do not suffice, and raise some open problems.