Случайные графы: Индуцированные подграфы и логика первого порядка / Random Graphs: Induced Subgraphs and First-Order Logic тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Буитраго Оропеса Хуан Карлос

• Буитраго Оропеса Хуан Карлос
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Буитраго Оропеса Хуан Карлос

Contents

Introduction

Thesis Aim and Scope

Zero-one Law for the Random k-partite Model

Concentration Phenomenon for Maximum Induced Subgraphs

Methodology

The First and Second Moment Methods

Proving Zero-one Law

Proving Concentration in Consecutive Points

Main Results

Scientific Novelty

Scientific and Practical Significance

Presentation of Results in Conferences

Publications

Structure of the Thesis

1 Chapter 1. Classical Results and Concentration for Paths in Dense G(n,n,p)

1.1 Thresholds

1.2 Zero-one Laws for G(n,p)

1.3 Independence Number and Largest Induced Subgraphs

1.3.1 Concentration for Maximum Paths in Dense G(n,n,p)

2 Chapter 2. Zero-one Laws for Random k-partite Graphs

2.1 Preliminaries

2.2 Results for p such that min{p, 1 — p}na ^

2.3 Results for p = n-a, a > 0 rational

2.4 Results for p = n-a, a > 0 irrational

2.5 Existence of Strictly Balanced Bipartite Graphs

3 Chapter 3. Maximum Induced Trees in Sparse Random Graphs

3.1 Proof of Theorem

3.1.1 Computation of k

3.1.2 First and Second Moment Methods

3.1.3 Part 1: I G [2,1*

3.1.4 Part 2: 1 G (V, k — w

3.1.5 Part 3: I e( k — w ,k — fl

[ p_ ' 2p_

3.1.6 Part 4: I G [k — 1 ,k

4 Conclusions

References

Введение диссертации (часть автореферата) на тему «Случайные графы: Индуцированные подграфы и логика первого порядка / Random Graphs: Induced Subgraphs and First-Order Logic»

Introduction

Random graph theory has become an essential and vibrant area of study within both discrete mathematics and probability theory. Its origins can be traced back to the seminal works of Erdos and Renyi in the late 1950s [18]-[21], who laid the foundational groundwork for what would become the modern theory of random graphs. These pioneering papers introduced the concept of a random graph and set forth fundamental results concerning their properties, such as the appearance of the giant component and the phase transition for connectivity. These groundbreaking works not only initiated a new field of study but also provided a probabilistic perspective on classical graph theory problems, which was revolutionary for its time.

Since its inception, random graph theory has evolved into a dynamic and influential discipline, extending far beyond its original scope. One of the key reasons for its importance lies in its ability to model and analyze complex networks found in the real world, such as social networks, biological networks, networks of interacting particles in statistical physics and percolation phenomena. These networks often exhibit random or semi-random characteristics, making random graph theory an invaluable tool for understanding their structure, behavior, and evolution. In social network analysis, random graph models help explain phenomena like the "small-world" effect described by the Watts-Strogatz model [34], [35], which highlights two essential properties of real-world networks: short average path lengths, where most vertices are reachable within a few steps, and high clustering coefficients, where vertices tend to form closely connected groups. In biology, they provide insight into the organization and dynamics of molecular networks, such as those governing gene regulation or protein-protein interactions [30]-[33]. In statistical physics, random graphs are used to study percolation phenomena, where the emergence of a giant connected component in a network models phase transitions in physical systems [36]-[39]. In epidemiology, random graphs are applied to address real-world problems by modeling the spread of diseases on networks [55]-[60]. In telecommunications, understanding the reliability and performance of communication networks requires insights from random graph models [61]-[67].

Furthermore, random graphs have been instrumental in the development of new mathematical techniques and tools. In computer science, random graphs are central in the analysis of average-case hardness of computational problems. As a consequence, random graphs are useful in designing algorithms that work efficiently in practice when data is large and inherently noisy, for example, in machine learning and data mining [42]-[54].

Generally speaking, a random graph is a graph chosen according to some probability distribution over a given set of graphs. Let [n] := {1,... , n}, n E N and p E (0,1). The Binomial random graph G(n,p) is a random element of the set Qn = {G = ([n],E)} of all undirected graphs without

loops and multiple edges with the set of vertices [n] and the distribution defined by

p(G(n,p) = G) = p|E|(1 — p)(n)-|E|,

i.e. every edge of the complete graph Kn appears with probability p independently. This model is particularly important and popular for its simplicity and versatility, providing a foundational framework for studying various properties of the graph, such as connectivity, the emergence of a giant component, and the distribution of cycles and other subgraphs [68]-[77].

In this work, we will also consider the binomial random k-partite graph Gkxn(p). Consider the set ^fcxn = {G = (V^LI... UVn E)} of all undirected graphs without multiple edges with the disjoint and independent sets of vertices Vn of size n, i G [k], such that only edges between vertices belonging to different sets are allowed. The random k-partite graph Gkxn(p) is a random element of Hfcxn with distribution defined by

p(Gkxn(p) = G) = p|E|(1 — p)(2)n2-|E|,

i.e. every edge of the complete k-partite graph appears with probability p independently. The k-partite random graph model allows for the study of random structures that are more constrained and structured than the usual G(n, p), making it suitable for applications where data is naturally divided into multiple categories or groups, such as in certain social or biological networks [78]-[83]. An important special case of the random k-partite graph, which we will consider in Chapter 1, is when k = 2. In this scenario, it is referred to as a random bipartite graph, denoted by G(n, n, p).

The most interesting and fundamental questions in random graph theory pertain to the case where the number of labeled vertices, n, tends to infinity. In this context, we study the asymptotic behavior of the probabilities of various graph properties under two different regimes for p: one in which p is a constant, and the other in which p is a function that depends on n.

When we say that a random graph possesses a certain property, such as being connected, we mean that the resulting graph belongs to the set of all graphs on n vertices that have this property. In random graph theory, we focus on specific properties known as monotone properties. A graph property L is called monotone if it is either increasing or decreasing, meaning that one of the following conditions holds:

• If H C G and H has the property L, then G has the property L (increasing property). For example, being connected.

• If H C G and G has the property L, then H has the property L (decreasing property). For example, having an isolated vertex.

A particular feature of many graph properties is that the limiting probability that a graph possesses them jumps from 0 to 1 (or vice versa) very rapidly as p increases. This is called the phenomenon of thresholds. To describe this phenomenon more precisely, we introduce threshold functions (or simply thresholds) for monotone graph properties. A function p* = p*(n) serves as a threshold for a monotone increasing property L, if

f0 if p/p* ^ 0, lim p(G(n,p) E L) = <

[1 if p/p* ^ro,

as n ^ ro. In the same way, a function p* = p*(n) is a threshold for a monotone decreasing property L, if

f1 if p/p* ^ 0, lim p(G(n,p) E L) = I

lo if p/p* ^ ro,

as n ^ ro. In 1987 it was proved by Bollobas and Thomason [14] that every non-trivial monotone graph property has a threshold.

Thesis Aim and Scope

In this study, we have three main objectives: The first one is to establish the validity of the Firstorder zero-one law [6]-[9] for the binomial random k-partite graph model. The second objective is to extend the well-known two-point concentration phenomenon, traditionally associated with the independence number in a random graph [23]-[25], for the size of maximum induced tress in G(n,p), where p(n) = o(1). Finally, we aim to initiate the study of the concentration phenomenon in binomial bipartite random graphs, proving that the size of the maximum induced path ([84]) in G(n,n,p) is concentrated on three consecutive points, where p E (0,1) is constant.

Zero-one Law for the Random k-partite Model

The first-order (FO) zero-one law is a fundamental result in the theory of random graphs, particularly within the context of the classic Erdos-Renyi model G(n,p) [6]-[9]. It states that for any property expressible in first-order logic—a formal system that allows quantification over individual vertices but not over sets or relations—the probability that this property holds in a random graph converges to either zero or one as the number of vertices n tends to infinity.

The FO language (for formal definitions, see [5], [15]) includes variables (x,y,...) representing vertices, equality and adjacency relations (x = y, x ~ y), standard Boolean connectives (A, —,...), and universal and existential quantifiers (V, 3). For instance, the property of containing a triangle can be expressed as: 3x3y3z[x ~ y A x ~ z A y ~ z]. Additionally, the quantifier depth of a FO sentence ^ (formally defined in [15]) roughly measures the number of times quantifiers are nested within

FO properties of graphs are defined by FO sentences. For a graph property L, let {Gkxn(p) G L} denote the event "Gkxn(p) has the property L". Then, for a given p = p(n), Gkxn(p) is said to obey the FO zero-one law (or just zero-one law) if for any FO property L the probability p(Gkxn(p) G L) tends either to 0, or to 1 as n ^ x>. The zero-one law has been widely studied in the case of classical binomial random graphs G(n,p) with no restrictions on possible edges. For this random graph model, all the main positive results, stated in Theorem 1.4, first part of Theorem 1.5 and Theorem 1.6 can be proved using the Ehrenfeucht game [13], [17].

In this work, in Chapter 2, we successfully extend the zero-one law to the binomial random k-partite graph model Gkxn(p). Our results were established for two distinct regimes of p: one where p is a constant, and another where p is a function of n such that p = o(1).

Concentration Phenomenon for Maximum Induced Subgraphs

A vertex set U C [n] in a graph in which no two vertices are adjacent is said to be an independent set. The size of the largest independent set is called the independence number of the graph. The size distribution of the largest independent set in the random graph has been carefully studied. In [23], [24] it was proved that, with probability tending to 1, the independence number of G(n,p = const) is concentrated on two values, /o(n) and /o(n) + 1, where

/o(n)= [2log6 n — 2logb logb n + 2log6 2 + 0.9J , b =1/(1 — p).

Some refinements of this result can be found in [25]. In this case, the independence number is said to be concentrated at two points.

Later, the two-point concentration was also proved for other characteristics of the random graph. A natural generalization of the independence number problem is the question about the maximum size of an induced subgraph in G(n,p) that has a given property. For example, in [26] the maximum size of an induced tree in G(n,p = const) was studied and its two-point concentration was proved. Later, in [27] a similar result for the maximum size of an induced forest was obtained.

The next step was to extend these results to the case p(n) = o(1). Specifically, it was proved in [28] that the independence number of G(n,p), where n-2/3+e < p < 1/[log(n)]2, is concentrated on two points.

In this work, in Chapter 3, we prove that the two-concentration point for the maximum size of an induced subtree in G(n,p) can be extended to a fairly wide range of p = o(1). Moreover, in Chapter 1, we initiate the study on this phenomenon on the bipartite model G(n, n,p = const) and we prove that in this model the maximum size of an induced path is concentrated on three consecutive points.

Methodology

The First and Second Moment Methods

Many results on random graph theory rely heavily on inequalities related to the Markov's inequality. Let eX and VarX correspond to the expected value and the variance of a random variable X, respectively. For any non-negative random variable X with a finite expectation, Markov's inequality states that, for any a > 0,

eX

p(X > a) < -.

a

Supposing further that X has a finite second moment, Markov's inequality applied to the random variable |X — eX|2 implies Chebyshev's inequality:

VarX

p(|X — eX| > a) <

a2

As a special instance of the Markov's inequality, for X being a non-negative integer valued random variable, the inequality p(X > 0) < eX holds. Let Xn be a sequence of such random variables. The first moment method relies on showing that eXn = o(1), and thus concluding that Xn = 0 asymptotically almost surely (a.a.s.), that is with probability approaching 1 as n ^ ro. On the other hand, as a special instance of Chebyshev's inequality, for a random variable X with eX > 0, the inequality

VarX

p(X = 0) < p(X < 0) = p(X - eX < -eX) < p(|X - eX| > eX) < ——

(eX)

holds. For a sequence of non-negative Xn, the second moment method relies on showing that the right-hand side of this inequality (with X replaced by Xn) converges to 0, and thus concluding that Xn > 0 a.a.s.

Throughout this work, we will use the first and second moment methods to determine suitable probabilities p E (0,1) under which certain given subgraphs may appear, both in G(n,p) and Gkxn(p) (Theorems 2.1, 2.4, 3.1, 1.10).

Proving Zero-one Law

To prove the validity of the zero-one law for the random k-partite graph model, we use methods similar to those previously applied for establishing zero-one laws in the classic random graph model G(n,p) (see [6]-[8]). In brief, we provide a winning strategy for the Duplicator in the Ehrenfeucht game (see [4], [5]). However, the adaptation of these methods to the k-partite setting is not straightforward. The k-partite model introduces additional constraints due to the partitioning of the vertex set into k distinct classes, which significantly complicates the analysis. A critical step in our approach was to establish a nontrivial result concerning the existence of strictly balanced bipartite graphs with a specified density (Lemma 2.4).

The Ehrenfeucht game was introduced by Ehrenfeucht in 1960 [13] and it was Spencer who in 1991 [17] used it for the first time for proving zero-one laws. Let us go over the rules of the game.

For s G N, the s-round Ehrenfeucht game, represented as EHR(G, H, s), is played on graphs G and H with two players: Duplicator and Spoiler. During each round, Spoiler picks a vertex from one of the graphs, and Duplicator responds by selecting a vertex from the other graph. Both players must pick vertices that haven't been chosen before. This process is repeated s times, resulting in two sequences of vertices (x,... ,xs) from G and (yi,... ,ys) from H. Duplicator wins if the subgraphs induced by these sequences are isomorphic, meaning the isomorphism maps x to y^:

Gljxi,...,xs} = H |{yi,...,ys}.

In 1960 Ehrenfeucht used the Ehrenfeucht game to verify s-elementary equivalence between graphs (Theorem 0.1). We say that graphs G and H are s-elementarily equivalent if, for any FO property L expressed by a sentence ^ with a quantifier depth at most s, either both G G L and H G L, or both G G L and H G L.

Theorem 0.1 (Ehrenfeucht, 1960, [13]). Let G, H be any graphs and s G N. Graphs G and H are s-elementary equivalent if and only if Duplicator has a winning strategy in EHR(G, H, s).

This theorem leads to another result (see [4], [5]) that connects logic to random graphs. It is important to note that the following theorem is applicable to any random graph model.

Theorem 0.2. The random graph G(n,p) satisfies the zero-one law if and only if for every s, letting G(n,p(n)), G(m,p(m)) be independently drawn on disjoint vertex sets,

lim P(Duplicator wins EHR[G(n,p(n)), G(m,p(m)), s]) = 1.

Henceforth, to demonstrate that G(n,p) (or Gkxn(p)) satisfies the zero-one law, it is no longer necessary to have any knowledge of logic. Instead, we simply need to identify a winning strategy for Duplicator.

The first result we present is the validity of the FO 0-1 law for Gkxn(p) when min{p, 1 — p}na ^ ro as n ^ ro for all a > 0 (see Theorem 2.3). In achieving this, we develop a modified version of the s-extension property used in the proof for the case of G(n,p) (see [7], [8]), which we call the k-partite s-extension property, and then, applying Chernoff bound, we show that this property holds a.a.s. in Gkxn(p).

Later, we consider the case when p = n-a. Here, we also successfully extend results from the classical model G(n,p) (see [6], [9]) to the k-partite model Gkxn(p). In Theorem 2.4 we prove that, for a > 0 rational, if a > 2 or a G (1 + il, 1 + \) for some I G N, then Gkxn(p) obeys the zero-one law, and in all the other cases the zero-one law does not hold.

The proof of Theorem 2.4 is divided into four parts. In part 1, we consider a > 2 and show that the resulting graph is empty, where Duplicator always wins. In part 2, we examine a E (1 + , 1 + |) and find that the resulting graph is a forest without trees on I + 2 or more vertices, but with infinitely many copies of trees on at most I +1 vertices. We prove that in this case, Duplicator wins. In part 3, for a = 1 + |, we demonstrate that the number of copies of paths on I + 1 vertices does not converge to either 0 or 1, implying that the zero-one law does not hold. Finally, in part 4, for a E (0,1), we first succeed in establishing a nontrivial result regarding the existence of strictly balanced bipartite graphs with density ^ (see Lemma 1.1), representing a significant improvement over a similar lemma for ordinary graphs (see [9]). Next, we extend Bollobas Theorem [12], which concerns the number of copies of strictly balanced graphs in G(n,p) at their threshold probabilities, to the k-partite model Gkxn(p) (Theorem 2.2), demonstrating that the number of copies of these graphs converges to a Poisson-distributed random variable. Consequently, we find that the probability of Gkxn(p) containing copies of such strictly balanced graphs does not converge to either 0 or 1, indicating that the zero-one law is not valid in this case either.

In Theorem 2.4, we prove that for irrational a > 0, Gkxn(p) follows the zero-one law. While we follow a similar methodology as in the proofs in [4] and [11], adaptations are necessary for the k-partite model, requiring additional combinatorial constructions in every step of the proof.

Proving Concentration in Consecutive Points

Proving the concentration phenomenon for the size of maximum induced structures in random graphs involves a different set of challenges. The standard approach relies on the first and second moment methods. The main difficulty in this part of the proof lies in obtaining a precise estimation of the upper bound for the second moment of the number of copies of these structures in the random graph. This task is particularly challenging due to the complex ways in which different copies of the same induced structure can intersect.

Unlike the case of the independence number, where each independent set is a disjoint collection of vertices, more general induced structures can overlap in various intricate configurations, creating dependencies that complicate the estimation of moments. Therefore, our analysis requires developing new combinatorial tools and techniques to carefully handle these intersections and dependencies, allowing us to derive sharp bounds on the second moment.

Two-point Concentration of Maximum Trees in G(n,p)

In this work, we largely follow the proof framework from [27], where the two-point concentration for the size of maximum induced subtrees was established for the case when p = const (Theorem 1.8). However, when considering p = o(1), the asymptotic behavior of the second moment of the

number of copies of induced trees in the graph changes completely, requiring a refined approach. Let Xk be the number of induced subtrees in G(n,p) of size k. We have that

EXfc = (n)kfc-y-1(1 - p)(2)-k+1.

In our proof we find a value k such that, on one hand, for any constant 5 > 0, it holds that eX|-£.+(5-| = o(1), and on the other hand, for any constant 5 G (0,1), it holds that eX|^-1+5j ^ to. By applying the first moment method, we obtain that p(X-^+5- > 1) = o(1), remaining only to

prove that p(X|k_i+(5j > 1) ^ 1.

For simplicity of notation, set k = Lk — 1 + 5J. Due to the second moment method, we have that

p(X -0)< eXk(Xk — 1) — (eXk)2 + o(1)

p(Xk = 0) - -(eX^-+ 0(1).

We were left to show that the right-hand side of the previous inequality is o(1). To achieve this, we derive suitable upper bounds for eXk(Xk — 1) — (eXk)2. In general, we obtain:

eX(Xk — 1) — (eX)2 - ± (n)(k)(n — J)« — p)2(i)-(l)-2<k-1'irnax^N(k,l,r),

where N(k,l, r) is the number of pairs of labeled trees on [k] and [2k — I] \ [k — I] such that the number of edges in their intersection on I vertices is exactly r.

The difficulty of the proof lies in finding a suitable partition of the set {2,..., k} of values of I, and then determining convenient upper bounds for N(k,l, r) in each of these parts, depending on the level of precision required to ensure that the sum divided by (eXk)2 remains o(1). Some of these upper bounds are the result of a refined combinatorial analysis.

The partition that we consider is the following:

{2,..., k} = [2,1*] U I

k — w p.

u

k — w p

.k — !

— 2p

U ( k — -1, k 2p

where the sequence w(n) ^ to is such that w(n) = o ^vln nj. The exact value of I* can be found in Chapter 3. For the interval [2,1*] we take the obvious bound N(k, I, r) — k2(k-2). For the second and last intervals we take the bound N(k,l, r) — kfc-2/(k,l, r), where f (k, /, r) is an upper bound over all choices of a forest F with r edges on [I], on the number of trees on [k] that induce F on [I]. Finally, for the interval (|_k — w/pJ,k — 1/(2p)] we use the bound N (k,l,r) — r)[f (k,l,r)]2, where r) is the number of forests on [I] with r edges.

*

Three-point Concentration of Maximum Paths in G(n,n,p)

In this part, although we continue applying the first and second moment methods, the bipartite nature of the graph introduces additional restrictions that we must address. Let Xk be the number of induced paths in G(n, n,p) of length k. Due to linearity of expectation, we have that

eX2fc = (n)2(k!)2p2k-1(1 -p)fc2-2fc+1, eX2fc+1 = (k) (k + Jk!(k + 1)!p2k(1 -p)k2-2k.

Here again, we identify the value k such that, on the one hand, for some constant e > 0, it holds that eX2p^,-1-£^+3 = o(1), and on the other hand, for any constant e > 0, it holds that eX2|-£,_1-e-| ^ œ. For simplicity of notation, let g = [k — 1 — e]. To apply the second moment method, we establish the following upper bound on the second factorial moment of X2g:

2g-1 /„\ 2 /OflN 2 „2(2S_1)(i p)2[g2_(2g_1)]

eX2g(X2g — 1) — (eX2g)2 < £ g (g!)22g n2g_vY(v) p f (1 p)/ p

v=1 w ^ 7 mi^ (1 — p)xW p

y 1 — p^

where 7(v) represents the number of possible permutations of the vertices at the intersection, x1 is the number of pairs of common vertices between different parts of the bipartite graph, and is the number of common edges. The crucial part of the proof is to determine an appropriate combination of values for 7(v), x1, and x2. For v < [1. 1gJ, we use the trivial bound 7(v) < v!, while for v > [1.1gJ, we get the bound 7(v) < (2g — v + 1)!22g-v+1. On the other hand, for p < 2

we take x1 = Vf and x2 = v — 1, while for p > 2 we take x1 = Vf and x2 = 0 when v < g and

2

x1 = v— 2(v — g) + 1, x2 = 2(v — g) — 1 when v > g + 1.

Main Results

The main results of our study can be summarized in the following key points:

1. We establish the validity of the first-order zero-one law for the binomial k-partite random graph model Gkxn(p) in two scenarios: dense (where the probability p is constant) and sparse (where p = n-a). Along the way, we prove that for every rational p > 1, there exists a strictly balanced bipartite graph with density p (see [1]).

e_2

2. We demonstrate that for any e > 0 and n- 3e-2 +£ < p = o(1), the maximum size of an induced tree in a binomial random graph G(n, p) is concentrated on two consecutive values with probability tending to 1 as n ^ ro (see [2]).

3. We prove that the maximum size of an induced path in the binomial bipartite random graph G(n,n,p = const) is asymptotically almost surely concentrated on three consecutive points (see [3]).

Scientific Novelty

1. We initiated the study of logical zero-one laws for random multipartite graphs. Along this way, we succeeded in extending many classical results, typically associated with G(n,p), to the case of Gkxn(p). Among these are Theorem 2.1, which addresses the threshold function for containing a copy of a subgraph in Gkxn(p); Theorem 2.2, which discusses the asymptotic distribution of the number of copies of a subgraph within the threshold; and finally, Lemma 2.4, which establishes the existence of strictly balanced bipartite graphs with a given density. Each of these results required the development and application of new techniques that, while being extensions of known results for G(n,p), are significant contributions in their own right.

2. We are the first to provide a partial answer to a previously unresolved question posed in [27] regarding the concentration phenomenon of trees in sparse random graphs. Our approach also introduces new techniques that can be applied to investigate the concentration properties of other subgraphs, such as induced maximum forests.

3. We discovered the concentration phenomena in the random bipartite graph model G(n, n,p), which has not been systematically explored. Our proof techniques can be applied to the study of concentration for other induced subgraphs, such as maximum cycles, trees, and forests.

Scientific and Practical Significance

The significance of our results can be further outlined in two main points. First, by proving the validity of the zero-one law in the random k-partite model, we motivate further investigation into the applicability of this law for other languages other than the first-order, such as the monadic second-order language and other higher logics. The extension of zero-one laws to these new contexts could lead to a deeper understanding of the universality and limits of such probabilistic principles, potentially resulting in a unified theory that encompasses a wide variety of random graph models. Furthermore, proving the existence of strictly balanced bipartite graphs, a necessary step in our proof of the zero-one law, could be applied to various problems not only in random graph theory but also in extremal graph theory.

Second, by establishing the concentration phenomenon for trees in G(n,p = o(1)) and for paths in G(n,n,p = const), we contribute to the investigation of this unique characteristic of random graphs, initially demonstrated for the independence number (see [23]-[25]). Since then, concentration has been shown for various graph structures, such as maximum cycles, trees, and forests, under different conditions on the edge probability p. In this way, our result raises further questions about the generality of the concentration phenomenon: Which classes of subgraphs or induced structures in random graphs exhibit concentration on consecutive points? What specific conditions, like the probability of edge appearance, affect whether concentration will occur? For instance, under what circumstances might concentration on consecutive points fail? How do changes in parameters like

graph sparsity, degree distribution, or edge probability impact these behaviors? For example, in 2022 in [28], it was proven that the concentration on two values for the independence number of G(n,p) fails when p = o((^)2/3). We would be particularly interested in seeing similar results for other graph structures.

Presentation of Results in Conferences

The main results of this study were presented at two prestigious international conferences: the Latin American Congress of Probability and Mathematical Statistics, held in Sao Paulo, Brazil, from July 10 to 14, 2023, and the XI International Petrozavodsk Conference Probabilistic Methods in Discrete Mathematics, held in Karelia, Russia, from May 27 to 31, 2024. Furthermore, some of the techniques used in our proofs were presented at the 63rd and 66th MIPT Scientific Conference, held in Dolgoprudny, Russia, in 2020 and 2024, respectively.

These presentations provided an opportunity to share our findings with leading experts and researchers in the field of random graph theory and combinatorics, fostering discussions and feedback that helped refine and validate our results. At the Latin American Congress of Probability and Mathematical Statistics, we focused on our extension of the zero-one law to the random k-partite graph model, highlighting its implications for understanding the almost sure properties of complex random graph models beyond the classical Erdos-Renyi framework. This presentation was well-received, generating interest in how similar principles might apply to other structured graph models. At the XI International Petrozavodsk Conference Probabilistic Methods in Discrete Mathematics, we presented our findings on the concentration phenomena of trees in sparse random graphs and the initial exploration of concentration phenomena in random bipartite graphs. This sparked engaging discussions on the potential for further research into the concentration behaviors of various subgraphs under different random graph models and conditions.

Publications

We published our findings in three prestigious academic journals: The Moscow Journal of Combinatorics and Number Theory (see [1]), Doklady Mathematics (see [2]) and Proceedings of MIPT (see [3]). All of these journals are included in the VAK list (from the Russian BAK, the Higher Attestation Commission). These publications not only showcase the significance and rigor of our research but also ensure that our contributions reach a broad audience of scholars in the fields of probability theory and combinatorics. Moreover, the inclusion of two articles in Scopus-indexed journals attests to the quality and impact of our work, positioning it within the global discourse on random graph theory.

Заключение диссертации по теме «Другие cпециальности», Буитраго Оропеса Хуан Карлос

4 Conclusions

The main results of our study can be summarized in the following key points:

1. The first-order zero-one laws for G(n,p) can be extended to the binomial k-partite random graph model Gkxn(p) in two distinct scenarios: dense (where the probability p of an edge appearing is constant) and sparse (where p = n-a, with n being the cardinality of each part of the graph). We first demonstrated that Gkxn(p) obeys the zero-one law under the condition that min{p, 1 — p}na ^ to as n ^ to for all a > 0 (Theorem 2.3). Then, for p = n-a and rational a > 0, we established that the zero-one law holds if a > 2 or if a e (1 + i+i, 1 + i) for some l e N, while in all other cases, the zero-one law fails (Theorem 2.4). Lastly, for p = n-a and irrational a > 0, we proved that Gkxn(p) always satisfies the zero-one law (Theorem 2.5).

2. While proving zero-one laws for Gkxn(p), we showed that for every rational p > 1, there exists a strictly balanced bipartite graph with density p (Lemma 2.4).

3. We established that the two-point concentration phenomenon, traditionally associated with the independence number in random graphs, can be extended to the maximum size of an induced tree in sparse random graphs G(n, p). Specifically, we demonstrated that for any

e_2

e > 0 and n- 3e—2 +£ < p = o(1), the maximum size of an induced tree is concentrated on two consecutive values with probability tending to 1 as n ^ to (Theorem 3.1).

4. We discovered the concentration phenomena within the random bipartite graph model G(n, n,p), and demonstrated that the maximum size of an induced path in G(n, n,p = const) is asymptotically almost surely concentrated at four consecutive points (Theorem 1.10).

By proving the validity of the zero-one law in the random k-partite model, we aim to inspire further exploration of this law's applicability to other languages other than the first-order, such as the monadic second-order language and other higher logics. The extension of zero-one laws to these new contexts could lead to a deeper understanding of the universality and limits of such probabilistic principles, potentially resulting in a unified theory that encompasses a wide variety of random graph models.

Similarly, our results on the concentration phenomenon for trees in G(n,p = o(1)) and for paths in G(n, n,p = const) raise compelling questions about the generality of concentration phenomena in random graphs. Specifically, which classes of subgraphs or induced structures exhibit concentration at consecutive points? What conditions, such as the edge probability, determine whether concentration occurs? Furthermore, under what circumstances might concentration on consecutive points fail? Investigating similar phenomena for other graph structures could provide valuable insights into the broader behavior of random graphs and their substructures.

Список литературы диссертационного исследования кандидат наук Буитраго Оропеса Хуан Карлос, 2024 год

References

[1] Buitrago Oropeza J.C. Zero-one laws for random k-partite graphs // Moscow Journal of Combinatorics and Number Theory. — 2021. — Vol. 10, no. 4. — P. 315-337. — DOI: 10.2140/moscow.2021.10.315

[2] Buitrago Oropeza J.C. Maximum Induced Trees in Sparse Random Graphs // Dokl. Math.— 2024. — Vol. 109. — P. 167-169. — D0I:10.1134/S1064562424701989

[3] Buitrago Oropeza J.C. Maximum induced paths in random bipartite graphs // Proceedings of MIPT. — 2024. — Vol. 16, no. 3.— P. 17—23.

[4] Zhukovskii M.E., Raigorodskii A.M. Random graphs: models and asymptotic characteristics // Russian Math. Surveys. — 2015. — Vol. 70, no. 1. — P. 33—81.

[5] Alon N., Spencer J.H. The Probabilistic Method: book // second ed., John Wiley & Sons, Inc., Tel Aviv, New York, 2000.

[6] Shelah S., Spencer J.H. Zero-one laws for sparse random graphs //J. Amer. Math. Soc. — 1988. — Vol. 1. — P. 97-115.

[7] Glebskii Y.V. , Kogan D.I., Liagonkii M.I., Talanov V.A. Range and degree of realizability of formulas the restricted predicate calculus // Cybern Syst Anal. — 1969. — Vol. 5— P. 142—54.

[8] Fagin R. Probabilities in finite models //J. Symbolic Logic. — 1976. — Vol. 41.— P. 50-58.

[9] Rucinski A., Vince A. Strongly balanced graphs and random graphs //J. Graph Theory. — 1986. — Vol. 10, no. 2. — P. 251-264.

[10] Rucinski A., Vince A. Balanced graphs and the problem of subgraphs of a random graph // Proceedings of the Sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1985). — 1985. — Congr. Numer. 49 — P. 181-190.

[11] Spencer J. Counting extensions //J. Combin. Theory Ser. A. — 1990. — Vol. 55, no. 2. — P. 247-255.

[12] Bollobas B. Threshold functions for small subgraphs // Math. Proc. Cambridge Philos. Soc.. — 1981. — Vol. 90, no. 2. — P. 197-206.

[13] Ehrenfeucht A. An application of games to the completness problem for formalized theories // Fund. Math.. — 1960/1961. — Vol. 49. — P. 121-141.

[14] Bollobas B., Thomason A. Hereditary and monotone properties of graphs // The Mathematics of Paul Erdos, II, eds. Graham, Nesetril, Algorithms and Combinatorics, Springer, Berlin. — 1997. — Vol. 14. — P. 70—78.

[15] Vereshagin N. K., Shen A. Languages and calculus: book // Moscow, MCCME. — 2012.

[16] Frieze A., Karonski M. Introduction to Random Graphs // Cambridge: Cambridge University Press. — 2015.

[17] Spencer J. Threshold spectra via the Ehrenfeucht game // Discrete Applied Mathematics. — 1991. — Vol. 30. — P. 235—252.

[18] Erdos P., Renyi A. On random graphs. I // Publ. Math. Debrecen. — 1959. — P. 290—297.

[19] Erdos P., Renyi A. On the evolution of random graphs // Magyar Tud. Akad. Mat. Kutato Int. Kozl. — 1960. — Vol. 5. — P. 17—61.

[20] Erdos P., Renyi A. On the evolution of random graphs // Bull. Inst. Internat. Statist. — 1961. — Vol. 38. — P. 343—347.

[21] Gilbert E. N. Random Graphs // Annals of Mathematical Statistics. — 1959. — Vol. 30, no. 4. — P. 1141—1144.

[22] Janson S., Luczak T., Rucinski A. Random Graphs // New York: Wiley. — 2000.

[23] Bollobas B., Erdos P. Cliques in random graphs // Mathematical Proceedings of the Cambridge Philosophical Society. — 1976. — Vol. 80. — P. 419—427.

[24] Matula D. The largest clique size in a random graph: book // Technical Report, Dept. Comp. Sci., Southern Methodist University, Dallas, Texas. — 1976.

[25] Krivelevich M., Sudakov B., Vu V. H., Wormald N. C. On the probability of independent sets in random graphs // Random Structures & Algorithms. — 2003. — Vol. 22, no. 1. — P. 1—14.

[26] Kamaldinov D., Skorkin A., Zhukovskii M. Maximum sparse induced subgraphs of the binomial random graph with given number of edges // Discrete Mathematics. — 2021. — Vol. 344, no. 2.

[27] Krivoshapko M., Zhukovskii M. Maximum induced forests in random graphs // Discrete Applied Mathematics. — 2021. — Vol. 305. — P. 211—213.

[28] Bohman T., Hofstad J. Two-Point Concentration of the Independence Number of the Random Graph // 2022. arXiv:2208.00117.

[29] Moon J. W. Counting Labelled Trees // Canadian Mathematical Monograph. — 1970.

[30] Jeong H., Tombor B., Albert R., Oltvai Z. N., Barabasi A.-L. The large-scale organization of metabolic networks // Nature. — 2000. — Vol. 407, no. 6804. — P. 651—654.

[31] Barabasi A.-L., Oltvai Z. N. Protein-protein interaction networks and biology // Nature Reviews Genetics. — 2004. — Vol. 5, no. 2. — P. 101—113.

[32] Oltvai Z. N., Barabasi A.-L. Network Biology: Understanding the Cell's Functional Organization // Nature Reviews Genetics. — 2002. — Vol. 3, no. 2. — P. 101—113.

[33] Newman M. E. J. The structure and function of complex networks // SIAM Review. — 2003.

— Vol. 45, no. 2. — P. 167—256.

[34] Newman M. E. J., Strogatz S. H., Watts D. J. Random Graphs as Models of Networks // Proceedings of the National Academy of Sciences. — 2001. — Vol. 98, no. 2. — P. 404—409.

[35] Watts D. J., Strogatz S. H. Collective Dynamics of 'Small-World' Networks // Nature. — 1998. — Vol. 393, no. 6684. — P. 440—442.

[36] Stauffer D., Aharony A. Introduction to Percolation Theory. — Taylor & Francis, 1994.

[37] Albert R., Barabasi A.-L. Statistical Mechanics of Complex Networks // Reviews of Modern Physics. — 2002. — Vol. 74, no. 1. — P. 47—97.

[38] Bollobas B., Janson S., Riordan O. Phase Transitions in Random Structures // Random Structures & Algorithms. — 2007. — Vol. 31, no. 1. — P. 3—122.

[39] Newman M. E. J., Strogatz S. H., Watts D. J. Percolation on Random Graphs with Arbitrary Degree Distributions // Physical Review E. — 2001. — Vol. 64, no. 2. — P. 026118.

[40] Jerrum M., Sinclair A., Vigoda E. Approximating the Permanent with Randomized Algorithms // SIAM Journal on Computing. — 2004. — Vol. 33, no. 6. — P. 1149—1178.

[41] Flajolet P., Martin G. N. Probabilistic Counting Algorithms for Data Base Applications // Journal of Computer and System Sciences. — 1985. — Vol. 31, no. 2. — P. 182—209.

[42] Zhou J., Cui G., Hu S., et al. Graph Neural Networks: A Review of Methods and Applications //AI Open. — 2020. — Vol. 1. — P. 57—81.

[43] Hamilton W. L., Ying R., Leskovec J. Inductive Representation Learning on Large Graphs // Advances in Neural Information Processing Systems. — 2017. — Vol. 30. — P. 1024—1034.

[44] Perozzi B., Al-Rfou R., Skiena S. DeepWalk: Online Learning of Social Representations // Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — 2014. — P. 701—710.

[45] Grover A., Leskovec J. Node2Vec: Scalable Feature Learning for Networks // Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

— 2016. — P. 855—864.

[46] Zhao S., Wu X., He R. Learning Graph Neural Networks with Noise Contrastive Estimation: The Random-Walk Approach // IEEE Transactions on Knowledge and Data Engineering. — 2021. — Vol. 33, no. 8. — P. 3526—3536.

[47] Moschitti A., Basili R., Pennacchiotti M. Random Graphs and Network Analysis in Natural Language Processing // Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. — 2007. — P. 143—152.

[48] Leskovec J., Shrivastava A. Random Graph Representations for Sentence Embeddings // Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing. — 2020. — P. 3516—3526.

[49] Zhu X., Ghahramani Z., Lafferty J. Graph-Based Semi-Supervised Learning // International Journal of Computer Vision. — 2003. — Vol. 20, no. 4. — P. 277—286.

[50] Atwood J., Towsley D. Diffusion Convolutional Neural Networks // Advances in Neural Information Processing Systems. — 2016. — P. 1993—2001.

[51] Lu L., Zhou T. Learning from Massive Network Data for Link Prediction // Proceedings of the National Academy of Sciences. — 2011. — Vol. 108, no. 6. — P. 2300—2305.

[52] On B.-W., Lee D., Chun S. A. Network Data Mining: Methods and Applications // Proceedings of the IEEE International Conference on Data Mining. — 2012. — P. 123—131.

[53] von Luxburg U. Spectral Clustering for Mining Large Data Sets: A Random Walk-based Approach // Journal of Machine Learning Research. — 2007. — Vol. 18. — P. 1985—2006.

[54] Sethu H., Cucuringu M., Subbian K. Graphs and Hypergraphs in Machine Learning: A Review // IEEE Transactions on Knowledge and Data Engineering. — 2021. — Vol. 33, no. 7. — P. 3018—3035.

[55] Pastor-Satorras R., Vespignani A. Epidemic Thresholds in Real Networks // Physical Review Letters. — 2001. — Vol. 86, no. 14. — P. 3200—3203.

[56] Newman M. E. J. The Role of Different Network Topologies in the Spread of Epidemics // Physical Review E. — 2002. — Vol. 66, no. 1. — P. 016128.

[57] Miller J. C. Modeling Infectious Disease Dynamics on Random Networks // Mathematical Biosciences. — 2009. — Vol. 224, no. 1. — P. 59—68.

[58] Meyers L. A., Newman M. E. J., Pourbohloul B. Networks and the Epidemiology of Infectious Disease // Emerging Infectious Diseases. — 2005. — Vol. 11, no. 4. — P. 528—534.

[59] Britton T., Deijfen M., Martin-Lof A. Reed-Frost Models of Epidemics on Random Graphs // Journal of Applied Probability. — 2007. — Vol. 44, no. 4. — P. 214—231.

[60] Ball F., Neal P. The Basic Reproduction Number of a Disease in a Network // Journal of the Royal Statistical Society: Series B (Statistical Methodology). — 2008. — Vol. 70, no. 5. — P. 1041—1064.

[61] Albert R., Jeong H., Barabasi A.-L. The Internet as a Complex Network: Structure, Topology, and Models // Nature. — 1999. — Vol. 401, no. 6749. — P. 130—131.

[62] Gupta P., Kumar P. R. Optimal Capacity of Wireless Networks with Random Node Distribution // IEEE Transactions on Information Theory. — 2000. — Vol. 46, no. 2. — P. 388—404.

[63] Penrose M. Connectivity in Wireless Ad Hoc Networks // Annals of Applied Probability. — 1997. — Vol. 7, no. 2. — P. 340—361.

[64] Faloutsos M., Faloutsos P., Faloutsos C. Modeling the Internet's Large-Scale Topology // ACM SIGCOMM Computer Communication Review. — 1999. — Vol. 29, no. 4. — P. 251—262.

[65] Haenggi M., Ganti R. K. Random Graph Models of Wireless Networks // IEEE Transactions on Wireless Communications. — 2009. — Vol. 7, no. 4. — P. 105—120.

[66] Dousse O., Baccelli F., Thiran P. Scalability of Random Graph Models for Wireless Networks // IEEE Transactions on Information Theory. — 2004. — Vol. 50, no. 8. — P. 2349—2359.

[67] Kleinberg J. The Small-World Phenomenon and Decentralized Search // SIAM Review. — 2000. — Vol. 47, no. 2. — P. 167—196.

[68] Palmer E. M., Bollobas B. The Giant Component in a Random Graph // Journal of Combinatorial Theory, Series B. — 1984. — Vol. 38, no. 2. — P. 179—183.

[69] Bollobas B. Random Graphs // Cambridge University Press. — 2001. — 512 p.

[70] Janson S., Luczak T., Rucinski A. Random Graphs // Wiley, New York. — 2000. — 368 p.

[71] Janson S., Luczak T., Rucinski A. The Evolution of Random Graphs // Random Structures & Algorithms. — 1993. — Vol. 4, no. 3. — P. 233—269.

[72] Bollobas B., Janson S., Riordan O. Phase Transitions in Random Structures // Random Structures & Algorithms. — 2007. — Vol. 31, no. 1. — P. 3—122.

[73] Bollobas B. Random Graphs and the Distribution of Cycles // Discrete Mathematics. — 1981. — Vol. 32, no. 2. — P. 107—115.

[74] Bollobas B., Riordan O. Connectivity in Random Graphs // Random Structures & Algorithms. — 2000. — Vol. 18, no. 2. — P. 83—88.

[75] Alon N., Spencer J. H. Subgraphs in Random Graphs // Discrete Mathematics. — 1992. — Vol. 95, no. 1—3. — P. 125—140.

[76] Bollobas B. Cycles and Connectivity in a Random Graph // Journal of Graph Theory. — 1984. — Vol. 6, no. 2. — P. 121—137.

[77] Bollobas B., Fernandez de la Vega W. The Diameter of a Random Graph // Combinatorica. — 1982. — Vol. 2, no. 2. — P. 125—134.

[78] Bollobas B. Random Bipartite Graphs // Journal of Graph Theory. — 1981. — Vol. 4, no. 2. — P. 249—255.

[79] Frieze A., Luczak T., Promel P. The Evolution of Sparse Random Bipartite Graphs // Discrete Mathematics. — 1996. — Vol. 144, no. 1—3. — P. 57—73.

[80] Janson S. Phase Transitions for the Properties of Random Graphs in a Multitype Setting // Random Structures & Algorithms. — 1996. — Vol. 9, no. 1—2. — P. 1—36.

[81] Ahlswede R., Erdos P. Subgraph Counts in Random Multipartite Graphs and Hypergraphs // Random Structures & Algorithms. — 1989. — Vol. 1, no. 1. — P. 15—43. —

[82] Luczak T., Promel T. Thresholds for Bipartite Subgraphs in Random Graphs // Random Structures & Algorithms. — 1988. — Vol. 4, no. 4. — P. 331—358.

[83] Wormald N. On the Chromatic Number of Random Multipartite Graphs // Discrete Mathematics. — 1983. — Vol. 43, no. 1. — P. 149—164.

[84] Dutta K., Subramanian C. R. On Induced Paths, Holes and Trees in Random Graphs // Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. — 2020. — P. 200—210.