ترغب بنشر مسار تعليمي؟ اضغط هنا

Independent sets of a given size and structure in the hypercube

130   0   0.0 ( 0 )
 نشر من قبل Will Perkins
 تاريخ النشر 2021
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

We determine the asymptotics of the number of independent sets of size $lfloor beta 2^{d-1} rfloor$ in the discrete hypercube $Q_d = {0,1}^d$ for any fixed $beta in [0,1]$ as $d to infty$, extending a result of Galvin for $beta in [1-1/sqrt{2},1]$. Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hard core model at any fixed fugacity $lambda>0$. In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.



قيم البحث

اقرأ أيضاً

We consider numbers and sizes of independent sets in graphs with minimum degree at least $d$, when the number $n$ of vertices is large. In particular we investigate which of these graphs yield the maximum numbers of independent sets of different size s, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.
189 - Ewan Davies , Will Perkins 2021
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density $alpha_c(Delta)$ and provide (i) for $alpha < alpha_c(Delta)$ randomiz ed polynomial-time algorithms for approximately sampling and counting independent sets of given size at most $alpha n$ in $n$-vertex graphs of maximum degree $Delta$; and (ii) a proof that unless NP=RP, no such algorithms exist for $alpha>alpha_c(Delta)$. The critical density is the occupancy fraction of hard core model on the clique $K_{Delta+1}$ at the uniqueness threshold on the infinite $Delta$-regular tree, giving $alpha_c(Delta)simfrac{e}{1+e}frac{1}{Delta}$ as $Deltatoinfty$.
We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on $n$ vertices with maximum degree $d$, showing that an independent set drawn uniformly at random from such a graph has expected size at le ast $(1+o_d(1)) frac{log d}{d}n$. This gives an alternative proof of Shearers upper bound on the Ramsey number $R(3,k)$. We then prove that the total number of independent sets in a triangle-free graph with maximum degree $d$ is at least $exp left[left(frac{1}{2}+o_d(1) right) frac{log^2 d}{d}n right]$. The constant $1/2$ in the exponent is best possible. In both cases, tightness is exhibited by a random $d$-regular graph. Both results come from considering the hard-core model from statistical physics: a random independent set $I$ drawn from a graph with probability proportional to $lambda^{|I|}$, for a fugacity parameter $lambda>0$. We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree $d$. The bound is asymptotically tight in $d$ for all $lambda =O_d(1)$. We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.
113 - Vladimir Nikiforov 2008
Let k_r(n,m) denote the minimum number of r-cliques in graphs with n vertices and m edges. For r=3,4 we give a lower bound on k_r(n,m) that approximates k_r(n,m) with an error smaller than n^r/(n^2-2m). The solution is based on a constraint minimizat ion of certain multilinear forms. In our proof, a combinatorial strategy is coupled with extensive analytical arguments.
Given integers $k$ and $m$, we construct a $G$-arc-transitive graph of valency $k$ and an $L$-arc-transitive oriented digraph of out-valency $k$ such that $G$ and $L$ both admit blocks of imprimitivity of size $m$.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا