Лемма Ловаса и другие вероятностные доказательства существования

Бывают ситуации, когда существование объекта с какими-то свойствами доказать легко, но это доказательство неконструктивно (не даёт возможности предъявить такой объект). Например, можно установить, что число всех объектов определённого вида, не обладающих нужным свойством, меньше числа всех объектов этого вида. Это можно переформулировать в терминах вероятности, а также в терминах сложности описания (плохие объекты можно коротко описать, поэтому их мало). Мы рассмотрим простые примеры такого рода, а также более сложную вероятностную технику, называемую «леммой Ловаса», а также вероятностный алгоритм построения объектов, придуманный Мозером и модифицированный Тардошем, и его следствия (слова без запрещённых подслов и другие применения).