On CNF formulas irredundant with respect to unit clause propagation

Abstract

Abstract

Two CNF formulas are called ucp-equivalent, if they behave in the same way with respect to the unit clause propagation (ucp). A formula is called ucp-irredundant, if removing any clause leads to a formula which is not ucp-equivalent to the original one. As a consequence of known results, the ratio of the size of a ucp-irredundant formula and the size of a smallest ucp-equivalent formula is at most $n^{2}$, where $n$ is the number of the variables. We demonstrate an example of a ucp-irredundant formula for a symmetric definite Horn function which is larger than a smallest ucp-equivalent formula by a factor $\Omega(n/\ln n)$ and, hence, a general upper bound on the above ratio cannot be smaller than this.

1 Introduction

In some contexts, the strength of unit clause propagation (UCP) on the formula is important and formulas representing the same function have to be distinguished according to the behavior of UCP on them. An important example is the set of learned clauses in a SAT solver. Most of these clauses are implicates of the original formula so they do not change the represented function and they are added in order to make UCP stronger. In order to investigate formulas that appear in such a context, we need to compare the strength of UCP on different formulas. In this paper, we consider a corresponding equivalence and irredundancy. Two CNF formulas are called ucp-equivalent, if for every partial assignment $\alpha$, UCP derives the same consistent set of literals from the two formulas together with $\alpha$ or we get a contradiction in both cases. A formula is called ucp-irredundant, if removing any clause makes UCP on the formula weaker and, hence, the obtained formula is not ucp-equivalent to the original one.

UCP in a CNF formula can be precisely described by its dual-rail encoding [3, 4, 5, 6, 11, 14, 15] which represents UCP by a specific Horn formula. In particular, two formulas are ucp-equivalent if and only if their dual-rail encodings are equivalent in the usual sense to represent the same Horn function. It is a well-known result [10] that the ratio of the size of a Horn formula irredundant with respect to representing a given function and the size of a smallest equivalent formula is at most the number of the variables. Using the dual-rail encoding we can transform this result to ucp-irredundant formulas, however, since dual-rail encoding changes the number of the clauses, we get a worse bound, namely $2n^{2}$, where $n$ is the number of the variables. A slightly better bound $n^{2}$ can be obtained by a proof used in [12] to prove the same bound for propagation complete formulas since the assumption of propagation completeness is used only to guarantee ucp-equivalence. Moreover, it appears that the factor $n^{2}$ holds both for the number of clauses and for the length of the formula.

It is not clear whether a general upper bound on the ratio better than $n^{2}$ can be obtained. The main result of the paper is an example of a ucp-irredundant formula $\varphi^{\ell}$ of $n$ variables which is larger than the smallest ucp-equivalent formula $\varphi^{*}$ by a factor $\Omega(n/\ln n)$. It follows that a general upper bound on the ratio discussed above cannot be smaller than this.

The formulas used in the example represent a symmetric definite Horn function and the construction of the formula $\varphi^{\ell}$ is easy. The hard part of the proof is to derive an upper bound on the size of $\varphi^{*}$ and we show that the size of $\varphi^{*}$ is closely related to the size of a specific covering system. Namely, for $n$ and $k=n/2+O(1)$, we use a system of $(k+1)$-subsets of an $n$-set such that every $k$-set is contained in at least one member of the system. The proof is then finished using a known upper bound on the size of such a system from [7] or a different upper bound from [18, 8].

Section 3 defines ucp-equivalence and ucp-irredundancy and Section 4 formulates the results. The property of the formulas needed for the results is reformulated in Section 5 as a property of a hypergraph. The construction of the required hypergraph is described in Section 7 using an auxiliary result from Section 6. The proofs of the results are summarized in Section 8. Conclusion and questions for further research are formulated in Section 9.

2 Preliminaries

2.1 CNF formulas

A literal is a variable or its negation, a clause is a disjunction of literals on different variables, and a CNF formula is a conjunction of clauses. Since we consider only CNF formulas, we call them formulas for simplicity.

A formula is considered as a set of clauses and a clause is considered as a set of literals. In particular, we use set operations on formulas and clauses. The size of a formula is the number of its clauses. A clause $C$ is an implicate of a formula $\varphi$, if $\varphi$ implies $C$. A clause $C$ is a prime implicate of a formula $\varphi$, if it is an implicate of $\varphi$ and no proper subset of $C$ is an implicate of $\varphi$. If $A$ is a set of variables, let $\mathrm{neg}(A)=\{\neg x\mid x\in A\}$.

A formula is a Horn formula, if every clause contains at most one positive literal and a formula is a definite Horn formula, if every clause contains exactly one positive literal.

A partial assignment of the variables is a partial map from the variables to the set $\{0,1\}$ understood as a conjunction of identities of the form $x=a$, where $x$ is a variable and $a\in\{0,1\}$. It is usual to represent a partial assignment by a conjunction of the literals equivalent to these identities. For example, the conjunction of identities $x_{1}=1\wedge x_{2}=0$ is equivalent to the conjunction of literals $x_{1}\wedge\neg x_{2}$.

Assume a formula $\varphi$, a clause $C\in\varphi$, and a literal $l\in C$. If $\alpha$ is a partial assignment falsifying all literals in $C\setminus\{l\}$, then every satisfying assignment of $\varphi$ extending $\alpha$ satisfies $l$ and, hence, $l$ is a consequence of $\varphi\wedge\alpha$. Unit propagation in a formula $\varphi$ from a partial assignment $\alpha$ is the process of extending $\alpha$ by assignments obtained as consequences of $\varphi\wedge\alpha$ of this simple type. The process terminates if either no further literal can be derived in this way or all the literals in some of the clauses of $\varphi$ are falsified. In the latter case, we say that a contradiction is derived and this means that the initial partial assignment cannot be extended to a satisfying assignment of $\varphi$. The opposite implication is not true. For example, unit propagation in the formula $(x_{1}\vee x_{2})\wedge(x_{1}\vee\neg x_{2})\wedge(\neg x_{1}\vee x_{2})\wedge(\neg x_{1}\vee\neg x_{2})$ from the empty assignment does not derive any literal and, hence, does not derive a contradiction, however, the formula is unsatisfiable.

2.2 Covering and Turán numbers

We use known bounds on covering numbers $C(n,r,k)$ [9] and the closely related Turán numbers $T(n,\ell,t)$ [18, 8] defined using different conventions. Note that Turán’s theorem implies a precise value of $T(n,\ell,2)$, if we minimize the number of edges to be removed from a complete graph on $n$ vertices in order to eliminate all complete subgraphs on $\ell$ vertices.

Definition 2.1.

For integers $n>r>k>0$, let the covering number $C(n,r,k)$ be the smallest size of a system of $r$-subsets of an $n$-set such that every $k$-subset is contained in at least one set in the system.

Definition 2.2.

For integers $n>\ell>t>0$, let the Turán number $T(n,\ell,t)$ be the smallest size of a system of $t$-subsets of an $n$-set such that every $\ell$-subset contains at least one set in the system.

By taking complements of the sets, we obtain $C(n,r,k)=T(n,n-k,n-r)$. Let us recall several known results on covering numbers in the case $r=k+1$ which we use. Clearly,

$$C(n,k+1,k)\geq\frac{1}{k+1}{n\choose k}\;.$$ (1)

If $k$ is fixed and $n\to\infty$, then by [16], we have

$$C(n,k+1,k)=(1+o(1))\frac{1}{k+1}{n\choose k}\;.$$

We are mainly interested in cases when $k=n/2+O(1)$ for which only less precise bounds are known. Let $\mu(n,k)$ be such that

$$C(n,k+1,k)=\frac{1}{k+1}{n\choose k}\mu(n,k)$$ (2)

and, equivalently,

$$T(n,t+1,t)=\frac{1}{t+1}{n\choose t}\mu(n,n-t-1)\;.$$ (3)

By (1), we have $1\leq\mu(n,k)$. For an upper bound on $\mu(n,k)$, let us recall the following.

Theorem 2.3 (a special case of Theorem 13.4 from [7]).

For every $n>k\geq 2$, we have

$$C(n,k+1,k)\leq\frac{1}{k+1}{n\choose k}(1+\ln(k+1))$$ (4)

This implies

$$1\leq\mu(n,k)\leq 1+\ln(k+1)$$ (5)

for every $n>k\geq 2$. An incomparable upper bound on $\mu(n,k)$ follows from the bound [18] on Turán numbers improving [8] by a factor of $2$. By this bound, we have

$$T(n,t+1,t)\leq\frac{(1+o(1))\ln t}{2t}{n\choose t}$$ (6)

for $n\to\infty$ and $t\to\infty$. Combining (6) with (3), substituting $k=n-t-1$ and assuming $n-k\to\infty$, we obtain

$$\mu(n,k)\leq\frac{1+o(1)}{2}\ln(n-k-1)\;.$$ (7)

Bounds (5) and (7) are complementary in the sense that (5) is better, if $k$ is small, while (7) is better, if $k$ is close to $n$. In Section 8 we need also the following.

Lemma 2.4.

For every $n>k>1$, we have

$$\mu(n-1,k-1) \leq \mu(n,k)$$ (8)

$$\frac{n-k+1}{n+1}\mu(n,k) \leq \mu(n+1,k)$$ (9)

Proof.

By [17, 9], we have

$$\frac{n}{k+1}C(n-1,k,k-1)\leq C(n,k+1,k)$$

implying (8). Assume a system of $(k+1)$-subsets of a set $X$ of $n+1$ points of size $C(n+1,k+1,k)$ and covering all $k$-subsets. For any $x\in X$, one can create a system of $(k+1)$-subsets of $X\setminus\{x\}$ covering all $k$-subsets by replacing each ocurrence of $x$ in a $(k+1)$-tuple in the system by any element of $X\setminus\{x\}$ not contained in the $(k+1)$-tuple. Hence, we have

$$C(n,k+1,k)\leq C(n+1,k+1,k)$$

implying (9). ∎

3 Ucp-equivalence and ucp-irredundancy

A formula $\varphi$ is called propagation complete (PC), if for every partial assignment $\alpha$ of the variables, UCP from $\varphi\wedge\alpha$ derives a contradiction, if $\varphi\wedge\alpha$ is not consistent, and all implied literals otherwise. A PC formula is called irredundant PC formula, if removing any clause leads to a formula which is not a PC formula equivalent to the original one.

By the result [12], the ratio of the size of an arbitrary irredundant PC formula and a smallest equivalent PC formula is at most $n^{2}$, where $n$ is the number of the variables. The assumption that the two formulas are PC is used only to obtain that they behave in the same way with respect to UCP, since UCP on both of them is controlled by the represented function. This suggests to generalize the result using ucp-equivalence defined below. In particular, a PC formula is a formula ucp-equivalent to the set of all its (prime) implicates.

Definition 3.1.

Formulas $\varphi_{1}$ and $\varphi_{2}$ are ucp-equivalent if for every partial assignment $\alpha$, unit clause propagation derives either the same partial assignment from $\varphi_{1}\wedge\alpha$ and from $\varphi_{2}\wedge\alpha$ or we get a contradiction in both cases.

In [5] a minimal PC formula is defined using the notion of an absorbed clause. A clause $C$ is absorbed by a formula $\varphi$, if for every $l\in C$, UCP from $\varphi\wedge\mathrm{neg}(C\setminus\{l\})$ derives $l$ or a contradiction. A formula is called minimal PC formula in [5] if none of its clauses is absorbed by the remaining ones. This does not guarantee that no smaller equivalent PC formula exists, however, the formula is irredundant with respect to the behavior of UCP. We use a straightforward generalization of this type of irredundancy obtained by removing the requirement that the formula is PC.

Definition 3.2.

A formula $\varphi$ is ucp-irredundant if any of the following equivalent conditions is satisfied:

• None of the clauses $C\in\varphi$ is absorbed by $\varphi\setminus\{C\}$.

• For every $C\in\varphi$, the formulas $\varphi$ and $\varphi\setminus\{C\}$ are not ucp-equivalent.

The following is a generalization of a similar upper bound for irredundant PC formulas from [12].

Proposition 3.3.

If $\varphi$ is a ucp-irredundant formula on $n$ variables and $\varphi^{*}$ is ucp-equivalent to $\varphi$, then

$$|\varphi|\leq n^{2}|\varphi^{*}|$$ (10)

and

$$\|\varphi\|\leq n^{2}\|\varphi^{*}\|$$ (11)

Proof.

Every clause of $\varphi^{*}$ is absorbed by $\varphi$. Let $\varphi^{\prime}$ be the set of clauses in $\varphi$ needed for this for all clauses of $\varphi^{*}$. For each pair $l\in C\in\varphi^{*}$, we need at most $n$ clauses of $\varphi$ to derive $l$ or a contradiction from $\varphi\wedge\mathrm{neg}(C\setminus\{l\})$. This implies $|\varphi^{\prime}|\leq n\|\varphi^{*}\|$. Since every clause of $\varphi$ is absorbed by $\varphi^{*}$, every clause of $\varphi^{*}$ is absorbed by $\varphi^{\prime}$ and $\varphi^{\prime}\subseteq\varphi$, the formula $\varphi^{\prime}$ is ucp-equivalent to $\varphi$. Since $\varphi$ is ucp-irredundant, we have $|\varphi|\leq n\|\varphi^{*}\|$ implying

$$|\varphi|\leq n\|\varphi^{*}\|\leq n^{2}|\varphi^{*}|$$

and

$$\|\varphi\|\leq n|\varphi|\leq n^{2}\|\varphi^{*}\|$$

as required. ∎

4 The results

The main result is the following separation between the size of a ucp-irredundant formula and a smallest ucp-equivalent formula.

Theorem 4.1.

For every $n$ and $k=n/2+O(1)$, there is a ucp-irredundant formula $\varphi^{\ell}$ of $n$ variables and of size

$$|\varphi^{\ell}|=(k+1){n-1\choose k}=\Theta(n){n\choose k}$$

and such that a smallest ucp-equivalent formula $\varphi^{*}$ has size

$$|\varphi^{*}|\leq 6(k+1)C(n,k+1,k)=O(\ln n){n\choose k}$$

In particular, $|\varphi^{\ell}|=\Omega(n/\ln n)|\varphi^{*}|$.

For a proof, we investigate the size of ucp-irredundant formulas ucp-equivalent to the following definite Horn formula $\Psi_{n,k}$.

Definition 4.2.

For any integers $n$, $k$, such that $1\leq k\leq n-1$, let $\Psi_{n,k}$ be the CNF formula consisting of all clauses on variables $X=\{x_{1},\ldots,x_{n}\}$ containing $k$ negative literals and one positive literal.

Clearly, $|\Psi_{n,k}|=(n-k){n\choose k}$. A boolean function is called symmetric, if it is invariant under any permutation of its variables.

Lemma 4.3.

Formula $\Psi_{n,k}$ represents the symmetric boolean function $f_{n,k}$ of $n$ variables defined by

$$f_{n,k}(x_{1},\ldots,x_{n})=1\Leftrightarrow\left(\sum_{i=1}^{n}x_{i}<k\right)\vee\left(\sum_{i=1}^{n}x_{i}=n\right)$$

Proof.

By case inspection concerning the number of variables with value $1$ and $0$ in a given assignment. ∎

In particular, we prove the following upper and lower bound on the size of a smallest formula ucp-equivalent to $\Psi_{n,k}$.

Theorem 4.4.

The minimum size (number of clauses) of a formula ucp-equivalent to $\Psi_{n,k}$ is at least

$$n\,C(n-1,k,k-1)={n\choose k}\mu(n-1,k-1)\geq{n\choose k}$$

and if $k=n/2+O(1)$ then it is at most

$$6(k+1)C(n,k+1,k)=6\,{n\choose k}\mu(n,k)=O(\ln n){n\choose k}\;.$$

The proof of Theorem 4.1 depends on Theorem 4.4 and the proof of both of them is summarized in Section 8 using constructions presented in this and the following sections. The lower and upper bound in Theorem 4.4 are proven to differ at most by a factor $O(\ln n)$, however, it is plausible to assume that they are in fact closer, see the discussion of this in Section 8.

The lower bound in Theorem 4.4 is proven in Section 5. For the proof of the remaining statements, we construct for infinitely many pairs $(n,k)$ ucp-irredundant formulas $\varphi^{\ell}$ (in Section 5) and $\varphi^{*}$ (in Section 8) ucp-equivalent to $\Psi_{n,k}$, such that $\varphi^{\ell}$ is as large as possible and $\varphi^{*}$ is as small as possible. We obtain $\varphi^{*}$ which meets the upper bound in Theorem 4.4 and the two formulas together satisfy Theorem 4.1. Each of the formulas $\varphi^{\ell}$ and $\varphi^{*}$ will be constructed as a hypergraph formula $\theta(H)$ where $H$ is a suitable hypergraph, see also [1, 2].

Definition 4.5.

For every $(k+1)$-uniform hypergraph $H$ whose vertices are the variables $X$, the hypergraph formula $\theta(H)$ consists of the clauses $\mathrm{neg}(e\setminus\{x\})\cup\{x\}$ for all hyperedges $e\in H$ and all variables $x\in e$.

Clearly, for every $H$, $\theta(H)\subseteq\Psi_{n,k}$ and $|\theta(H)|=(k+1)|H|$. Considering hypergraph formulas for the upper bound in Theorem 4.4 is restrictive, however, this does not seem to be significant. The lower bound is valid for an arbitrary subset of $\Psi_{n,k}$ and the gap between the lower bound and the upper bound obtained by hypergraph formulas is relatively small.

5 A combinatorial characterization

For simplicity, when considering formulas ucp-equivalent to $\Psi_{n,k}$, we consider only prime formulas. Since the formula $\Psi_{n,k}$ is equal to the set of its prime implicates, these formulas are subsets of $\Psi_{n,k}$. We present two combinatorial characterizations of the subsets of $\Psi_{n,k}$ which are ucp-equivalent to $\Psi_{n,k}$. The first of them is valid for an arbitrary subset of $\Psi_{n,k}$ and is used for a lower bound on the size of prime formulas ucp-equivalent to $\Psi_{n,k}$. The other characterization is valid for subsets of $\Psi_{n,k}$ in the form of a hypergraph formula $\theta(H)$ defined above and is used later for a corresponding upper bound.

Every clause of $\Psi_{n,k}$ contains $k$ negative literals. It follows that UCP from $\Psi_{n,k}$ and a partial assignment setting less than $k-1$ variables to $1$ derives no additional literal. The same is true for every subset of $\Psi_{n,k}$ and, hence, for a characterization of subsets of $\Psi_{n,k}$ which are ucp-equivalent to $\Psi_{n,k}$, it is sufficient to consider partial assignments setting at least $k-1$ variables to $1$.

Definition 5.1.

Assume $\varphi\subseteq\Psi_{n,k}$ and a $(k-1)$-set $A\subseteq X$. Let $G^{d}(\varphi,A)$ be the directed graph on $X\setminus A$ defined as

$$G^{d}(\varphi,A)=\{(x_{i},x_{j})\mid\mathrm{neg}(A)\cup\{\neg x_{i},x_{j}\}\in\varphi\}\;.$$

This graph represents unit propagation in $\varphi$ for partial assignments setting all variables in $A$ to $1$ in the following sense.

Lemma 5.2.

Let $\varphi$ and $A$ be as in Definition 5.1. Assume a partial assignment $\alpha$ setting all variables in $A$ to $1$ and setting a variable $x_{i}\in X\setminus A$ to $b\in\{0,1\}$. Let $\beta$ be the partial assignment obtained by extending $\alpha$ by unit propagation in $\varphi$.

• If $b=0$, then $\beta$ extends $\alpha$ precisely by setting to $0$ the variables $x_{j}$ such that $G^{d}(\varphi,A)$ contains a path from $x_{j}$ to $x_{i}$.

• If $b=1$, then $\beta$ extends $\alpha$ at least by setting to $1$ the variables $x_{j}$ such that $G^{d}(\varphi,A)$ contains a path from $x_{i}$ to $x_{j}$.

Proof.

Consider setting all variables in $A$ to $1$. With this partial assignment, the clauses containing a positive literal on a variable from $A$ become satisfied and, hence, can be removed. Since $|A|=k-1$, the remaining clauses form a definite Horn formula without unit clauses. In such a formula, setting some of the variables in $X\setminus A$ to $0$ can derive a value of a new variable by unit propagation only using a clause containing one negative literal. Since the derived value of the variable in this literal is $0$, the same is true if the propagation is iterated. If $C\in\varphi$, then setting the variables in $A$ to $1$ in $C$ produces a clause with one negative literal only if $C=\mathrm{neg}(A)\cup\{\neg x_{i},x_{j}\}$ for some $i,j$ and the resulting clause is $\{\neg x_{i},x_{j}\}$. Hence, the clauses relevant for propagating assignments of variables in $X\setminus A$ to $0$ after setting all variables in $A$ to $1$ form the 2-CNF formula

$$\varphi_{A}=\{C\setminus\mathrm{neg}(A)\mid\mathrm{neg}(A)\subseteq C\in\varphi\}\;.$$ (12)

The clause $\{\neg x_{i},x_{j}\}$ is the same as $\neg x_{i}\vee x_{j}$ and is equivalent to implication $x_{i}\to x_{j}$. Unit propagation using this implication derives $x_{i}=0$, if $x_{j}=0$ and the graph $G^{d}(\varphi,A)$ corresponds precisely to implications in $\varphi_{A}$. Setting all variables in $X\setminus A$ to $0$ is a satisfying assignment of $\varphi_{A}$, so propagating zeros cannot lead to a contradiction. This proves the statement concerning $b=0$.

The statement concerning $b=1$ is clear, since $\varphi_{A}$ is a subset of the formula obtained from $\varphi$ by setting variables in $A$ to $1$ and the clauses of $\varphi_{A}$ allow propagation of values $1$ along all directed paths in $G^{d}(\varphi,A)$. ∎

Lemma 5.3.

A formula $\varphi\subseteq\Psi_{n,k}$ is ucp-equivalent to $\Psi_{n,k}$ if and only if for every $(k-1)$-set $A\subseteq X$ the graph $G^{d}(\varphi,A)$ is a strongly connected graph on $X\setminus A$.

Proof.

Let $A$ be any $(k-1)$-subset of $X$ and let $\Psi_{n,k,A}$ be obtained from $\Psi_{n,k}$ by setting the variables in $A$ to $1$. Formula $\Psi_{n,k,A}$ contains the clauses $\neg x_{i}\vee x_{j}$ for every $x_{i},x_{j}\in X\setminus A$. It follows that unit propagation in $\Psi_{n,k,A}$ from a partial assignment setting a variable $x_{j}\in X\setminus A$ to $0$ derives the value $0$ for all the remaining variables $x_{i}\in X\setminus A$. The resulting assignment is a satisfying assignment of $\Psi_{n,k,A}$, so contradiction is not derived.

Assume, $\varphi\subseteq\Psi_{n,k}$ is ucp-equivalent to $\Psi_{n,k}$. Since unit propagation in $\Psi_{n,k,A}$ derives value $0$ for all variables in $X\setminus A$ if one of them is set to $0$, the same should be true for the formula obtained from $\varphi$ by setting the variables in $A$ to $1$. By Lemma 5.2 with $b=0$, this implies that $G^{d}(\varphi,A)$ contains a path in both directions between any two variables in $X\setminus A$, so it is strongly connected.

Assume that $G^{d}(\varphi,A)$ is strongly connected. Let $C\in\Psi_{n,k}\setminus\varphi$ and let us prove that any unit propagation step using the clause $C$ can be replaced by unit propagation in $\varphi$ deriving the same literal from the same assumptions. Let $l\in C$ and consider a partial assignment $\alpha$ of the variables falsifying all the literals in $C\setminus\{l\}$. We have to show that unit propagation in $\varphi$ derives $l$ from $\alpha$.

If $l$ is positive, let $g\in C\setminus\{l\}$ be arbitrary. If $l$ is negative, let $g$ be the positive literal contained in $C$. For a suitable $(k-1)$-set of variables $A$, we have $C=\mathrm{neg}(A)\cup\{g,l\}$, $g$ and $l$ have the opposite sign, and $\alpha$ falsifies all the literals in $\mathrm{neg}(A)$ and $g$. Assume that the variable in $g$ is $x_{i}$ and the variable in $l$ is $x_{j}$. Hence, we have either $g=x_{i}$ and $l=\neg x_{j}$ or $g=\neg x_{i}$ and $l=x_{j}$. By assumption, $G^{d}(\varphi,A)$ contains paths between $x_{i}$ and $x_{j}$ in both directions. If $g=x_{i}$, then falsifiying $g$ means setting $x_{i}$ to $0$ and Lemma 5.2 with $b=0$ implies that unit propagation derives $x_{j}=0$ and, hence, the literal $l$. If $g=\neg x_{i}$, then falsifiying $g$ means setting $x_{i}$ to $1$ and Lemma 5.2 with $b=1$ implies that unit propagation derives $x_{j}=1$ and, hence, the literal $l$.

We obtained that unit propagation in $\varphi$ from partial assignment $\alpha$ derives $l$. Since this is true for every clause $C\in\Psi_{n,k}\setminus\varphi$ and for every $l\in C$, $\varphi$ is ucp-equivalent to $\Psi_{n,k}$. ∎

Proposition 5.4.

The size (number of clauses) of a formula ucp-equivalent to $\Psi_{n,k}$ is at least $n\,C(n-1,k,k-1)$.

Proof.

Let $\varphi^{*}$ be a smallest formula ucp-equivalent to $\Psi_{n,k}$. Without loss of generality, we can assume that $\varphi^{*}$ consists only of prime implicates and, hence, is a subset of $\Psi_{n,k}$. For every variable $x\in X$, let

$$\mathcal{S}_{x}=\{B\mid\mathrm{neg}(B)\vee x\in\varphi^{*}\}\;.$$

For every $B\in\mathcal{S}_{x}$, we have $B\subseteq X\setminus\{x\}$ and $|B|=k$. Let $x\in X$ and let $A$ be an arbitrary $(k-1)$-subset of $X\setminus\{x\}$. By Lemma 5.3, vertex $x$ has non-zero in-degree in $G^{d}(\varphi^{*},A)$ and, hence, there is a set $B\in\mathcal{S}_{x}$ such that $A\subseteq B$. It follows that $\mathcal{S}_{x}$ is a system of $k$-subsets of an $(n-1)$-set covering all $(k-1)$-subsets. Hence, $|\mathcal{S}_{x}|\geq C(n-1,k,k-1)$ and, since $|\varphi^{*}|=\sum_{x\in X}|\mathcal{S}_{x}|$, the statement follows. ∎

For analysis of the formulas $\theta(H)$ we use the following notion.

Definition 5.5.

We say that a $(k+1)$-uniform hypergraph $H$ on the set of vertices $X$ has connected restrictions, if for every $(k-1)$-set $A\subseteq X$, the graph

$$G(H,A)=\{e\setminus A\mid A\subseteq e\in H\}$$ (13)

is a connected graph on the set $X\setminus A$.

Proposition 5.6.

If $H$ is $(k+1)$-uniform hypergraph on $X$, then $\theta(H)$ is ucp-equivalent to $\Psi_{n,k}$ if and only if $H$ has connected restrictions.

Proof.

Since $\theta(H)$ is a subset of $\Psi_{n,k}$, we can use the characterization of formulas ucp-equivalent to $\Psi_{n,k}$ from Lemma 5.3.

Let $A$ be an arbitrary $(k-1)$-subset of $X$. If $G^{d}(\theta(H),A)$ contains the directed edge $(x_{i},x_{j})$, then it also contains the directed edge $(x_{j},x_{i})$. Moreover, these two edges are contained in $G^{d}(\theta(H),A)$ if and only if $G(H,A)$ contains the undirected edge $\{x_{i},x_{j}\}$. Hence, $G^{d}(\theta(H),A)$ is strongly connected if and only if $G(H,A)$ is connected. Since this is satisfied for arbitrary $(k-1)$-subset $A\subseteq X$, $\theta(H)$ satisfies the condition from Lemma 5.3 if and only if $H$ has connected restrictions. ∎

Note that $\Psi_{n,k}=\theta(H_{0})$, where $H_{0}$ is the complete $(k+1)$-uniform hypergraph. The ucp-irredundant formula $\varphi^{\ell}$ can be obtained as follows.

Definition 5.7.

Let $H_{1}$ consist of all $(k+1)$-subsets of $X$ containing the variable $x_{1}$ and let $\varphi^{\ell}=\theta(H_{1})$.

In particular, $H_{1}$ has connected restrictions, since for every $(k-1)$-set $A$ not containing $x_{1}$, the graph $G(H_{1},A)$ is a star on $X\setminus A$ whose central vertex is $x_{1}$. If $x_{1}\in A$, then $G(H_{1},A)$ is a complete graph on $X\setminus A$.

Proposition 5.8.

Formula $\varphi^{\ell}$ is ucp-irredundant and ucp-equivalent to $\Psi_{n,k}$.

Proof.

As mentioned above, $H_{1}$ has connected restrictions. It follows that $\varphi^{\ell}$ is ucp-equivalent to $\Psi_{n,k}$ by Proposition 5.6. Let us prove that it is ucp-irredundant. For this purpose, let $C\in\varphi^{\ell}$ be arbitrary and let us prove that $\varphi^{\ell}\setminus\{C\}$ is not ucp-equivalent to $\Psi_{n,k}$. Let $V$ be the set of variables used in $C$ except of $x_{1}$, so we have $|V|=k$. Let $\alpha$ be the partial assignment of the variables in $V$ such that all literals on variables from $V$ in $C$ are falsified. The clause $C$ together with $\alpha$ derives a value of $x_{1}$ which makes the literal on $x_{1}$ in $C$ satisfied. Since $C$ is an implicate of $\Psi_{n,k}$, every formula ucp-equivalent to $\Psi_{n,k}$ should derive the same value of $x_{1}$ as $C$. The proof will be finished by proving that $\varphi^{\ell}\setminus\{C\}$ does not satisfy this.

Depending on whether $C$ contains the literal $x_{1}$ or $\neg x_{1}$, the partial assignment $\alpha$ assigns all variables in $V$ the value $1$ or all variables in $V$ are assigned the value $1$ except of one which is assigned $0$. In both cases, the following is true. Every clause $D$ in $\varphi^{\ell}\setminus\{C\}$ on the same set of variables as $C$ is satisfied by $\alpha$, since two of the variables in $C$ have different sign in $C$ and $D$. At least one of them is not $x_{1}$ and the literal with this variable is satisfied in $D$. Every clause in $\varphi^{\ell}\setminus\{C\}$ on a set of variables different from the set of variables of $C$ contains at least two variables not assigned by $\alpha$, namely $x_{1}$ and some variable not in $V\cup\{x_{1}\}$ and, hence, cannot be used for unit propagation. It follows that unit propagation in $\varphi^{\ell}\setminus\{C\}$ from the assignment $\alpha$ does not derive a value of any new variable, in particular, a value of $x_{1}$. ∎

Construction of a hypergraph $H$ such that the size of $\theta(H)$ is a good upper bound on the size of $\varphi^{*}$ is more complicated and we use results proven in the next two sections for this purpose.

6 Random permutations of a graph or hypergraph

The purpose of this section is to prove that a union of independent permutations of several graphs without isolated vertices is connected with high probability. This is an auxiliary result used in the next section to prove that union of several independent random permutations of a $(k+1)$-uniform hypergraph which covers all $k$-subsets is a hypergraph with connected restrictions with high probability.

Definition 6.1.

Let $H$ be a hypergraph on a set of vertices $V$. Consider a permutation $\pi:V\to V$. We denote by $\pi(H)$ the hypergraph on the set of vertices $V$ such that for every set $e\subseteq V$, $\pi(e)$ is a hyperedge of $\pi(H)$ is and only if $e$ is a hyperedge of $H$.

Intuitively, hypergraph $\pi(H)$ is obtained by moving each vertex $u$ of $H$ to $\pi(u)$ and moving the edges correspondingly. By a random permutation of $H$, we mean $\pi(H)$, where $\pi$ is chosen at random from the uniform distribution on permutations of $V$.

The following lemma is an anticoncentration inequality for the sum of independent variables $X_{i}$ such that the distribution of $X_{i}$ is uniform on $\{0,a_{i}\}$ where $a_{i}\geq 2$ are integers. For technical reasons, it is formulated using counts instead of probabilities.

Lemma 6.2 ([19]).

Assume integers $a_{i}\geq 2$ for $i=1,\ldots,r$ and let $m=\sum_{i=1}^{r}a_{i}$. Then for every $2\leq d\leq m/2$, the number of sets $I\subseteq\{1,\ldots,r\}$, such that

$$\sum_{i\in I}a_{i}=d$$ (14)

is at most

$${\lfloor m/2\rfloor\choose\lfloor d/2\rfloor}\;.$$

Proof.

The sets $I$ satisfying (14) are pairwise incomparable and have size at most $\lfloor d/2\rfloor$. Let $c_{j}$ for $j=1,\ldots,\lfloor d/2\rfloor$ be the number of these sets of size $j$. By LYM inequality [13], we have

$$\sum_{j=1}^{\lfloor d/2\rfloor}\frac{c_{j}}{{r\choose j}}\leq 1\;.$$

Since $r\leq\lfloor m/2\rfloor$, we have also

$$\sum_{j=1}^{\lfloor d/2\rfloor}\frac{c_{j}}{{\lfloor m/2\rfloor\choose j}}\leq 1$$

and, since $\lfloor d/2\rfloor\leq\lfloor m/2\rfloor/2$, this implies that the number of sets $I$ satisfying (14) is at most

$$\sum_{j=1}^{\lfloor d/2\rfloor}c_{j}\leq{\lfloor m/2\rfloor\choose\lfloor d/2\rfloor}$$

as required. ∎

Let $G=(V,E)$ be an undirected graph. For a permutation $\pi:V\to V$, we define $\pi(G)$ in the same way as for a hypergraph. Namely, for every pair of distinct vertices $u,v\in V$, $\{\pi(u),\pi(v)\}$ is an edge of $\pi(G)$ if and only if $\{u,v\}$ is an edge of $G$.

Lemma 6.3.

Assume a set $Y$ of size $m$ and let $G$ be a graph on $Y$ with no isolated vertices. Let $A\subseteq Y$, and let $2\leq d=|A|\leq m/2$. The probability that a random permutation of $G$ has no edge connecting $A$ and $Y\setminus A$ is at most

$${\lfloor m/2\rfloor\choose\lfloor d/2\rfloor}{m\choose d}^{-1}$$

Proof.

Consider a random permutation $\pi$ of the vertices of $G$. Graph $\pi(G)$ has no edge between $A$ and $Y\setminus A$ if and only if the preimage $\pi^{-1}(A)$ is a union of connected components of $G$. The preimages $\pi^{-1}(A)$ are uniformly distributed over subsets of $Y$ of size $d$. The number of subsets of $Y$ of size $d$ that are a union of connected components in $G$ is equal to the number of solutions of the equation (14) where $r$ is the number of connected components of $G$ and $a_{i}$ are their sizes. Since $G$ has no isolated vertices, we have $a_{i}\geq 2$ for $i=1,\ldots,r$ and, hence, the lemma follows from Lemma 6.2. ∎

Proposition 6.4.

Let $G_{1},\ldots,G_{s}$, $s\geq 3$, be graphs on the same set of $m$ vertices each of which has no isolated vertices. If $s$ is fixed and $m$ tends to infinity, then the probability that the union of independent random permutations of $G_{1},\ldots,G_{s}$ is not a connected graph is at most $O(m^{2-s})$.

Proof.

Let $Y$ be the common set of vertices of the graphs. The probability of the event that the union of independent permutations of $G_{1},\ldots,G_{s}$ is not a connected graph is at most the sum of the probabilities over subsets $A\subseteq Y$ of size between $2$ and $m/2$ of the event that the union contains no edge between $A$ and $Y\setminus A$. Using $d=|A|$ as a summation index and using Lemma 6.3, this is at most

$$\sum_{d=2}^{\lfloor m/2\rfloor}p_{d}$$

where

$$p_{d}={\lfloor m/2\rfloor\choose\lfloor d/2\rfloor}^{s}{m\choose d}^{1-s}\;.$$ (15)

For a few smallest values of $d$, the following simple estimate is sufficient. If $d$ and $s$ are fixed and $m\to\infty$, we have

$$p_{d}=O\left(m^{d(1-s/2)}\right)\;.$$ (16)

For larger values of $d$, we estimate $p_{d}$ using more precise bounds on binomial coefficients. Denote

$$b(t,d)=\left(\frac{t}{d}\right)^{d}\left(\frac{t}{t-d}\right)^{t-d}=\mathrm{e}^{t\mathrm{H}(d/t)}$$

where $\mathrm{H}(x)=-x\ln x-(1-x)\ln(1-x)$ is the entropy function. Since $\mathrm{H}(x)$ is increasing for $0\leq x\leq 1/2$, $b(t,d)$ is increasing in $d$ if $t$ is fixed and $1\leq d\leq t/2$. Since $\mathrm{H}(x)$ is strictly concave, $\mathrm{H}(x)/x$ is decreasing for $0<x\leq 1$ and, hence, $b(t,d)$ is increasing in $t$ if $d$ is fixed. By a well-known upper bound on binomial coefficients and using $d\leq\lfloor m/2\rfloor$, we get

$${\lfloor m/2\rfloor\choose\lfloor d/2\rfloor}\leq b(\lfloor m/2\rfloor,\lfloor d/2\rfloor)\leq b(m/2,d/2)=b(m,d)^{1/2}\;.$$

By a well-known lower bound on binomial coefficients, we have

$$\frac{1}{m+1}b(m,d)\leq{m\choose d}\;.$$

Using these bounds and (15), we obtain

$$p_{d}\leq(m+1)^{s-1}b(m,d)^{1-s/2}\;.$$ (17)

Choose a fixed integer $d_{0}\geq 4(s-1)/(s-2)$. By (16) we have

$$\sum_{d=2}^{d_{0}-1}p_{d}=O(m^{2-s})\;.$$ (18)

If $d_{0}\leq d\leq m/2$, then $b(m,d)\geq b(m,d_{0})\geq(m/d_{0})^{d_{0}}$ and by (17)

$$p_{d}\leq(m+1)^{s-1}(m/d_{0})^{d_{0}(1-s/2)}=O(m^{1-s})\;.$$

Together with (18), we obtain

$$\sum_{d=2}^{\lfloor m/2\rfloor}p_{d}=O(m^{2-s})$$ (19)

and the proof is finished. ∎

7 Size of a hypergraph with connected restrictions

In this section, we prove an upper bound on the minimum size of a hypergraph with connected restrictions using covering numbers.

Proposition 7.1.

For every large enough $n$ and $k=n/2+O(1)$, there is a $(k+1)$-uniform hypergraph on $n$ vertices of size at most $6\,C(n,k+1,k)$ with connected restrictions.

Proof.

Let $|X|=n$ and let $H$ be a $(k+1)$-uniform hypergraph of size $C(n,k+1,k)$ covering all $k$-subsets of $X$. Let $s=5$ and consider independent random permutations $\pi_{1},\ldots,\pi_{s}$ of $X$ chosen from the uniform distribution and let $H^{*}=\pi_{1}(H)\cup\ldots\cup\pi_{s}(H)$.

If $A$ is a $(k-1)$-subset of $X$ and $\pi$ is a permutation of $X$, then the graph $G(\pi(H),A)$ has no isolated vertices, however, for different permutations $\pi$, the graphs $G(\pi(H),A)$ are not, in general, permutations of the same graph on $X\setminus A$. In order to overcome this, we partition the probability space of all $s$-tuples of permutations of $X$ by a set of mutually exclusive conditions such that the conditional distribution of the $s$-tuple of graphs $G(\pi_{i}(H),A)$, $i=1,\ldots,s$ under any of these conditions satisfies the assumption of Proposition 6.4. Namely, for an arbitrary $s$-tuple $(A_{1}^{\prime},\ldots,A_{s}^{\prime})$ of $(k-1)$-subsets of $X$ consider the condition $\pi_{i}(A_{i}^{\prime})=A$ for every $i=1,\ldots,s$. Clearly, these conditions have the same probability for all $s$-tuples of $(k-1)$-subsets $A_{i}^{\prime}$ and represent a partition of the probability space.

Fix an arbitrary $s$-tuple $(A_{1}^{\prime},\ldots,A_{s}^{\prime})$ and consider the corresponding conditional distribution. For a fixed $i$ and all permutations $\pi_{i}$ satisfying $\pi_{i}(A_{i}^{\prime})=A$, the graphs $G(\pi_{i}(H),A)$ are isomorphic. Choose any of them as $G_{i}$. The distribution of $G(\pi_{i}(H),A)$ is the same as random permutations of $G_{i}$. Moreover, these permutations are independent for $i=1,\ldots,s$. Hence, we can use Proposition 6.4 to obtain that $G(H^{*},A)$ is not connected with probability at most $O((n-k+1)^{2-s})$ under any of the considered conditions and, hence, also unconditionally.

A $(k-1)$-set $A$ is called “bad”, if the graph $G(H^{*},A)$ is not connected and let $t$ be the random variable equal to the number of such sets. By the argument above, we have

$$\mathbf{E}\;t=O\left((n-k+1)^{2-s}\right){n\choose k-1}\;.$$ (20)

For each of the $t$ “bad” sets $A$, we add several $(k+1)$-sets to $H^{*}$ to make $G(H^{*},A)$ connected. The number of $(k+1)$-sets needed for this is at most the number of the connected components $G(H^{*},A)$ minus $1$ which is at most $(n-k)/2$. Hence, the resulting $(k+1)$-uniform hypergraph $H^{**}$ has size at most $s|H|+t(n-k)/2$. By (20), there is a choice of permutations $\pi_{i}$ for $i=1,\ldots,s$, such that

$$t\leq O\left((n-k+1)^{2-s}\right){n\choose k-1}\leq O\left((n-k+1)^{2-s}\right){n\choose k}$$

Since $n-k=\Theta(k)$, we can conclude

$$|H^{**}|\leq s|H|+O\left(k^{3-s}\right){n\choose k}\;.$$

Using (1) and $s=5$, we get

$$|H^{**}|\leq(s+1)|H|\leq 6\,C(n,k+1,k)$$

if $n$ and, hence, also $k$ are sufficiently large. This finishes the proof, since $H^{**}$ has connected restrictions. ∎

8 Proof of the results

In this section, we summarize the results of the previous sections. First, we finish the proof of Theorem 4.4 which presents a lower and an upper bound on the size of a smallest formula ucp-equivalent to $\Psi_{n,k}$ needed for the proof of the main result.

Proof of Theorem 4.4.

The lower bound is Proposition 5.4. For the upper bound, consider a hypergraph $H$ of size at most $6\,C(n,k+1,k)$ with connected restrictions guaranteed by Proposition 7.1. By Proposition 5.6, $\theta(H)$ is ucp-equivalent to $\Psi_{n,k}$ and its size is $(k+1)|H|$. It follows that the size of a smallest formula ucp-equivalent to $\Psi_{n,k}$ is at most $6\,(k+1)C(n,k+1,k)$. Using (2) and the bound (5) or (7), we obtain the required asymptotic estimate. ∎

The main result is Theorem 4.1 providing an almost linear separation between the size of a specific ucp-irredundant formula ucp-equivalent to $\Psi_{n,k}$ and a smallest such formula.

Proof of Theorem 4.1.

Let $\varphi^{\ell}$ be the formula defined in Section 5. This formula is an irredundant PC formula equivalent to $\Psi_{n,k}$ by Proposition 5.8 and its size is

$$|\varphi^{\ell}|=(k+1){n-1\choose k}=(k+1)\left(1-\frac{k}{n}\right){n\choose k}=\Omega(n){n\choose k}\;.$$

Let $\varphi^{*}$ be a smallest formula ucp-equivalent to $\Psi_{n,k}$. The statement follows by comparing the lower bound on $|\varphi^{\ell}|$ and the upper bound on $|\varphi^{*}|$ implied by Theorem 4.4. ∎

Let us include an observation concerning the difference between the lower and the upper bound in Theorem 4.4. The following proposition implies that there is an infinite set of pairs $(n,k)$ satisfying $k=n/2+O(1)$ for which this lower and upper bound differ at most by a multiplicative constant. It remains open whether this is true for all pairs $(n,k)$ satisfying $k=n/2+O(1)$.

Proposition 8.1.

Let $a\in\mathbb{Z}$. We have $1\leq\mu(n,k)/\mu(n-1,k-1)\leq 3$ for infinitely many $k\geq 2$ and $n=2k+a$.

Proof.

By (8), we have $1\leq\mu(n,k)/\mu(n-1,k-1)$. Assume for a contradiction that for some $k_{0}\geq 2$ and every $k\geq k_{0}$ and $n=2k+a$, we have $\mu(n,k)/\mu(n-1,k-1)>3$. Let $P=\{(n,k)\mid k\geq k_{0},n=2k+a\}$. By (9), the pairs $(n,k)\in P$ satisfy

$$\frac{\mu(n+1,k)}{\mu(n,k)}\geq\frac{k+a+1}{2k+a+1}=\frac{1}{2}+o(1)$$

and since $(n+2,k+1)\in P$, we have

$$\frac{\mu(n+2,k+1)}{\mu(n+1,k)}>3$$

implying

$$\frac{\mu(n+2,k+1)}{\mu(n,k)}\geq\frac{3}{2}+o(1)\;.$$

It follows that $\mu(n,k)$ grows exponentially with $k$ for pairs $(n,k)\in P$ which contradicts the bound $\mu(n,k)=O(\ln n)$. ∎

9 Conclusion and further research

The paper shows that a general upper bound on the ratio of the size of a ucp-irredundant formula and the size of a smallest ucp-equivalent formula is at most $n^{2}$ (Proposition 3.3) and at least $\Omega(n/\ln n)$ (Theorem 4.1). The gap between these bounds is quite large. An interesting open problem for further research is to reduce this gap.

The lower and the upper bound on the size of a smallest formula ucp-equivalent to $\Psi_{n,k}$ in Theorem 4.4 differ by a factor $\Theta(\mu(n,k)/\mu(n-1,k-1))$. Is this factor bounded by a constant for every $k\geq 2$ and $n=2k+a$ if $a\in\mathbb{Z}$ is fixed?

Acknowledgement. The author would like to thank Diana Piguet for a fruitful discussion on using hypergraphs, in particular, for suggesting Definition 4.5, and Matas Šileikis for suggesting Lemma 6.2 which improves a slightly weaker bound on the same quantity by the author. The author acknowledges institutional support RVO:67985807.