Теорема Бека–Фиалы

В математике теорема Бека–Фиалы является основной теоремой в теории несоответствий, выдвинутой Йожефом Беком и Тибором Фиалой. Несоответствие связано с раскраской элементов базового множества таким образом, чтобы каждое множество в определенной системе множеств было максимально сбалансированным, т. е. имело приблизительно одинаковое количество элементов каждого цвета. Теорема Бека–Фиалы касается случая, когда каждый элемент не появляется много раз во всех множествах. Теорема гарантирует, что если каждый элемент появляется не более t раз, то элементы можно раскрасить так, чтобы несоответствие не превышало 2 t − 1 . Бек и Фиала предположили, что несоответствие может быть даже ограничено .${\displaystyle O({\sqrt {t}})}$

Формально, если задана вселенная

${\displaystyle [n]=\{1,\ldots ,n\}}$

и набор подмножеств

${\displaystyle S_{1},S_{2},\ldots ,S_{m}\subseteq [n]}$

таким образом, что для каждого ,${\displaystyle я\в [н]}$

${\displaystyle \vert \{j:i\in S_{j}\}\vert \leq t,}$

тогда можно найти задание

${\displaystyle x:[n]\rightarrow \{-1,+1\}}$

такой что

${\displaystyle |x(S_{j})|\leq 2t-1,\forall j{\text{ где }}x(S_{j}):=\sum _{i\in S_{j}}x_{i}.}$

Доказательство основано на простом линейно-алгебраическом аргументе. Начните с for всех элементов и назовите все переменные активными в начале.${\displaystyle x_{i}=0}$

Рассмотрим только наборы с . Поскольку каждый элемент появляется в наборе чаще всего, таких наборов меньше, чем. Теперь примените линейные ограничения для них. Поскольку это нетривиальное линейное подпространство с меньшим количеством ограничений, чем переменных, существует ненулевое решение. Нормализуйте это решение, и по крайней мере одно из значений будет либо . Установите это значение и деактивируйте эту переменную. Теперь проигнорируйте наборы с меньшим количеством активных переменных. И повторите ту же процедуру, применив линейные ограничения, чтобы сумма активных переменных каждого оставшегося набора оставалась прежней. По тому же аргументу подсчета существует нетривиальное решение, поэтому можно брать линейные комбинации этого с исходным, пока какой-то элемент не станет . Повторяйте, пока не будут установлены все переменные.${\displaystyle \vert S_ {j} \vert >t}$${\displaystyle т}$${\displaystyle n}$${\displaystyle \sum _{i\in S_{j}}x_{i}=0}$${\displaystyle \mathbf {R} ^{n}}$${\displaystyle +1,-1}$${\displaystyle т}$${\displaystyle +1,-1}$

После того, как множество игнорируется, сумма значений его переменных равна нулю, и существует не более неустановленных переменных. Изменение в них может увеличиться до не более .${\displaystyle т}$${\displaystyle |x(S_{j})|}$${\displaystyle 2t-1}$

• Йожеф Бек и Тибор Фиала (1981). «Теоремы о целых числах». Дискретная прикладная математика . 3 (1): 1–8 . дои : 10.1016/0166-218X(81)90022-6 .

• Шазелл, Бернард (2000). Метод расхождения: случайность и сложность . Нью-Йорк: Cambridge University Press. ISBN 0-521-77093-9.