Let $F$ be a random k-CNF formula with $n$ variables and $m$ clauses. Let $G$ be the undirected graph built in the following manner: there is a vertex $v$ for every clause $c \in F$, and there is an edge $e = (v, u)$ if and only if the clause corresponding to $v$ has at least one variable in common with the clause corresponding to $u$.

The question is: how many variables, on average, shall I remove from $F$ before $G$ gets divided into 2 or more connected components? Is such number of variables related to $r = \frac{m}{n}$?

Here is what I mean by "removing a variable $v$ from a formula $F$": every clause $c$ in which $v$ is mentioned (no matter if positive or negative) gets shortened; if $c$ becomes empty, then it is removed from $F$.

  • 1
    $\begingroup$ $G'$ does not seem to add anything to your setup, as it is simply a forest of cliques. You seem to be asking about the average connectivity of $G$, but what is the distribution of functions? $\endgroup$ Commented Sep 21, 2010 at 9:33
  • 2
    $\begingroup$ Are the k-CNF formulas chosen uniformly at random from among the ones with m clauses and n variables? $\endgroup$ Commented Sep 21, 2010 at 10:49
  • 1
    $\begingroup$ Oops, you are right. The item 1 in my previous comment was wrong. I realized that I did not understand the problem; what do you mean by removing a variable from a CNF formula? More specifically, if you remove a variable, do the clauses containing that variable disappear, or do they still exist (with one less alternatives)? Does it depend on whether the variable is negated in the clause or not? $\endgroup$ Commented Sep 21, 2010 at 13:36
  • 1
    $\begingroup$ In my opinion you should state the definition of “removing a variable” in the question because it is far from obvious. In particular, your previous comment implies that a unit clause disappears if the only variable in it is removed; this is counter-intuitive (almost contradictory) when compared to the other case, and has to be stated explicitly if that is really what you want. (more) $\endgroup$ Commented Sep 21, 2010 at 14:03
  • 1
    $\begingroup$ (Cont’d) Also, I do not see any role played by the negation, and moreover I find the question stated in terms of CNF formula rather confusing because the definition of “removing a variable” does not seem to be any meaningful operation on CNF formulas such as assigning a value to a variable. The question seems to be about a set system (or equivalently a hypergraph). $\endgroup$ Commented Sep 21, 2010 at 14:09


Browse other questions tagged or ask your own question.