First-order logic of uniform attachment random graphs with a given degree

2025-05-06 0 0 123.11KB 7 页 10玖币

侵权投诉

arXiv:2210.15538v1 [math.PR] 27 Oct 2022

First-order logic of uniform attachment random graphs

with a given degree⋆

Y.A. Malyshkina

aMoscow Institute of Physics and Technology//Tver State University

Abstract

In this paper, we prove the ﬁrst-order convergence law for the uniform attach-

ment random graph with almost all vertices having the same degree. In the

considered model, vertices and edges are introduced recursively: at time m+ 1

we start with a complete graph on m+ 1 vertices. At step n+ 1 the vertex n+ 1

is introduced together with medges joining the new vertex with mvertices cho-

sen uniformly from those vertices of 1,...,n, whom degree is less then d= 2m.

To prove the law, we describe the dynamics of the logical equivalence class of

the random graph using Markov chains. The convergence law follows from the

existence of a limit distribution of the considered Markov chain.

Keywords: uniform attachment; convergence law; ﬁrst-order logic; Markov

chains

1. Introduction

In the present paper, we proof of the FO convergence law for uniform at-

tachment random graphs with most vertices having a given degree using ﬁnite

Markov chains.

FO sentences about graphs could include the following symbols: variables

x, y, x1,... (which represent vertices), logical connectives ∧,∨,¬,⇒,⇔, two re-

lational symbols (between variables) ∼(adjacency) and =(equality) , brackets

and quantiﬁers ∃,∀(see the formal deﬁnition in, e.g., [L04]). The sequence Gn

of random graphs obeys the FO convergence law, if, for every FO sentence ϕ,

Pr(Gn|=ϕ)converges as n→ ∞. If the limit is eighter 0or 1for any formula,

Gnobeys the zero-one law. If Gnobeys the zero-one law, it is trivial in terms of

the FO logic in the sense that all properties are trivial on a typical large enough

graph.

The FO logical laws usually proven using Ehrenfeucht-Fraïssé pebble game

(see, e.g., [L04, Chapter 11.2]). The connection between FO logic and the

Ehrenfeucht-Fraïssé game is described in the following result.

⋆Present work was funded by RFBR, project number 19-31-60021.

Email address: yury.malyshkin@mail.ru (Y.A. Malyshkin)

Preprint submitted to Elsevier October 28, 2022

Theorem 1.1. Duplicator wins the γ-pebble game on Gand Hin Rrounds

if and only if, for every FO sentence ϕwith at most γvariables and quantiﬁer

depth at most R, either ϕis true on both Gand Hor it is false on both graphs.

In particular, if for any ǫ > 0one could deﬁne a ﬁnite number of classes Ak,

k= 1, ..., K, of graphs such that Duplicator wins the pebble game on graphs of

the same class and Pr(Gn∈ Ak)→pkfor all k= 1, ..., K with PK

k=1 pk>1−ǫ,

then Gnobeys the FO convergence law.

Logic limit laws were studied on many diﬀerent models, such as the binomial

random graph ([S91, SS88]), random regular graphs ([HK10]), attachment mod-

els ([MZ21, M22, MZ22]), etc. ([HMNT18, S01, W93]). In the present article,

we are interested in recursive random graph models. One of the main arguments

towards Gnnot satisfying the zero-one law for such models is the existence of

rare subgraphs which appear with diminishing probability (and with high prob-

ability does not appear after some moment, see, e.g. [MZ21]). In this case, even

if Gnobeys the FO convergence law and not the zero-one law, it still could be

asymptotically trivial in terms of some classes of sentences of the FO logic in a

sense that the correctness of the property on a graph does not change after some

moment (see, e.g., [M22, MZ22]). In such a case, the division on the classes Ak,

k= 1, ..., K, is based on subgraph of Gnon ﬁrst Nvertices for all n > N (N

depends on ǫ). The more diﬃcult case is when the correctness of the property

changes inﬁnitely many times during the course of the (graph) process. Such

behavior is somewhat similar to the behavior of a Markov chain, which changes

its state inﬁnitely many times but still could have a limiting probability distri-

bution. One of the main purposes of the present paper is to showcase such a

connection between a graph obeying the FO convergence law and the existence

of the limiting probability distribution for related Markov chains (in our case

such a chain would be ﬁnite).

Let us give a formal description of our model. Fix m∈N,m > 1, and let

d= 2m. We start with a complete graph Gm+1 on m+ 1 vertices. Then on

each step, we add a new vertex and draw medges from it to diﬀerent vertices,

chosen uniformly among vertices with a degree less than d. Note that the total

degree (the sum of degrees of all vertices) of the graph Gnwould be equal to

m(m−1) + 2m(n−m) = dn −m(m+ 1). In particular, the number of vertices

of degree din Gnis between n−m(m+ 1) and n−(m+ 1). Hence it is always

possible to draw medges from a new vertex to diﬀerent vertices (of a degree less

than d). The model for d > 2mwas considered in [MalZhu22], where a similar

result was proven using Markov chains with inﬁnitely many states, as well as

the stochastic approximation technique.

The resulting graph is somewhat similar to a d-regular graph (i.e. graph

with all vertices having degree d, either number of vertices or the degree should

be even for such a graph to exist). Note that regular graphs could not be

dynamic since if we draw edges to vertices of a regular graph it would no longer

be regular. Hence, regular graphs are built separately for each n(where nis the

number of vertices). Our model could be considered as a way to build a graph

with properties close to a regular graph through the dynamic procedure.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.15538v1[math.PR]27Oct2022First-orderlogicofuniformattachmentrandomgraphswithagivendegree⋆Y.A.MalyshkinaaMoscowInstituteofPhysicsandTechnology//TverStateUniversityAbstractInthispaper,weprovetheﬁrst-orderconvergencelawfortheuniformattach-mentrandomgraphwithalmostallverticeshavingthesamedegr...

展开>> 收起<<

First-order logic of uniform attachment random graphs with a given degree.pdf

共7页,预览2页

还剩页未读，继续阅读

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

First-order logic of uniform attachment random graphs with a given degree

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: