Disproof of the neighborhood conjecture with implications to SAT (Q377802): Difference between revisions

In a binary tree (a rooted tree whose nodes all have either 2 or 0 children) a leaf is \(\ell\)-close to a node if the node is an ancestor distant at most \(\ell\); a \((k,d)\)-tree is a binary tree in which every leaf has depth at least \(k-1\), and there are, for every node, at most \(d\) leaves which are \((k-1)\)-close. Lemma 1.1: A \(\left(k,\left\lfloor \frac{2^{k+2}}k\right\rfloor\right)\)-tree exists for every \(k\geq1\). The author advises in her introduction that this lemma ``will be the main ingredient in proving some new results on Maker/Breaker games and SAT'' (the ``Boolean satisfiability problem''). See also the detailed abstract of the author's paper [Lect. Notes Comput. Sci. 5757, 764--775 (2009; Zbl 1256.68083)].