The Setting
A graph on vertices is an assignment of zeros and ones to the possible edges , where and means that an edge is present. Coordinate restrictions study the dependence of a function on selected edges when the remaining edges are fixed.
For sets and , write for the set of assignments .
The Definition
Definition 1. Let be a coordinate set, let be the free coordinates, and put . Let be a set of coordinate values. For assignments and , the pasted configuration is defined by (1): (1)✦ Let be a set of function values and let . The coordinate restriction at the exterior assignment is the function defined by (2): (2)✦
In the paper, the result reads: for and , an exterior assignment defines on at bias , and the restriction identities hold for every Boolean function , without invariance or monotonicity.
What Is Checked
The pasting and restriction definitions are stated over arbitrary coordinate and value sets, with an arbitrary function on the full assignment space and an arbitrary fixed exterior assignment.