# Connected components of k-CNF formulas [closed]

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

• $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? Commented Sep 21, 2010 at 9:33
• Are the k-CNF formulas chosen uniformly at random from among the ones with m clauses and n variables? Commented Sep 21, 2010 at 10:49
• 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? Commented Sep 21, 2010 at 13:36
• 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) Commented Sep 21, 2010 at 14:03
• (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). Commented Sep 21, 2010 at 14:09