On the maximal minimal cube lengths in distinct DNF tautologies

By Manuel Kauers, Martina Seidl, and Doron Zeilberger

.pdf     LaTex source  

First Written: Feb. 9, 2019. This version: March 18, 2019.

[Appeared in Discrete Mathematics Letters, v.2 (2019), 47-51.]

Hamlet famously asked "To Be or Not To Be". This is a very simple example of a DNF tautology, albeit not with "distinct supports", since the supports of both "To Be" and "Not To Be" is {To Be}. On the other hand

Drink or Drive or (Not Drink and Not Drive)

Is a DNF tautology with distinct supports, since the supports are {Drink}, {Drive}, {Drink,Drive}.

In this seminal paper, an old Dr. Z and a young Dr. Z treated the question of such DNF tautologies with distinct supports, where the size of the smallest support is as large as possible. In the present article, we answer some of the questions that they left open, and treat other interesting extensions and variations.

Python Code

Here is the Python program used to generated the results in our paper.

Doron Zeilberger's List of papers

Doron Zeilberger's Home Page

Manuel Kauers' Home Page

Martina Seidl's Home Page