Sahar Diskin

activity

20212026

most citedPercolation on Irregular High-dimensional Product Graphs

3 citations · 6 across the 26 of their papers we have counts for

collaborators

31 papers

math.CO2026

Long induced cycles in pseudorandom graphs

Sahar Diskin, Lyuben Lichev, Michael Krivelevich +1

We show that, for some absolute constants $c_{1}, c_{2} > 0$ , every $(n, d, λ)$ -graph with $λ \leq c_{1} d$ contains an induced cycle of length at least $c_{2} n lo g (d / λ) / d$ . This is best possible…

math.CO2026

The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes

Micha Christoph, Sahar Diskin, Lyuben Lichev +1

We study the edge-expansion of the graph of a random $0/1$ polytope $P_{p}^{d}$ , defined as the convex hull of a random subset of the points in ${0, 1}^{d}$ where every point is retaine…

math.CO2026

Supercritical Site Percolation on Regular Graphs

Sahar Diskin, Michael Krivelevich, Itay Markbreit

We consider site (vertex) percolation on $d$ -regular graphs, for both constant-degree and growing-degree cases. We give sufficient, and relatively tight, conditions for the emergen…

math.PR2026

Supercritical sharpness of percolation

Sahar Diskin, Philip Easo, Ritvik Ramanan Radhakrishnan +2

We prove that for supercritical percolation on every infinite transitive graph, the probability that the origin belongs to a finite cluster of size at least $n$ decays exponentiall…

math.PR2025

Diameter and mixing time of the giant component in the percolated hypercube

Michael Anastos, Sahar Diskin, Lyuben Lichev +1

We consider bond percolation on the $d$ -dimensional binary hypercube with $p = c / d$ for fixed $c > 1$ . We prove that the typical diameter of the giant component $L_{1}$ is of order $Θ(d)…

math.CO2025

Cycle lengths in the percolated hypercube

Michael Anastos, Sahar Diskin, Joshua Erde +3

Let $Q_{p}^{d}$ be the random subgraph of the $d$ -dimensional binary hypercube obtained after edge-percolation with probability $p$ . It was shown recently by the authors that, for ever…

math.CO2025

A large hole in pseudo-random graphs

Sahar Diskin, Michael Krivelevich, Itay Markbreit +1

We show that there exist constants $δ_{1}, δ_{2} > 0$ such that if $G$ is an $(n, d, λ)$ -graph with $λ / d \leq δ_{1}$ , then $G$ contains an induced cycle of length at least $δ_{2} n / d$ . We further d…

math.CO2025

Spanning trees of bounded degree in random geometric graphs

Michael Anastos, Sahar Diskin, Dawid Ignasiak +2

We determine the sharp threshold for the containment of all $n$ -vertex trees of bounded degree in random geometric graphs with $n$ vertices. This provides a geometric counterpart o…

math.CO2025

Nearly spanning cycle in the percolated hypercube

Michael Anastos, Sahar Diskin, Joshua Erde +3

Let $Q^{d}$ be the $d$ -dimensional binary hypercube. We form a random subgraph $Q_{p}^{d} \subseteq Q^{d}$ by retaining each edge of $Q^{d}$ independently with probability $p$ . We show that,…

math.CO2025

Universality of the matching number in percolated regular graphs

Sahar Diskin, Mihyun Kang, Lyuben Lichev

Fix a sequence of $d$ -regular graphs $(G_{d})_{d \in N}$ and denote by $G_{d, p}$ the graph obtained from $G_{d}$ after edge-percolation with probability $p = c / d$ , for a constant…

math.CO2024

Tree tilings in random regular graphs

Sahar Diskin, Ilay Hoshen, Maksim Zhukovskii

We show that for every $ε > 0$ there exists a sufficiently large $d_{0} \in N$ such that for every $d \geq d_{0}$ , whp the random $d$ -regular graph $G (n, d)$ contains a $T$ -factor f…

math.CO2024

Minimum degree $k$ and $k$ -connectedness usually arrive together

Sahar Diskin, Anna Geisler

Let $d, n \in N$ be such that $d = ω (1)$ , and $d \leq n^{1 - a}$ for some constant $a > 0$ . Consider a $d$ -regular graph $G = (V, E)$ and the random graph process that starts with the…

math.CO2024

Components, large and small, are as they should be II: supercritical percolation on regular graphs of constant degree

Sahar Diskin, Michael Krivelevich

Let $d \geq 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…

math.CO2024

Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree

Sahar Diskin, Michael Krivelevich

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\cdo…

math.CO2024

Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs

Sahar Diskin, Joshua Erde, Mihyun Kang +1

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 $ε > 0$ , there exis…

math.CO2024

Long cycles in percolated expanders

Maurício Collares, Sahar Diskin, Joshua Erde +1

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 N$ and constants $0<c…

math.CO2024

Saturation in Random Hypergraphs

Sahar Diskin, Ilay Hoshen, Dániel Korándi +2

Let $K_{n}^{r}$ be the complete $r$ -uniform hypergraph on $n$ vertices, that is, the hypergraph whose vertex set is $[n] := {1, 2, ..., n}$ and whose edge set is $(r [ n ])$ . We form…

math.PR2024

Hitting time of connectedness in the random hypercube process

Sahar Diskin, Michael Krivelevich

We present a short and self-contained proof of a classical result due to Bollobás (1990): in the random hypercube process, with high probability the hitting time of connectedness e…

math.CO2024

Perfect Matching in Product Graphs and in their Random Subgraphs

Sahar Diskin, Anna Geisler

For $t \in N$ and ever $i \in [t]$ , let $H_{i}$ be a $d_{i}$ -regular connected graph with $1 < ∣ V (H_{i}) ∣ \leq M$ for some integer $M \geq 2$ . Let $G = □_{i = 1}^{t} H_{i}$ be the $t$ -dime…

math.CO2023

Climbing up a random subgraph of the hypercube

Michael Anastos, Sahar Diskin, Dor Elboim +1

Let $Q^{d}$ be the $d$ -dimensional binary hypercube. We say that $P = {v_{1}, \dots, 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…

math.CO2023

Percolation through Isoperimetry

Sahar Diskin, Joshua Erde, Mihyun Kang +1

We provide a sufficient condition on the isoperimetric properties of a regular graph $G$ of growing degree $d$ , under which the random subgraph $G_{p}$ typically undergoes a phase tr…

math.PR2023

Isoperimetric Inequalities and Supercritical Percolation on High-dimensional Graphs

Sahar Diskin, Joshua Erde, Mihyun Kang +1

It is known that many different types of finite random subgraph models undergo quantitatively similar phase transitions around their percolation thresholds, and the proofs of these…

math.CO2023

A Jump of the Saturation Number in Random Graphs?

Sahar Diskin, Ilay Hoshen, Maksim Zhukovskii

For graphs $G$ and $F$ , the saturation number $sat (G, F)$ is the minimum number of edges in an inclusion-maximal $F$ -free subgraph of $G$ . In 2017, Korándi and Sudakov init…

math.CO2022

On vertex Ramsey graphs with forbidden subgraphs

Sahar Diskin, Ilay Hoshen, Michael Krivelevich +1

A classical vertex Ramsey result due to Nešetřil and Rödl states that given a finite family of graphs $F$ , a graph $A$ and a positive integer $r$ , if every graph $B\in\ma…

Long induced cycles in pseudorandom graphs

The Mihail-Vazirani conjecture and strong edge-expansion in random 0/1 polytopes

Supercritical Site Percolation on Regular Graphs

Supercritical sharpness of percolation

Diameter and mixing time of the giant component in the percolated hypercube

Cycle lengths in the percolated hypercube

A large hole in pseudo-random graphs

Spanning trees of bounded degree in random geometric graphs

Nearly spanning cycle in the percolated hypercube

Universality of the matching number in percolated regular graphs

Tree tilings in random regular graphs

Minimum degree k and k-connectedness usually arrive together

Components, large and small, are as they should be II: supercritical percolation on regular graphs of constant degree

Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree

Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs

Long cycles in percolated expanders

Saturation in Random Hypergraphs

Hitting time of connectedness in the random hypercube process

Perfect Matching in Product Graphs and in their Random Subgraphs

Climbing up a random subgraph of the hypercube

Percolation through Isoperimetry

Isoperimetric Inequalities and Supercritical Percolation on High-dimensional Graphs

A Jump of the Saturation Number in Random Graphs?

On vertex Ramsey graphs with forbidden subgraphs

The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes

Minimum degree $k$ and $k$ -connectedness usually arrive together