Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe sharp threshold for jigsaw percolation in random graphs
61
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are `jointly connected. Bollobas, Riordan, Slivken and Smith proved that when the two graphs are independent binomial random graphs, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $Thetaleft( frac{1}{nln n} right)$. We show that this threshold is sharp, and that it lies at $frac{1}{4nln n}$.
rate research
Read More
Suppose that $mathcal{P}$ is a property that may be satisfied by a random code $C subset Sigma^n$. For example, for some $p in (0,1)$, $mathcal{P}$ might be the property that there exist three elements of $C$ that lie in some Hamming ball of radius $pn$. We say that $R^*$ is the threshold rate for $mathcal{P}$ if a random code of rate $R^{*} + varepsilon$ is very likely to satisfy $mathcal{P}$, while a random code of rate $R^{*} - varepsilon$ is very unlikely to satisfy $mathcal{P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably symmetric. For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property $mathcal{P}$ above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.
Jigsaw percolation is a nonlocal process that iteratively merges connected clusters in a deterministic puzzle graph by using connectivity properties of a random people graph on the same set of vertices. We presume the Erdos--Renyi people graph with edge probability p and investigate the probability that the puzzle is solved, that is, that the process eventually produces a single cluster. In some generality, for puzzle graphs with N vertices of degrees about D (in the appropriate sense), this probability is close to 1 or small depending on whether pD(log N) is large or small. The one dimensional ring and two dimensional torus puzzles are studied in more detail and in many cases the exact scaling of the critical probability is obtained. The paper settles several conjectures posed by Brummitt, Chatterjee, Dey, and Sivakoff who introduced this model.
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4.
A bootstrap percolation process on a graph G is an infection process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round every uninfected node which has at least r infected neighbours becomes infected and remains so forever. The parameter r > 1 is fixed. We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank 1. Assuming that initially every vertex is infected independently with probability p > 0, we provide a law of large numbers for the number of vertices that will have been infected by the end of the process. We also focus on a special case of such random graphs which exhibit a power-law degree distribution with exponent in (2,3). The first two authors have shown the existence of a critical function a_c(n) such that a_c(n)=o(n) with the following property. Let n be the number of vertices of the underlying random graph and let a(n) be the number of the vertices that are initially infected. Assume that a set of a(n) vertices is chosen randomly and becomes externally infected. If a(n) << a_c(n), then the process does not evolve at all, with high probability as n grows, whereas if a(n)>> a_c(n), then with high probability the final set of infected vertices is linear. Using the techniques of the previous theorem, we give the precise asymptotic fraction of vertices which will be eventually infected when a(n) >> a_c (n) but a(n) = o(n). Note that this corresponds to the case where p approaches 0.
A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$, denoted by $D(G)$, is the minimum number of colors required for such coloring. The distinguishing threshold of $G$, denoted by $theta(G)$, is the minimum number $k$ such that every $k$-coloring of $G$ is distinguishing. In this paper, we study $theta(G)$, find its relation to the cycle structure of the automorphism group of $G$ and prove that $theta(G)=2$ if and only if $G$ is isomorphic to $K_2$ or $overline{K_2}$. Moreover, we study graphs that have the distinguishing threshold equal to 3 or more and prove that $theta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $overline{K_n}$. Finally, we consider the graphs in the Johnson scheme for their distinguishing numbers and thresholds.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
