{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T09:55:30Z","timestamp":1781344530271,"version":"3.54.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T00:00:00Z","timestamp":1781308800000},"content-version":"vor","delay-in-days":12,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1657377 and CCF-1942742"],"award-info":[{"award-number":["CCF-1657377 and CCF-1942742"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In an influential paper, Erd\u0151s and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values to variables of their choosing, and Breaker\u2019s goal is to satisfy the CNF, while Maker\u2019s goal is to falsify it. The Erd\u0151s\u2013Selfridge Theorem says that the least number of clauses in any monotone CNF with\n                    <jats:italic>k<\/jats:italic>\n                    literals per clause where Maker has a winning strategy is\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\Theta (2^k)}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u0398<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>2<\/mml:mn>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . We study the analogous question when the CNF is not necessarily monotone. We prove bounds of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\Theta (\\sqrt{2}\\,^k)}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u0398<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msqrt>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msqrt>\n                            <mml:mmultiscripts>\n                              <mml:mspace\/>\n                              <mml:mrow\/>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:mmultiscripts>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    when Maker plays last, and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\Omega (1.5^k)}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03a9<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>.<\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>5<\/mml:mn>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{O(r^k)}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>r<\/mml:mi>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    when Breaker plays last, where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{r=(1+\\sqrt{5})\/2\\approx 1.618}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:msqrt>\n                              <mml:mn>5<\/mml:mn>\n                            <\/mml:msqrt>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>\/<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mo>\u2248<\/mml:mo>\n                            <mml:mn>1.618<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is the golden ratio.\n                  <\/jats:p>","DOI":"10.1007\/s00224-026-10281-y","type":"journal-article","created":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T09:00:19Z","timestamp":1781341219000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Erd\u0151s\u2013Selfridge Theorem for Nonmonotone CNFs"],"prefix":"10.1007","volume":"70","author":[{"given":"Md Lutfar","family":"Rahman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Watson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"10281_CR1","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P., Selfridge, J.: On a combinatorial game. Journal of Combinatorial Theory, Series A 14(3) (1973)","DOI":"10.1016\/0097-3165(73)90005-8"},{"key":"10281_CR2","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: Complexity of decision problems based on finite two-person perfect-information games. In: Proceedings of the 8th Symposium on Theory of Computing (STOC), pp. 41\u201349. ACM (1976)","DOI":"10.1145\/800113.803629"},{"issue":"2","key":"10281_CR3","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"T Schaefer","year":"1978","unstructured":"Schaefer, T.: On the complexity of some two-person perfect-information games. J. Comput. Syst. Sci. 16(2), 185\u2013225 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"10281_CR4","doi-asserted-by":"crossref","unstructured":"Byskov, J.: Maker-Maker and Maker-Breaker games are PSPACE-complete, BRICS, Department of Computer Science, Aarhus University (2004). (RS-04-14 Technical Report)","DOI":"10.7146\/brics.v11i14.21839"},{"key":"10281_CR5","unstructured":"Kutz, M.: The angel problem, positional games, and digraph roots. PhD thesis, Freie Universit\u00e4t Berlin. Chapter 2: Weak Positional Games (2004)"},{"key":"10281_CR6","doi-asserted-by":"crossref","unstructured":"Kutz, M.: Weak positional games on hypergraphs of rank three. In: Proceedings of the 3rd European Conference on Combinatorics, Graph Theory, and Applications (EuroComb), pp. 31\u201336. Discrete Mathematics & Theoretical Computer Science, (2005)","DOI":"10.46298\/dmtcs.3422"},{"key":"10281_CR7","doi-asserted-by":"crossref","unstructured":"Ahlroth, L., Orponen, P.: Unordered constraint satisfaction games. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 64\u201375. Springer (2012)","DOI":"10.1007\/978-3-642-32589-2_9"},{"issue":"3","key":"10281_CR8","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/3397478","volume":"12","author":"ML Rahman","year":"2020","unstructured":"Rahman, M.L., Watson, T.: Complexity of unordered CNF games. ACM Transactions on Computation Theory. 12(3), 18 (2020)","journal-title":"ACM Transactions on Computation Theory."},{"issue":"2","key":"10281_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/s00037-025-00274-7","volume":"34","author":"ML Rahman","year":"2025","unstructured":"Rahman, M.L., Watson, T.: Tractable unordered 3-CNF games. Comput. Complex. 34(2), 12 (2025)","journal-title":"Comput. Complex."},{"issue":"3","key":"10281_CR10","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s00493-023-00026-7","volume":"43","author":"ML Rahman","year":"2023","unstructured":"Rahman, M.L., Watson, T.: 6-uniform Maker-Breaker game is PSPACE-complete. Combinatorica 43(3), 595\u2013612 (2023)","journal-title":"Combinatorica"},{"key":"10281_CR11","doi-asserted-by":"publisher","unstructured":"Galliot, F., Gravier, S., Sivignon, I.: Maker-Breaker is solved in polynomial time on hypergraphs of rank 3. Technical Report (2022). arXiv:2209.12819, https:\/\/doi.org\/10.48550\/arXiv.2209.12819","DOI":"10.48550\/arXiv.2209.12819"},{"key":"10281_CR12","unstructured":"Rahman, M.L., Watson, T.: Erd\u0151s-Selfridge theorem for nonmonotone CNFs. In: Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), p. 31. Schloss Dagstuhl (2022)"},{"key":"10281_CR13","doi-asserted-by":"crossref","unstructured":"Hefetz, D., Krivelevich, M., Stojakovi\u0107, M., Szab\u00f3, T.: Positional Games. Springer (2014)","DOI":"10.1007\/978-3-0348-0825-5"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10281-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10281-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10281-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T09:00:26Z","timestamp":1781341226000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10281-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10281"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10281-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"12 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"39"}}