APPROXIMATING FRACTIONALLY ISOMORPHIC GRAPHONS JAN HLADK Y AND ENG KEAT HNG

2025-04-30 0 0 577.94KB 23 页 10玖币
侵权投诉
APPROXIMATING FRACTIONALLY ISOMORPHIC
GRAPHONS
JAN HLADK ´
Y AND ENG KEAT HNG
Abstract. Greb´ık and Rocha [Fractional Isomorphism of Graphons,
Combinatorica 42, pp 365–404 (2022)] extended the well studied notion
of fractional isomorphism of graphs to graphons. We prove that frac-
tionally isomorphic graphons can be approximated in the cut distance
by fractionally isomorphic finite graphs. This answers the main question
from ibid. As an easy but convenient corollary, we deduce that every
regular graphon can be approximated by regular graphs.
1. Introduction
The theory of limits of dense graph sequences, introduced in [9, 1] and
nicely surveyed in [8], provides a powerful correspondence between (finite)
graphs on the one hand and analytic objects called graphons on the other.
In the motivating part of this introduction, we shall refer to this theory
rather casually and do not need exact definitions.
The two main results of the theory of dense graph limits say that
(R1) each sequence of graphs contains a subsequence converging[∗]to a
graphon, and
(R2) each graphon has a sequence of graphs converging to it.
A key question is how various graph properties and parameters relate to
their graphon counterparts in the context of (R1) and (R2). One parame-
ter which is well understood is homomorphism density: by the continuity
of homomorphism densities, every convergent sequence of graphs has ho-
momorphism densities with respect to each fixed graph which converge to
that in the limit graphon. On the other hand, there are properties and pa-
rameters of graphons which are more subtle in that they are not reflected
in every sequence of graphs converging to a certain graphon, but rather in
at least one sequence. Take for example the concept of vertex-transitivity,
which was treated in detail for graphons in [10]. It was shown there that
the limit graphon of a convergent sequence of vertex-transitive graphs is
vertex-transitive; this relates to (R1). Regarding (R2), we may ask if every
vertex-transitive graphon is the limit of at least one sequence of vertex-
transitive graphs; this seems to be a difficult question (see [2]). Clearly,
Research supported by Czech Science Foundation Project GX21-21762X and with in-
stitutional support RVO:67985807.
An extended abstract titled ‘Fractionally isomorphic graphs and graphons’ summariz-
ing this work will appear in the proceedings of Eurocomb2023.
[∗]convergence is meant here and elsewhere to be in the cut distance (denoted by δ)
1
arXiv:2210.14097v2 [math.CO] 18 May 2023
2 JAN HLADK ´
Y AND ENG KEAT HNG
not every sequence of graphs with a vertex-transitive limit graphon is a se-
quence of vertex-transitive graphs (hint: delete a single edge). Indeed, many
of these more subtle properties concern symmetries.
In this paper we use this point of view to study fractional isomorphism.
The concept of fractional isomorphism for graphs was introduced by Tin-
hofer in 1986 [14], and several important equivalent but very different-
looking definitions were later added by Ramana, Scheinerman, and Ull-
man [11] and another by Dvoˇr´ak [4] and independently by Dell, Grohe, and
Rattan [3]. We refer the reader to Section 6 of [13] for a treatise of these
concepts and recall here the definition introduced in [11], which is the most
convenient to work with in this paper. An equitable partition of a graph G
is a partition P={Pi}i∈[k]of V(G) into disjoint nonempty parts such that
for all i, j ∈[k] and u∈Piwe have
(1) degG(u;Pj) = 1
|Pi|X
v∈Pi
degG(v;Pj).
The parameters of Pare a pair ((pi)i∈[k],(Di,j)i,j∈[k]) where pi=|Pi|for
all i∈[k] and Di,j = degG(u;Pj) for all i, j ∈[k] and u∈Pi. We say
that two graphs Gand Hare fractionally isomorphic if they have equitable
partitions PGand PHwhich can be indexed in a way so that they have
the same parameters. As a first example, observe that taking equitable
partitions with k= 1 in the definition yields that any two d-regular graphs
on nvertices are fractionally isomorphic.
In [6], Greb´ık and Rocha developed a theory of fractional isomorphism for
graphons. In particular, they showed that all the equivalent definitions of
fractional isomorphism of graphs previously studied have graphon counter-
parts and that these are indeed all equivalent. It follows from their results
that if {Gn}n∈Nand {Hn}n∈Nare sequences of graphs so that Gnis frac-
tionally isomorphic to Hn(for each n), {Gn}n∈Nconverges to a graphon
Wand {Hn}n∈Nconverges to a graphon U, then Uand Ware fraction-
ally isomorphic. Let us sketch a proof of this result. To this end, we first
recall another characterization of fractional isomorphism from [4, 3], which
says that two graphs Gand Hon the same number of vertices are fraction-
ally isomorphic if and only if their homomorphism counts hom(T, G) and
hom(T, H) coincide for all trees T. Hence, if {Gn}n∈N,{Hn}n∈N,Wand U
are as above, then by the continuity of homomorphism densities we get that
the homomorphism density of every tree Tin Wand in Uare equal. This
in turn is a characterization of fractional isomorphism of graphons from [6].
As with vertex-transitivity, we cannot reverse this in the strong sense: for
two fractionally isomorphic graphons Wand Uthere are many sequences
{Gn}n∈Nconverging to Wand {Hn}n∈Nconverging to Uwhere Gnis not
fractionally isomorphic to Hn. However, a weak reversal was the main open
question in [6].
Question 1.1 (Question 3.2 in [6]).Let Wand Ube fractionally isomorphic
graphons. Does there exist sequences {Gn}n∈Nand {Hn}n∈Nof graphs such
that Gnis fractionally isomorphic to Hnfor each n∈Nand
Gn→δWand Hn→δU?
APPROXIMATING FRACTIONALLY ISOMORPHIC GRAPHONS 3
The main result of this paper is a positive answer to Question 1.1. In
fact, we prove a slightly stronger statement in which we simultaneously
approximate an arbitrary (even infinite) family of fractionally isomorphic
graphons.
Theorem 1.2. Given ε > 0and a family Uof fractionally isomorphic
graphons, there exists n0∈Nsuch that for each n≥n0there exists a family
{HU}U∈U of fractionally isomorphic graphs on vertex set [n]such that for
each U∈ U we have δ(U, HU)≤ε.
The simplest instance of Theorem 1.2 is the regular case. Specifically,
suppose that d∈[0,1] and Uis a family of regular graphons with degree d
on a probability space (Ω, π); we say that a graphon Uis regular with degree
dif for almost every x∈Ω we have degU(x) = Ry∈ΩU(x, y) dπ=d. Such
graphons are known to be fractionally isomorphic (and it is easy to show
this). Hence, our theorem applies and says that there are fractionally iso-
morphic graphs {HU}U∈U of order nwhich approximate {U}U∈U . This itself
does not guarantee that the degree-regularity of the graphs HU. Indeed, for
example in our construction we might add an isolated vertex to each graph
HU(which is a step which does not spoil fractional isomorphism). However,
it follows from basic properties of the cut distance that most vertices in each
graph HUhave degrees around dn. Despite this, a closer look at our proof
does give that the graphs HUare in fact D-regular for some D= (1 ±ε)dn.
This leads to the following theorem.
Theorem 1.3. Suppose that d∈[0,1] and Uis a family of graphons which
are fractionally isomorphic to the constant-dgraphon Cd. Then for every
ε > 0there exists n0∈Nsuch that for each n≥n0there exists D∈Nand
a family {HU}U∈U of D-regular graphs on vertex set [n]such that for each
U∈ U we have δ(U, HU)≤ε.
The remainder of this paper is organised as follows. We begin with a high
level sketch of the strategy of our proof of Theorem 1.2 in Section 1.1. In
Section 2 we introduce notation, introduce some technical tools and recall
important concepts about graphons, fractional isomorphism for graphons
and graphon sampling. We also introduce a version of Szemer´edi’s regularity
lemma suited to our purposes. In Section 3 we provide our main lemmas
and apply them to prove Theorem 1.2. We provide proofs of the main
lemmas in Section 3.1. Finally, in Section 4 we show how to obtain a proof
of Theorem 1.3 from the proof of Theorem 1.2 given in Section 3.
1.1. Proof idea. Let us describe our proof of Theorem 1.2 at a high level
and give relevant pointers along the way. The key concept of the theory
developed in [6] is a certain quotient object W/C(W) for each graphon W;
a formal definition is given in Section 2.4. The importance of this object is
that two graphons Uand Ware fractionally isomorphic if and only if U/C(U)
and W/C(W) are isomorphic. To start with, we give a simplified description
mimicking the definition of equitable partitions of graphs. Let (Ω, π) be a
probability space. Assume in this simplification that for a graphon W: Ω2→
[0,1] the object W/C(W) comes from a suitably chosen finite partition Q=
{Qi}i∈[M](for some M∈N) of Ω and has the property that for all i, j ∈[M]
4 JAN HLADK ´
Y AND ENG KEAT HNG
and x∈Qiwe have
(2) degW(x;Qj) = 1
π(Qi)·Zy∈Qi
degW(y;Qj) dπ ,
a property clearly inspired by (1). Then W/C(W) serves as a counter-
part to the profile, that is, it records the measures of the sets Qiinto
a vector r= (ri)i∈[M]and the densities of pairs (Qi, Qj) into a matrix
D= (di,j)i,j∈[M]. That means ri=π(Qi) for all i∈[M] and di,j =
1
π(Qi)π(Qj)R(x,y)∈Qi×QjW(x, y) for all i, j ∈[M]. Now since fractional iso-
morphism of graphons is characterized by isomorphic quotients, all the
graphons in Uhave the same profile (r,D).
The standard approach to approximating each U∈ U is to take a U-
random graph HU∼G(n, U) for nlarge. Details about U-random graphs
are given in Section 2.5; for now it is enough to recall that such a random
graph has vertex set [n], which corresponds to a set of ni.i.d. uniformly
random points x1, x2, . . . , xnfrom Ω, and each pair {i, j}is inserted as
an edge independently with probability U(xi, xj). In such a setting, basic
concentration tells us that with high probability,
(C1) for each i∈[M] the set Xi:= {`∈V(HU) : x`∈Qi}has size
|Xi| ≈ rin, and
(C2) for each i, j ∈[M] and each `∈Xiwe have degHU(`, Xj)≈di,j rjn.
Observe that if the approximate equalities above were exact, then the
graphs {HU}U∈U constructed would automatically be fractionally isomor-
phic with the collection {Xi}i∈[M]playing the role of an equitable partition.
Hence, we shall modify each HUslightly by adding o(n) vertices and o(n2)
edges to obtain exact control on the number of vertices in each part and on
degrees between pairs of parts. To get exact control on the number of ver-
tices in each part, for each i∈[M] we add a set Yiof newly created vertices
with |Yi|=brin(1 + β)c−|Xi|(for some small β > 0); the vertex set of the
modified graph GUshall be (X1tY1)∪(X2tY2)t. . . t(XMtYM).
To get exact control on the degrees, we would like to add edges to obtain
GUwhere (for some α > 0 small)
(G1) for each i, j ∈[M] with i6=jand each `∈Xi∪Yiwe have
degGU(`, Xj∪Yj) = b(1 + α)di,j rjnc, and
(G2) for each i∈[M] the graph GU[Xi∪Yi] is regular with degree
b(1 + α)di,irinc.
To achieve the exact degrees in (G1), for each i, j ∈[M] with i6=jwe shall
add a set of edges in the bipartite pair (Xi∪Yi, Xj∪Yj) which are incident
to Yi∪Yj; we obtain these edges by applying a theorem of Gale and Ryser.
To achieve the exact degrees in (G2), for each i∈[M] we shall add a set
Fi,i of edges on Xi∪Yiwhich are incident to Yi; some of these edges are
obtained in the bipartite pair (Xi, Yi) by applying the theorem of Gale and
Ryser referenced above, while the remainder of these edges are obtained on
Yiby applying a theorem of Erd˝os and Gallai. Finally, note that since the
initial graph contained no edges of the types mentioned above, the addition
of such edges does not create multiedges.
APPROXIMATING FRACTIONALLY ISOMORPHIC GRAPHONS 5
The key lemmas that describe the construction outlined in the previous
paragraphs are Lemmas 3.3–3.5 (which are all already tailored to the gen-
eral setting, which we address below). Lemma 3.3 encapsulates a cleaning
procedure for graphons whose purpose goes beyond our simplified setting,
Lemma 3.4 formalizes the outcome of the random graph sampling procedure
(represented by (C1) and (C2) in our simplified setting), and Lemma 3.5
deals with the subtle procedure of adding vertices and balancing degrees.
In the general setting, U/C(U) is defined in terms of a suitable sub-sigma-
algebra and does not usually correspond to a finite partition. To see that
such a setting is unavoidable in the theory of Greb´ık and Rocha, observe
that vertices inside one set Qiabove must have the same overall degree; on
the other hand, it is easy to construct graphons such that any particular
degree is achieved only on a nullset of Ω.[†]Even though the Greb´ık–Rocha
theory is inherently infinitesimal, for the steps described in (C1), (C2), (G1)
and (G2) it is essential that we work with a finite partition. To bridge the
gap between the two settings, we employ Szemer´edi’s regularity lemma.
Indeed, it is well-known that if Q={Qi}i∈[M]is an ε-regular partition of U,
then in particular we have an approximate version of (2) for most vertices
x∈Qi. All in all, we can essentially return to the finite setting as above,
with many additional technical modifications to treat various imprecisions
that are unavoidable in connection with the regularity lemma.
2. Preliminaries
2.1. Notation. Write Nfor the set of positive integers and N0for the set
N∪{0}. For a∈N0write [a] for the set {1, . . . , a}and [a]0for [a]∪{0}. For
`∈N0and a set Swrite S
`for the set of all subsets of Sof size `. For a
set Swrite S(2) ={(i, j)∈S2:i6=j}. For real numbers xand y, we write
x±yto mean an appropriate real number zsatisfying x−y≤z≤x+y.
2.2. Tools. In this subsection we collect some tools. We first state a form
of the Chernoff bounds.
Theorem 2.1 ([7, Theorem 2.1]).Suppose that Xis a sum of independent
and identically distributed Bernoulli random variables. Then for 0≤ε≤3/2
we have
P(X≥(1 + ε)E[X]) ≤e−ε2E[X]/3and P(X≤(1 −ε)E[X]) ≤e−ε2E[X]/3.
Next, we recall some tools related to degree sequences in graphs. Recall
that a sequence (ci)i∈[n]is graphic if there exists a graph whose degree
sequence is (ci)i∈[n]. Graphic sequences are characterized by the Erd˝os–
Gallai theorem.
Theorem 2.2 (Erd˝os–Gallai).A sequence (di)i∈[n]of nonnegative integers
in nonincreasing order is graphic if and only if the following hold.
(EG1) Pn
i=1 diis even.
(EG2) For each k∈[n]we have Pk
i=1 di≤k(k−1) + Pn
i=k+1 min{di, k}.
[†]For example, take a graphon W: [0,1]2→[0,1] defined by W(x, y) = (x+y)/2.
摘要：

APPROXIMATINGFRACTIONALLYISOMORPHICGRAPHONSJANHLADKYANDENGKEATHNGAbstract.GrebkandRocha[FractionalIsomorphismofGraphons,Combinatorica42,pp365{404(2022)]extendedthewellstudiednotionoffractionalisomorphismofgraphstographons.Weprovethatfrac-tionallyisomorphicgraphonscanbeapproximatedinthecutdistance...

展开>> 收起<<
APPROXIMATING FRACTIONALLY ISOMORPHIC GRAPHONS JAN HLADK Y AND ENG KEAT HNG.pdf

共23页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：23 页 大小：577.94KB 格式：PDF 时间：2025-04-30

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 23
评分 收藏
分享
立即下载
客服
关注