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$.


closed as not a real question by Dave Clarke Mar 10 '11 at 17:33

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$ – András Salamon Sep 21 '10 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$ – András Salamon Sep 21 '10 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$ – Tsuyoshi Ito Sep 21 '10 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$ – Tsuyoshi Ito Sep 21 '10 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$ – Tsuyoshi Ito Sep 21 '10 at 14:09

Browse other questions tagged or ask your own question.