Dependent random choice finds a large vertex set whose small subsets have large common neighbourhoods. In a bipartite graph with parts , choose random vertices of with repetition and take their common neighbourhood ; convexity gives a lower bound for , while counting subsets of with small common neighbourhood allows their deletion.
In a bipartite graph with parts of sizes and density , a neighbourhood of size at least can be chosen so that at least a proportion of its ordered pairs have at least common neighbours. Choose a random vertex on the other side, use the second moment of its degree, and penalize pairs with few common neighbours. This is a simple dependent random choice tool for controlling restricted sumsets.
If a bipartite graph has vertices and maximum degree , thenA dependent random choice argument finds, in one colour, enough vertices whose every subset of at most vertices has a large common neighbourhood; a greedy embedding then places .
If a bipartite graph with parts has density at least , then averaging ordered distinct -tuples gives a common neighbourhood of size at leastIn particular this is at least when is sufficiently large compared with .
The completion form of dependent random choice starts with vertices having at least common neighbours in one colour. Reapplying common-neighbourhood sampling inside the remaining polynomial-size set either completes these vertices to a monochromatic in that colour or produces a in the other colour. It yields
Articles by others on the same topic
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.