 Dependent random choice

Dependent random choice finds a large vertex set whose small subsets have large common neighbourhoods. In a bipartite graph with parts $A,B$, choose random vertices of $B$ with repetition and take their common neighbourhood $X\subseteq A$; convexity gives a lower bound for $\mathbb{E}|X|$, while counting subsets of $X$ with small common neighbourhood allows their deletion.

Dependent random choice is a concept mainly used in probability theory and stochastic processes. It refers to a selection process where the choices made are not independent of one another; rather, the outcome of one choice influences the probabilities of subsequent choices. In a typical independent random choice scenario, the probability of each outcome remains constant regardless of what has happened before. However, in dependent random choice, the selection of one item or event alters the likelihood of selecting other items or events in the future.