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

Showing math.COShow all

26 papers · 1 filter

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.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.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.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…

math.CO2022★ 3 cited

Percolation on Irregular High-dimensional Product Graphs

Sahar Diskin, Joshua Erde, Mihyun Kang +1

We consider bond percolation on high-dimensional product graphs $G = □_{i = 1}^{t} G^{(i)}$ , where $□$ denotes the Cartesian product. We call the $G^{(i)}$ the base graphs and…

math.CO2022

Heavy and Light Paths and Hamilton Cycles

Sahar Diskin, Dor Elboim

Given a graph $G$ , we denote by $f (G, u_{0}, k)$ the number of paths of length $k$ in $G$ starting from $u_{0}$ . In graphs of maximum degree 3, with edge weights $i . i . d .$ with $e x p (1)$ ,…

math.CO2022★ 1 cited

Percolation on High-dimensional Product Graphs

Sahar Diskin, Joshua Erde, Mihyun Kang +1

We consider percolation on high-dimensional product graphs, where the base graphs are regular and of bounded order. In the subcritical regime, we show that typically the largest co…

math.CO2022★ 1 cited

Expansion in Supercritical Random Subgraphs of Expanders and its Consequences

Sahar Diskin, Michael Krivelevich

In 2004, Frieze, Krivelevich and Martin [17] established the emergence of a giant component in random subgraphs of pseudo-random graphs. We study several typical properties of the…

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

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

Perfect Matching in Product Graphs and in their Random Subgraphs

Climbing up a random subgraph of the hypercube

Percolation through Isoperimetry

A Jump of the Saturation Number in Random Graphs?

On vertex Ramsey graphs with forbidden subgraphs

Percolation on Irregular High-dimensional Product Graphs

Heavy and Light Paths and Hamilton Cycles

Percolation on High-dimensional Product Graphs

Expansion in Supercritical Random Subgraphs of Expanders and its Consequences

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

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