The Tseitin formulas are as follows: Given a connected graph and a function $\alpha: V \rightarrow \{0,1\}$. Associate each edge $e$ with a variable $x_e$. The Tseitin formula $G(\alpha)$ is defined to be$$\bigwedge_{v \in V} \big(\sum_{(u,v) \in E(G)} x_{(u,v)} = \alpha(v) \mod 2 \big)$$It's easy to see that the Tseitin formula $G(\alpha)$ is satisfiable iff $\sum_{v \in V} \alpha(v) = 0 \mod 2$.This gives a nice characterization of the satisfiability of a system of random mod2 equations ($k$-XORs) $Ax = b \mod 2$ where each variable occurs in exactly 2 equations in the system which is connected (we cannot partition the rows of $A$ into two sets $A_1$ and $A_2$ so that $A_1 \cap A_2 = \emptyset$). Push the negation of any variable in a constraint into $b$ so that all variables occur positively in $A$. $Ax = b$ is then satisfiable iff $$\sum_{i = 1}^{|b|} b_i= 0 \mod 2.$$This is because $Ax = b$ is equivalent to the Tseitin formulas where for each constraint $a_ix = b_i$ we create a vertex $v_i$ where $\alpha(v_i) = b_i$ and each variable $x_i$ corresponds to an edge between the two constraints in which $x_i$ appears. My question is, if we relax the requirement that each variable occurs in 2 equations (to say at most $k$ equations), is there a similar nice combinatorial characterization of the satisfiability of the system of equations? This corresponds to a hypergraph version of the Tseitin formulas. It's easy to see that in this case if $\sum_{i=1}^{|b|} = 1\mod 2$ is odd then the system is unsatisfiable, but the other direction does not hold. Is there a nice sufficient condition for the satisfiability of such a system?
Combinatorial characterization of hypergraph Tseitin satisfiability
cc.complexity theory;proof complexity