{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:07Z","timestamp":1750306327430,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,6,14]],"date-time":"2016-06-14T00:00:00Z","timestamp":1465862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union's Seventh Framework Programme","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}]},{"name":"Eduard \u010cech Center"},{"name":"European Research Council"},{"name":"ERC","award":["279611"],"award-info":[{"award-number":["279611"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2016,7,26]]},"abstract":"<jats:p>\n            Ramsey\u2019s Theorem is a cornerstone of combinatorics and logic. In its simplest formulation it says that for every\n            <jats:italic>k<\/jats:italic>\n            &gt; 0 and\n            <jats:italic>s<\/jats:italic>\n            &gt; 0, there is a minimum number\n            <jats:italic>r<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>s<\/jats:italic>\n            ) such that any simple graph with at least\n            <jats:italic>r<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>s<\/jats:italic>\n            ) vertices contains either a clique of size\n            <jats:italic>k<\/jats:italic>\n            or an independent set of size\n            <jats:italic>s<\/jats:italic>\n            . We study the complexity of proving upper bounds for the number\n            <jats:italic>r<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            ). In particular, we focus on the propositional proof system cutting planes; we show that any cutting plane proof of the upper bound \u201c\n            <jats:italic>r<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            ) \u2a7d 4\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            \u201d requires high rank. In order to do that we show a protection lemma which could be of independent interest.\n          <\/jats:p>","DOI":"10.1145\/2903266","type":"journal-article","created":{"date-parts":[[2016,6,15]],"date-time":"2016-06-15T19:32:01Z","timestamp":1466019121000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Rank Lower Bound for Cutting Planes Proofs of Ramsey\u2019s Theorem"],"prefix":"10.1145","volume":"8","author":[{"given":"Massimo","family":"Lauria","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e9cnica de Catalunya, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-010-0247-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370100000"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225275"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275569"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.17"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90167-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(89)90476-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.170.941"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"#cr-split#-e_1_2_1_14_1.1","doi-asserted-by":"crossref","unstructured":"Paul Erd\u0151s and G. Szekeres. 1987. A combinatorial problem in geometry. In Classic Papers in Combinatorics Ira Gessel and Gian-Carlo Rota (Eds.). Birkh\u00e4user Boston 49--56. DOI:http:\/\/dx.doi.org\/10.1007\/978-0-8176-4842-8_3 10.1007\/978-0-8176-4842-8_3","DOI":"10.1007\/978-0-8176-4842-8_3"},{"key":"#cr-split#-e_1_2_1_14_1.2","doi-asserted-by":"crossref","unstructured":"Paul Erd\u0151s and G. Szekeres. 1987. A combinatorial problem in geometry. In Classic Papers in Combinatorics Ira Gessel and Gian-Carlo Rota (Eds.). Birkh\u00e4user Boston 49--56. DOI:http:\/\/dx.doi.org\/10.1007\/978-0-8176-4842-8_3","DOI":"10.1007\/978-0-8176-4842-8_3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1838552.1838556"},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"The cutting plane proof system with bounded degree of falsity","author":"Goerdt Andreas","unstructured":"Andreas Goerdt . 1992. The cutting plane proof system with bounded degree of falsity . In Computer Science Logic, Egon B\u00f6rger, Gerhard J\u00e4ger, Hans Kleine B\u00fcning, and MichaelM. Richter (Eds.). Lecture Notes in Computer Science , Vol. 626 . Springer , Berlin , 119--133. DOI:http:\/\/dx.doi.org\/10.1007\/BFb0023762 10.1007\/BFb0023762 Andreas Goerdt. 1992. The cutting plane proof system with bounded degree of falsity. In Computer Science Logic, Egon B\u00f6rger, Gerhard J\u00e4ger, Hans Kleine B\u00fcning, and MichaelM. Richter (Eds.). Lecture Notes in Computer Science, Vol. 626. Springer, Berlin, 119--133. DOI:http:\/\/dx.doi.org\/10.1007\/BFb0023762"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1958-10224-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11499107_10"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1994.316069"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050024"},{"volume-title":"Boolean Function Complexity: Advances and Frontiers","author":"Jukna Stasys","key":"e_1_2_1_21_1","unstructured":"Stasys Jukna . 2012. Boolean Function Complexity: Advances and Frontiers . Springer-Verlag , Berlin . Stasys Jukna. 2012. Boolean Function Complexity: Advances and Frontiers. Springer-Verlag, Berlin."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070302"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-010-0212-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802454"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39071-5_26"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/647840.736235"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.05.004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90044-9"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903266","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2903266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:33Z","timestamp":1750222473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,14]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,26]]}},"alternative-id":["10.1145\/2903266"],"URL":"https:\/\/doi.org\/10.1145\/2903266","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2016,6,14]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}