Тема: Threshold probabilities of containing copies of certain spanning subgraphs in the random graph

In the study of random graphs, thresholds for various properties of interest play a crucial role in under-standing the emergence and disappearence of specific graph properties since its initiation by Erdos and Renyi. And thresholds for containment of copies of specific graphs in the binomial random graph G(n,p) or uniform random graph G(n, m) have been the subject of the most powerful work in this area. For example, you can see the most general results in. This general topic has applications in areas such as:
• Characterizing the behavior of complex networks
• Designing efficient algorithms for graph optimization problems
• Understanding the emergence of specific patterns and structures in random graphs
But in the case of general spanning structures only sufficient conditions are known, which lead to upper bound for the threshold probability. However, it follows from the recent proof of the expectation threshold conjecture of Kahn and Kalai that the threshold for any graph differs from the union-bound estimate by a logarithmic factor. Thus, only the question of the this additional factor limited between 1 and ln n remains unclear. It is worth noting that both of these estimates are achievable. For some sparse graphs with a large number of bridges the additional logarithmic factor appears in the threshold probability, but already for the second power of Hamiltonian cycle this factor is equal to 1.
Until recently, the most general result providing upper bounds was the result of O.Riordan (see the Theorem 3.1) based on the second-moment method. This estimate, as can be seen, is directly connected with the maximum density of subgraphs of our spanning structure. To be more precise, we consider the maximum value of the ratio of the number of edges — E(H) — to the number of vertices minus 2 — (V(H) — 2) — over all subgraphs H. In some cases it gives asymptotically optimal upper bounds. For example, it is different lattices, hypercubes, for the study of which Riordan proved his result. Also it is k-th powers of Hamilton cycles for k > 3.
For some general spanning structures the threshold is known. In particular, the case of usual Hamilton cycles has been investigated quite a long time ago. The threshold in this case equals to ^^^. This follows not even from expectation considerations but out of necessity to avoid isolated vertices. Also the result for such popular structures as spanning trees, F-factors and, in particular, for perfect matchings is known. It should be noted that the most difficult structure to study is apparently the second power of Hamiltonian cycle and similar structures. This graph is ordinary Hamiltonian cycle with ”ear” diagonals drawn through one vertex. Quite recently, Kahn, Narayanan and Park proved that the theshold for its appearance is -1^, using the proof approach of (the last work established the fractional expectation threshold conjecture of Talagrand). However, the question of finding the theshold probability of this structure accurate to a constant has still not been resolved, although a large number of attempts have been made.
Other similar ’’cyclic” structures with overlapping are of particular interest. For example, the most natural generalization is t overlapping spanning Kr cycles for 1 vertices. Frieze in a recent paper find that in the case of t =1 the threshold is n-r log (2) n. In the case of t > 3, Riordan’s upper bound [20] is sufficient. The answer is also known in the case when t = 2 (we mention it a couple of lines later). Note, that the second power of Hamilton cycle exactly corresponds to the case t = 2, r = 3.
Finally, we would like to mention excellent general survey by Bottcher in this topic of spanning structures, which provides references to many other results.
In their work, Kahn, Narayanan and Park suggested the new approach to prove the upper bound: the so-called fragmentation process along with the spreadness property of hypergraph. The idea is to represent a uniform random graph G(n, m) as a union of several random graphs G(n, mf) in order to consider small pieces — fragments — of the original graph. Using this process the total variance can be decomposed into a sum of variances and estimated, which can not be done in ”direct” approach. The number of random graphs in decomposition is called the number of rounds of the fragmentation process.
For example, Kahn, Narayanan and Park used only 2 rounds in their proof in. Several subsequent works developed this technology. In particular, in authors applied this technology for finding the threshold for appearance the spanning 2-overlapping C4-cycles (n-3 j and for spanning 2-overlapping Kr-cycles for r > 4 (n ■ 1). They have formulated general result of fragmentation process — the fragmentation lemma, which from the fact that hypergraph of all copies of spanning structure has the q-spreadness propery, allows us to obtain a general upper bound for the threshold probability in terms of q. This lemma is based on a fragmentation process with an arbitrary constant number of rounds, in contrast to work [15] with 2 rounds and with logarithmic number of rounds. In my thesis we apply exactly the technology described in...
Купить

In this work, for another family of graphs - triangulations of a k-gon, the threshold probability was found up to a constant. Essentially, the upper estimate was obtained from considerations of the ratio of the number of vertices and edges in the triangulation constructed in the work. Due to the planarity of the subgraph under consideration, this property is equivalent to the fact that the ratio of the number of internal vertices in any simple cycle to the length of this cycle does not exceed the same value for the entire graph. This statement is some analogue of the property of uniformity: the absence of subgraphs with too high (low) density. This property was proven using the isoperimetric inequality due to the "lattice” structure of the triangulation.
For further research it is necessary to do the following. Firstly, in the case when the boundary of the k-gon consists of almost all the vertices of the graph, the statement is not proven. This is due to the inability to directly apply the fragmentation process with a large number of rounds due to the presence of either a small dense piece or a vertex of unbounded constant degree in the constructed triangulation. However, this case has already been tested, but is not presented in this work due to the increase in text size. Essentially, this is the same test as in the paper [15] about the second degree of the Hamiltonian cycle.
Secondly, what is actually interesting and challenging is the problem of finding a given threshold probability along with a constant. This problem does not seem simple, at least in all cases, since with £ tending to unity, the density of this graph is practically equal to the density of the second degree of the Hamiltonian cycle, for which the problem has not yet been solved.
Купить