TY - GEN

T1 - Resolution complexity of perfect matching principles for sparse graphs

AU - Itsykson, Dmitry

AU - Slabodkin, Mikhail

AU - Sokolov, Dmitry

PY - 2015/1/1

Y1 - 2015/1/1

N2 - The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph Gn such that the resolution complexity of the perfect matching principle for Gn is 2Ω(n), where n is the number of vertices in Gn. This lower bound is tight up to some polynomial. Our result implies the 2Ω(n) lower bounds for the complete graph K2n+1 and the complete bipartite graph Kn,O(n) that improves the lower bounds following from [Raz04]. Our results also imply the well-known exponential lower bounds on the resolution complexity of the pigeonhole principle, the functional pigeonhole principle and the pigeonhole principle over a graph. We also prove the following corollary. For every natural number d, for every n large enough, for every function h : {1, 2, ..., n} → {1, 2, ..., d}, we construct a graph with n vertices that has the following properties. There exists a constant D such that the degree of the i-th vertex is at least h(i) and at most D, and it is impossible to make all degrees equal to h(i) by removing the graph’s edges. Moreover, any proof of this statement in the resolution proof system has size 2Ω(n). This result implies well-known exponential lower bounds on the Tseitin formulas as well as new results: for example, the same property of a complete graph.

AB - The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph Gn such that the resolution complexity of the perfect matching principle for Gn is 2Ω(n), where n is the number of vertices in Gn. This lower bound is tight up to some polynomial. Our result implies the 2Ω(n) lower bounds for the complete graph K2n+1 and the complete bipartite graph Kn,O(n) that improves the lower bounds following from [Raz04]. Our results also imply the well-known exponential lower bounds on the resolution complexity of the pigeonhole principle, the functional pigeonhole principle and the pigeonhole principle over a graph. We also prove the following corollary. For every natural number d, for every n large enough, for every function h : {1, 2, ..., n} → {1, 2, ..., d}, we construct a graph with n vertices that has the following properties. There exists a constant D such that the degree of the i-th vertex is at least h(i) and at most D, and it is impossible to make all degrees equal to h(i) by removing the graph’s edges. Moreover, any proof of this statement in the resolution proof system has size 2Ω(n). This result implies well-known exponential lower bounds on the Tseitin formulas as well as new results: for example, the same property of a complete graph.

UR - http://www.scopus.com/inward/record.url?scp=84950123244&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-20297-6_15

DO - 10.1007/978-3-319-20297-6_15

M3 - Conference contribution

AN - SCOPUS:84950123244

SN - 9783319202969

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 219

EP - 230

BT - Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings

A2 - Beklemishev, Lev D.

A2 - Musatov, Daniil V.

A2 - Musatov, Daniil V.

PB - Springer Nature

T2 - 10th International Computer Science Symposium in Russia, CSR 2015

Y2 - 13 July 2015 through 17 July 2015

ER -