Multi-cyclic graphs in the random graph process with restricted budget
Daniel Iľkovič, Jared León, Xichao Shu · 2024
Read Multi-cyclic graphs in the random graph process with restricted budget by Daniel Iľkovič, Jared León, Xichao Shu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17620.txt.
Introduction
Daniel Iľkovič, Jared León, and Xichao Shu study a 2024 random graph game in which a builder buys edges under a tight budget. Edges of a full graph appear in random order, and each must be bought or passed on the spot. Past work set the best budget for building a tree or a single cycle, but graphs with two cycles stayed open.
The team gives a buy plan for the smallest two-cycle case, a near-complete graph of four points with one edge missing, and proves the budget bound is tight. They do the same for fan graphs, where many triangles share one point.
Catalog record
| CREATOR | Daniel Iľkovič, Jared León, Xichao Shu |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17620
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-cyclic graphs in the random graph process with restricted budget Thanks: (DI, XS): Research supported by the MUNI Award in Science and Humanities (MUNI/I/1677/2018) of the Grant Agency of Masaryk University. Thanks: (JL): Research supported by the Warwick Mathematics Institute Centre for Doctoral Training. Daniel Iľkovič, Jared León, Xichao Shu Abstract . We study a controlled random graph process introduced by Frieze, Krivelevich, and Michaeli. In this model, the edges of a complete graph are randomly ordered and revealed sequentially to a builder. For each edge revealed, the builder must irrevocably decide whether to purchase it. The process is subject to two constraints: the number of observed edges t t and the builder’s budget b b . The goal of the builder is to construct, with high probability, a graph possessing a desired property. Previously, the optimal dependencies of the budget b b on n n and t t were established for constructing a graph containing a fixed tree or cycle, and the authors claimed that their proof could be extended to any unicyclic graph. The problem, however, remained open for graphs containing at least two cycles, the smallest of which is the graph K 4 − K_{4}^{-} (a clique of size four with one edge removed). In this paper, we provide a strategy to construct a copy of the graph K 4 − K_{4}^{-} if b ≫ max { n 6 / t 4 , n 4 / 3 / t 2 / 3 } b\gg\max\left\{n^{6}/t^{4},n^{4/3}/t^{2/3}\right\} , and show that this bound is tight, answering the question posed by Frieze et al. concerning this specific graph. We also give a strategy to construct a copy of a graph consisting of k k triangles intersecting at a single vertex (the k k -fan) if b ≫ max { n 4 k − 1 / t 3 k − 1 , n / t } b\gg\max\left\{n^{4k-1}/t^{3k-1},n/\sqrt{t}\right\} , and also show that this bound is tight. These are the first optimal strategies for constructing a multi-cyclic graph in this random graph model. 1. Introduction Random graph processes have garnered significant attention in recent years, as they offer a natural framework for modeling the evolution of complex networks over time. These processes do not only provide a straightforward, and in some cases the only, method for constructing counterexamples in extremal graph theory but also exhibit strong connections to algorithmic graph theory. In particular, the analysis of random graph processes can lead to valuable insights into the typical running times of algorithms. Random graph processes can be defined in various ways, with one of the most well-known and the simplest being the Erdős–Rényi random graph process, introduced by Erdős and Rényi [ 11 , 12 ] . This process begins with an empty graph on n vertices. At each step, an edge is chosen uniformly at random from the set of non-edges and is added to the graph. At any fixed time t , the random graph process is distributed as a uniform random graph G(n,t) . A graph property is a family of graphs that is invariant under isomorphisms. Such a property is called monotone if it remains preserved under the addition of edges. The hitting time for a monotone property P is defined as the random variable t_{P}=\min\{t\in[N]:\text{$G(n\mathchar 59\penalty\hskip 0.0ptt)$ satisfies $P$ }\} . A significant body of research focuses on identifying the hitting time for various monotone graph properties in the random graph process. 1.1. Random graph process with restricted budget Beyond the classical binomial random graph model, also known as the Erdős–Rényi random graph, numerous fascinating variants have been investigated. Examples include the H -free process [ 9 , 13 , 22 , 27 ] , with particular attention given to the triangle-free process [ 7 , 10 , 14 ] , the more recently studied model of multi-source invasion percolation on the complete graph [ 1 ] , Achlioptas processes proposed by Dimitris Achlioptas [ 6 , 8 , 24 , 25 , 26 ] , and the semi-random graph process suggested by Peleg Michaeli [ 5 ] , and studied recently in [ 3 , 4 , 16 , 17 , 18 , 19 , 23 ] . Recently, Frieze, Krivelevich, and Michaeli [ 15 ] introduced the following controlled random graph process. Consider a Builder who observes the edges of a random permutation e_{1},\ldots,e_{N} one at a time and must make an irrevocable decision whether to select e_{i} upon seeing it. A (t,b) -strategy is an online algorithm (either deterministic or randomized) that Builder employs in this setting, where observes only the first t edges of the random permutation of E(K_{n}) and is permitted to select at most b of them. The Builder’s goal is for her graph to achieve a specified monotone graph property of P . For instance, there exists a simple (t_{\text{con}},n-1) -strategy ensuring that Builder’s graph becomes connected at the hitting time for connectivity: Builder selects an edge if and only if it reduces the number of connected components in the graph. In this model, the problems of constructing spanning structures such as a perfect matching, a Hamilton cycle, a graph with a prescribed minimum degree, or a graph with a fixed level of connectivity have been extensively studied in [ 2 , 15 , 20 , 21 ] . It was demonstrated that for these properties, a linear edge budget suffices to achieve the desired structure at or shortly after the hitting time. This contrasts sharply with the superlinear hitting time required for achieving minimum degree one, which, as is well known, occurs at \left(\frac{1}{2}+o(1)\right)n\log n . Much less is known about the construction of small subgraphs, specifically those whose number of vertices remains bounded independently of the size of the host graph. The problem of constructing trees and unicyclic graphs was addressed in [ 15 ] . Notably, Frieze et al. [ 15 ] established the following results. Theorem 1.1 . Let k\geqslant 3 be an integer and let T be a k -vertex tree. If t\geqslant b\gg\max\{(n/t)^{k-2},1\} then there exists a (t,b) -strategy B of Builder such that \lim_{n\to\infty}\mathbb{P}(T\subseteq B_{t})=1 and if b\ll(n/t)^{k-2} then for any (t,b) -strategy B of Builder, \lim_{n\to\infty}\mathbb{P}(T\subseteq B_{t})=0. Theorem 1.2 . Let k\geqslant 1 be an integer and let H=C_{2k+1} or H=C_{2k+2} . Write b^{*}=b^{*}(n,t,k)=\max\{n^{k+2}/t^{k+1},n/\sqrt{t}\} . If t\gg n and b\gg b^{*} then there exists a (t,b) -strategy B of Builder such that \lim_{n\to\infty}\mathbb{P}(H\subseteq B_{t})=1, and if t\ll n or b\ll b^{*} then for any (t,b) -strategy B of Builder, \lim_{n\to\infty}\mathbb{P}(H\subseteq B_{t})=0. Theorems 1.1 and 1.2 analyze the budget thresholds required for constructing trees and cycles. Extending these results to any fixed unicyclic graph is straightforward: once the cycle is formed, the remaining forest can be efficiently built with a constant budget. Consequently, the smallest graph not covered by their results is the graph on four vertices and five edges, K_{4}^{-} (the diamond). A notable challenge is that several natural strategies lead to different upper bounds, each one optimal within distinct time regimes. A similar issue arises in the case of constructing cycles. 1.2. Our results In this paper, we discuss optimal strategies for constructing small subgraphs with multiple cycles. Firstly,