Zobrazeno 1 - 10
of 722
pro vyhledávání: '"Krivelevich, Michael"'
Autor:
Diskin, Sahar, Krivelevich, Michael
Let $d\ge 3$ be a fixed integer. Let $y:= y(p)$ be the probability that the root of an infinite $d$-regular tree belongs to an infinite cluster after $p$-bond-percolation. We show that for every constants $b,\alpha>0$ and $1<\lambda< d-1$, there exis
Externí odkaz:
http://arxiv.org/abs/2408.04599
Autor:
Diskin, Sahar, Krivelevich, Michael
We provide sufficient conditions for a regular graph $G$ of growing degree $d$, guaranteeing a phase transition in its random subgraph $G_p$ similar to that of $G(n,p)$ when $p\cdot d\approx 1$. These conditions capture several well-studied graphs, s
Externí odkaz:
http://arxiv.org/abs/2408.04597
Given a graph $G$ and $p\in [0,1]$, the random subgraph $G_p$ is obtained by retaining each edge of $G$ independently with probability $p$. We show that for every $\epsilon>0$, there exists a constant $C>0$ such that the following holds. Let $d\ge C$
Externí odkaz:
http://arxiv.org/abs/2407.16458
Given a graph $G$ and probability $p$, we form the random subgraph $G_p$ by retaining each edge of $G$ independently with probability $p$. Given $d\in\mathbb{N}$ and constants $00$, we show that if every subset $S\subseteq V(G)$ of
Externí odkaz:
http://arxiv.org/abs/2407.11495
We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph $G(n,p)$ with constant diameter with high probability. We get a tight (up to a constant factor) answer for all $p>n^{-1+o(1)}$ outside "thr
Externí odkaz:
http://arxiv.org/abs/2404.18318
Autor:
Diskin, Sahar, Krivelevich, Michael
We present a short and self-contained proof of a classical result due to Bollob\'as (1990): in the random hypercube process, with high probability the hitting time of connectedness equals the hitting time of having minimum degree at least one.
C
C
Externí odkaz:
http://arxiv.org/abs/2404.09289
Autor:
Hefetz, Dan, Krivelevich, Michael
Given positive integers $k \leq m$ and a graph $G$, a family of lists $L = \{L(v) : v \in V(G)\}$ is said to be a random $(k,m)$-list-assignment if for every $v \in V(G)$ the list $L(v)$ is a subset of $\{1, \ldots, m\}$ of size $k$, chosen uniformly
Externí odkaz:
http://arxiv.org/abs/2402.09998
We study several basic problems about colouring the $p$-random subgraph $G_p$ of an arbitrary graph $G$, focusing primarily on the chromatic number and colouring number of $G_p$. In particular, we show that there exist infinitely many $k$-regular gra
Externí odkaz:
http://arxiv.org/abs/2312.08340
Let $Q^d$ be the $d$-dimensional binary hypercube. We say that $P=\{v_1,\ldots, v_k\}$ is an increasing path of length $k-1$ in $Q^d$, if for every $i\in [k-1]$ the edge $v_iv_{i+1}$ is obtained by switching some zero coordinate in $v_i$ to a one coo
Externí odkaz:
http://arxiv.org/abs/2311.16631
A graph is called $d$-rigid if there exists a generic embedding of its vertex set into $\mathbb{R}^d$ such that every continuous motion of the vertices that preserves the lengths of all edges actually preserves the distances between all pairs of vert
Externí odkaz:
http://arxiv.org/abs/2311.14451