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 .
Let a bipartite graph with nonempty parts have edge density of a bipartite graph at least , and let . Some ordered tuple of distinct vertices of has a common neighbourhood of size at leastSample the tuple uniformly without replacement. A vertex belongs to its common neighbourhood with probability , where . This is at least . The function is convex, so averaging over and using Jensen's inequality proves the bound.
For fixed and , taking sufficiently large compared with makes this at least . The positive part in the formula is essential: without it, a negative base raised to an even power would assert a spurious positive common neighbourhood.
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.