اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLarge components in random induced subgraphs of n-cubes
108
0
0.0
(
0
)
تأليف
Christian M. Reidys
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we study random induced subgraphs of the binary $n$-cube, $Q_2^n$. This random graph is obtained by selecting each $Q_2^n$-vertex with independent probability $lambda_n$. Using a novel construction of subcomponents we study the largest component for $lambda_n=frac{1+chi_n}{n}$, where $epsilonge chi_nge n^{-{1/3}+ delta}$, $delta>0$. We prove that there exists a.s. a unique largest component $C_n^{(1)}$. We furthermore show that $chi_n=epsilon$, $| C_n^{(1)}|sim alpha(epsilon) frac{1+chi_n}{n} 2^n$ and for $o(1)=chi_nge n^{-{1/3}+delta}$, $| C_n^{(1)}| sim 2 chi_n frac{1+chi_n}{n} 2^n$ holds. This improves the result of cite{Bollobas:91} where constant $chi_n=chi$ is considered. In particular, in case of $lambda_n=frac{1+epsilon} {n}$, our analysis implies that a.s. a unique giant component exists.
قيم البحث
اقرأ أيضاً
In this note, we study large deviations of the number $mathbf{N}$ of intercalates ($2times2$ combinatorial subsquares which are themselves Latin squares) in a random $ntimes n$ Latin square. In particular, for constant $delta>0$ we prove that $Pr(mat
hbf{N}le(1-delta)n^{2}/4)leexp(-Omega(n^{2}))$ and $Pr(mathbf{N}ge(1+delta)n^{2}/4)leexp(-Omega(n^{4/3}(log n)^{2/3}))$, both of which are sharp up to logarithmic factors in their exponents. As a consequence, we deduce that a typical order-$n$ Latin square has $(1+o(1))n^{2}/4$ intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.
Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independe
nce number of $G(n,p)$ by ErdH{o}s and Bollobas, and Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C/nle p le 0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2log_q(np)$, where $q= frac{1}{1-p}$.
We study Hamiltonicity in random subgraphs of the hypercube $mathcal{Q}^n$. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $mathcal{Q}^n$ according to a uniformly chosen random orderi
ng. Then, with high probability, as soon as the graph produced by this process has minimum degree $2k$, it contains $k$ edge-disjoint Hamilton cycles, for any fixed $kinmathbb{N}$. Secondly, we obtain a perturbation result: if $Hsubseteqmathcal{Q}^n$ satisfies $delta(H)geqalpha n$ with $alpha>0$ fixed and we consider a random binomial subgraph $mathcal{Q}^n_p$ of $mathcal{Q}^n$ with $pin(0,1]$ fixed, then with high probability $Hcupmathcal{Q}^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $kinmathbb{N}$. In particular, both results resolve a long standing conjecture, posed e.g. by Bollobas, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. Our techniques also show that, with high probability, for all fixed $pin(0,1]$ the graph $mathcal{Q}^n_p$ contains an almost spanning cycle. Our methods involve branching processes, the Rodl nibble, and absorption.
The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the ErdH{o}s-Renyi random graph $G(n,m)$. Our approach is based on applying Freedmans inequalities for the probab
ility of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related $G(n,p)$ model.
It is an intriguing question to see what kind of information on the structure of an oriented graph $D$ one can obtain if $D$ does not contain a fixed oriented graph $H$ as a subgraph. The related question in the unoriented case has been an active are
a of research, and is relatively well-understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs, and provide some results on the global behavior of the orientation of $D$. For the case that $H$ is an oriented four-cycle we prove: in every $H$-free oriented graph $D$, there is a pair $A,Bssq V(D)$ such that $e(A,B)ge e(D)^{2}/32|D|^{2}$ and $e(B,A)le e(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case $H$ is an oriented six-cycle, and a more precise result in the case $D$ is dense and $H$ is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph $D$, and provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
