Source author record

Sahar Diskin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Saturation in Random Hypergraphs

Let $K^r_n$ 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 $\binom{[n]}{r}$ . We form $G^r(n,p)$ by retaining each edge of $K^r_n$ independently with probability $p$ . An $r$ -uniform hypergraph $H\subseteq G$ is $F$ -saturated if $H$ does not contain any copy of $F$ , but any missing edge of $H$ in $G$ creates a copy of $F$ . Furthermore, we say that $H$ is weakly $F$ -saturated in $G$ if $H$ does not contain any copy of $F$ , but the missing edges of $H$ in $G$ can be added back one-by-one, in some order, such that every edge creates a new copy of $F$ . The smallest number of edges in an $F$ -saturated hypergraph in $G$ is denoted by $sat(G,F)$ , and in a weakly $F$ -saturated hypergraph in $G$ by $wsat(G,F)$ . In 2017, Korándi and Sudakov initiated the study of saturation in random graphs, showing that for constant $p$ , with high probability $sat(G(n,p),K_s)=(1+o(1))n\log_{\frac{1}{1-p}}n$ , and $wsat(G(n,p),K_s)=wsat(K_n,K_s)$ . Generalising their results, in this paper, we solve the suturation problem for random hypergraphs for every $2\le r < s$ and constant $p$ .

preprint2022arXiv

Expansion in Supercritical Random Subgraphs of Expanders and its Consequences

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 giant component, most notably its expansion characteristics. We establish an asymptotic vertex expansion of connected sets in the giant by a factor of $\tilde{O}\left(ε^2\right)$ . From these expansion properties, we derive that the diameter of the giant is typically $O_ε\left(\log n\right)$ , and that the mixing time of a lazy random walk on the giant is asymptotically $O_ε\left(\log^2 n\right)$ . We also show similar asymptotic expansion properties of (not necessarily connected) linear sized subsets in the giant, and the typical existence of a large expander as a subgraph.

preprint2022arXiv

On the Performance of the Depth First Search Algorithm in Supercritical Random Graphs

We consider the performance of the Depth First Search (DFS) algorithm on the random graph $G\left(n,\frac{1+ε}{n}\right)$ , $ε>0$ a small constant. Recently, Enriquez, Faraud and Ménard [2] proved that the stack $U$ of the DFS follows a specific scaling limit, reaching the maximal height of $(1+o_ε(1))ε^2n$ . Here we provide a simple analysis for the typical length of a maximum path discovered by the DFS.

preprint2022arXiv

Supercritical Site Percolation on the Hypercube: Small Components are Small

We consider supercritical site percolation on the $d$ -dimensional hypercube $Q^d$ . We show that typically all components in the percolated hypercube, besides the giant, are of size $O(d)$ . This resolves a conjecture of Bollobás, Kohayakawa, and Łuczak from 1994.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sahar Diskin

Research overview

Is this your work?

4 publications

Saturation in Random Hypergraphs

Expansion in Supercritical Random Subgraphs of Expanders and its Consequences

On the Performance of the Depth First Search Algorithm in Supercritical Random Graphs

Supercritical Site Percolation on the Hypercube: Small Components are Small

See the researcher in context

Building this map preview