{"entities":{"Q2870501":{"pageid":2881221,"ns":120,"title":"Item:Q2870501","lastrevid":83953196,"modified":"2026-05-07T14:52:10Z","type":"item","id":"Q2870501","labels":{"en":{"language":"en","value":"Optimizing the graph minors weak structure theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6248034"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870501$818479F7-46FF-4320-8BD9-0A9761DFD097","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d1fe3436bd51b0c7d1b22c6d8d6214eadd900934","datavalue":{"value":"1283.05253","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870501$7B5F7245-4F02-4129-B51B-676703C9E3B1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"040c451707178140ed30181380c3398b6c988f5b","datavalue":{"value":"10.1137/110857027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870501$67D509DA-937E-4C85-BA7F-58E1519DAED0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ab1127874727d7404c2dac50647044559b4cf39","datavalue":{"value":{"entity-type":"item","numeric-id":395007,"id":"Q395007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870501$D1515922-384C-41A5-B4CD-6AC6B6C04A68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1348fb004fb071dffe1335a9785ae0b754bd6be2","datavalue":{"value":{"entity-type":"item","numeric-id":284716,"id":"Q284716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870501$DF2EE823-D166-4424-86E4-9D58FF714FFB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39a509948a5fd41054da3e7af81581f39adaebc1","datavalue":{"value":{"entity-type":"item","numeric-id":2706174,"id":"Q2706174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870501$AE85DF1C-7628-416F-B386-77E2B33155A8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41a1e4f019ef435c314233e0481265bcc6e79494","datavalue":{"value":{"time":"+2014-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2870501$3AE1D164-08DD-4136-97DA-B1F576DFE4A5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ef79d515f7779dc6f106379f042127b3adb46f00","datavalue":{"value":"https://arxiv.org/abs/1102.5762","type":"string"},"datatype":"url"},"type":"statement","id":"Q2870501$55ABF3AB-6C92-43D5-A351-08719CD840A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870501$BA67733B-6969-4DB1-B460-68289AD774AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870501$0A7DCB29-65BE-4B16-9DDE-2A2FF16DD725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870501$4B3E1115-131A-45A2-A06C-6AC805201B74","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d459300e557fe08cf44515d192ecaf024112ba5d","datavalue":{"value":"6248034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870501$22243C5B-748E-4775-8556-791FCC37C0D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b4a7e94f67b1256fa87c9c444c77ea9a3d63a5","datavalue":{"value":"graph minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q2870501$E1C51B44-8E82-4283-8684-007F9D5BDDBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2870501$5A4846EA-4C70-430F-B3ED-D2A62753C603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bfbab3dbf8e7ac2c2c629063b4b1d1deefc28c2","datavalue":{"value":"weak structure theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2870501$CB9798F7-BFF3-4BE3-9B42-61F0DF3FD57F","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870501$C20DF18D-D25B-4381-B768-F79088D29760","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"018102e6e9cd3f5203ea2f65961a9d4734ec8f93","datavalue":{"value":"W1928357011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870501$456A574B-CDA0-4E85-86B9-1C158A8AED80","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f1be9c0a7bb88d7cf4cd16fa68a9a5df8c9db105","datavalue":{"value":{"text":"Optimizing the graph minors weak structure theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2870501$67C64AC5-E987-4442-9D72-AA17035609AE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8a90524fd1f9f6a1db8cf082bcf3c71d02ed6485","datavalue":{"value":"A key result in the structural theory of graphs is Robertson, Seymour and Thomas's so-called weak structure theorem for graphs excluding a certain fixed graph as a minor [\\textit{N. Robertson} and \\textit{P. D. Seymour}, J. Comb. Theory, Ser. B 63, No. 1, 65--110 (1995; Zbl 0823.05038)]. The original theorem is that there is a function \\(f: \\mathbb{N}\\times \\mathbb{N}\\rightarrow \\mathbb{N}\\) such that for every \\(k\\in \\mathbb{N}\\), every \\(h\\)-vertex graph \\(H\\) and every graph \\(G\\), either \\(G\\) contains \\(H\\) as a minor, or \\(G\\) has treewidth at most \\(f(h,k)\\) or there is a set \\(X\\) of at most \\({h\\choose 2}\\) vertices (apices) of \\(G\\) such that \\(G\\backslash X\\) contains as a subgraph a subdivision of a certain graph, the `wall\\'\\, of height \\(k\\) which is arranged in \\(G\\) in a certain `flat\\'\\, manner (called the flatness condition: we omit its exact definition).NEWLINENEWLINEThe paper under review gives a significant sharpening of the weak structure theorem by firstly, making \\(f(h,k)\\) a function linear in \\(k\\) and secondly by reducing the maximum number of apices from \\({h\\choose 2}\\) to \\(h-5\\). This is optimal as can be shown by considering a \\(k\\times k\\) grid all of whose vertices are adjacent to all vertices in a \\(K_{h-5}\\). The proof is non-trivially harder than in the original paper of Robertson and Seymour: in particular, it uses their strong structure theory on the global structure of graphs with no \\(K_{h}\\) minor [\\textit{N. Robertson} and \\textit{P. D. Seymour}, J. Comb. Theory, Ser. B 89, No. 1, 43--76 (2003; Zbl 1023.05040)] together with facts from [\\textit{F. V. Fomin} et al., J. Comb. Theory, Ser. B 101, No. 5, 302--314 (2011; Zbl 1223.05022)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2870501$432C8B5E-CC1A-4E85-8B46-D78DDDB28310","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870501$DEBE748E-FD98-4753-BB56-70E9151ABEB9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa6f69240d5e51c2e980f20c2924dcd115bf26c","datavalue":{"value":{"entity-type":"item","numeric-id":684127,"id":"Q684127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e1f7db712c5071870846e13f09977cc4bf3adfd","datavalue":{"value":{"amount":"+0.7974515557289124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870501$ED6D461B-7B74-4FD3-B8ED-FE60CB23D9FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60dbfca7da0878fa8f66666f33d733f09a08a3d1","datavalue":{"value":{"entity-type":"item","numeric-id":5363032,"id":"Q5363032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16670cae0d7c679b7e2d16969d67eb036d874b5d","datavalue":{"value":{"amount":"+0.7952998280525208","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870501$FBFA020C-65C9-4510-BAEA-B32BE91CC74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd0558ea7ec61fec5d08153e189af9218240d290","datavalue":{"value":{"entity-type":"item","numeric-id":1931397,"id":"Q1931397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12de7a654dbd19718a27a203b819a601ccbe46a2","datavalue":{"value":{"amount":"+0.7892444133758545","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870501$00DD06FD-A428-4CFA-BBB1-390423E5BEF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8bd224906d17e736734db95be1e3409eb8962a9","datavalue":{"value":{"entity-type":"item","numeric-id":5415695,"id":"Q5415695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df2ef7af4f50a3237ea1abdd2f69b43126a0dc2b","datavalue":{"value":{"amount":"+0.7801718711853027","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870501$6BC38ACC-0A64-4966-900F-D96E60226444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60eac97d6e07721bd54bc9f22830e87f4ba797f6","datavalue":{"value":{"entity-type":"item","numeric-id":1932472,"id":"Q1932472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69fb5bc3fa565d088aa35b28895fd7be71d3688f","datavalue":{"value":{"amount":"+0.7726318836212158","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870501$B87A7626-DB4F-45FB-8D52-D24B042D41CF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimizing the graph minors weak structure theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimizing_the_graph_minors_weak_structure_theorem"}}}}}