AN ALGORITHMIC PROOF OF FRANKL'S UNION-CLOSED SETS CONJECTURE

Abstract. We prove the Frankl conjecture (also known as theunion-closed sets conjecture), which states that for any finite unionclosed family of sets containing at least one non-empty set, thereexists an element that belongs to at least half of the sets in thefamily. Our proof establishes a connection between union-closedfamilies and binary matrices, showing that the characteristic matrix of a union-closed family (which we call a Frankl matrix) satisfies certain structural properties. We then apply a recent result onheavy columns in binary matrices to conclude that such a matrixmust contain a heavy column, which directly implies the Franklconjecture.

Перевод пока недоступен