Skip to main content

php_is_partial_matching

Function php_is_partial_matching 

Source
pub fn php_is_partial_matching(mono: Mono, holes: usize) -> bool
Expand description

Is a PHP monomial a partial matching — an injective partial pigeon→hole map? PHP’s variable x_{p,h} sits at index p·holes + h (crate::families::php), so a monomial (a set of variables) is a partial matching iff no two of its variables share a pigeon or a hole. This is the support of the Razborov degree lower bound’s pseudo-expectation.