ﻻ يوجد ملخص باللغة العربية
We determine the size of $k$-core in a large class of dense graph sequences. Let $G_n$ be a sequence of undirected, $n$-vertex graphs with edge weights ${a^n_{i,j}}_{i,j in [n]}$ that converges to a kernel $W:[0,1]^2to [0,+infty)$ in the cut metric. Keeping an edge $(i,j)$ of $G_n$ with probability $min { {a^n_{i,j}}/{n},1 }$ independently, we obtain a sequence of random graphs $G_n(frac{1}{n})$. Denote by $C_k(G)$ the size of $k$-core in graph $G$, by $X^W$ the branching process associated with the kernel $W$, by $mathcal{A}$ the property of a branching process that the initial particle has at least $k$ children, each of which has at least $k-1$ children, each of which has at least $k-1$ children, and so on. Using branching process and theory of dense graph limits, under mild assumptions we obtain the size of $k$-core of random graphs $G_n(frac{1}{n})$, begin{align*} C_kleft(G_nleft(frac{1}{n}right)right) =n mathbb{P}_{X^W}left(mathcal{A}right) +o_p(n). end{align*} Our result can also be used to obtain the threshold of appearance of a $k$-core of order $n$. In addition, we obtain a probabilistic result concerning cut-norm and branching process which might be of independent interest.
Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of low-degree dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbourhood. We prove that th
Let $mathcal{H}$ denote a collection of subsets of ${1,2,ldots,n}$, and assign independent random variables uniformly distributed over $[0,1]$ to the $n$ elements. Declare an element $p$-present if its corresponding value is at most $p$. In this pape
Given a natural number k and an orientable surface S of finite type, define the k-curve graph to be the graph with vertices corresponding to isotopy classes of essential simple closed curves on S and with edges corresponding to pairs of such curves a
We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Ko
The order-$k$ Voronoi tessellation of a locally finite set $X subseteq mathbb{R}^n$ decomposes $mathbb{R}^n$ into convex domains whose points have the same $k$ nearest neighbors in $X$. Assuming $X$ is a stationary Poisson point process, we give expl