{"entities":{"Q2416442":{"pageid":2427185,"ns":120,"title":"Item:Q2416442","lastrevid":74104293,"modified":"2026-04-14T18:22:48Z","type":"item","id":"Q2416442","labels":{"en":{"language":"en","value":"Treewidth of grid subsets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7058213"}},"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":"Q2416442$81ADDCC3-ACF6-46E7-82EE-3AED232D69D9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d9d67cda55b9b2414394330423100274f72daac6","datavalue":{"value":{"text":"Treewidth of grid subsets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2416442$DA2F7C35-96CE-4715-9C03-12A79CF6C150","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4ad823c438eeeaeaba0cb711466afb6092fdf73a","datavalue":{"value":"1449.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2416442$24D5A091-F719-4A28-8F4E-6901F08292E5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84a8555b67c6b23fa0b4b81d144fd117edd2c5b2","datavalue":{"value":{"entity-type":"item","numeric-id":186190,"id":"Q186190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2416442$5CCB8AC5-B5A4-430D-B2C2-48E4B7278F38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"350eba5e980e4fd79c371adfd049f978487e189c","datavalue":{"value":{"entity-type":"item","numeric-id":2416441,"id":"Q2416441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2416442$4BDD5548-EAED-4FF4-974A-C620B3BDD306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"de1d4457fd68ac1c44e4c5653031d868f82a4bb2","datavalue":{"value":{"entity-type":"item","numeric-id":462931,"id":"Q462931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2416442$5DD35BCB-E14A-418C-8988-5FE394BF57F9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2416442$07A83DF9-FAC1-41F0-9F8F-9FA3EB44E7C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7175bc5b448813e6c45463c465346435e9aa8168","datavalue":{"value":{"time":"+2019-05-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2416442$ED1B8D85-7EBE-4BCC-AD60-C91BEFF01458","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a6df86d134dff199ad9653739b66bc8279d1b56a","datavalue":{"value":"https://arxiv.org/abs/1512.06441","type":"string"},"datatype":"url"},"type":"statement","id":"Q2416442$2FD51507-DE78-4D28-A61C-F2869ED875CE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c422ac93a660e3b10cd135e7825578ff0929e3fe","datavalue":{"value":"The \\(3\\)-dimensional \\( n \\times n \\times n \\) grid \\( Q_n \\) considered in this paper is the `usual' \\(3\\)-dimensional grid with non-decreasing diagonals of its unit cubes added to its set of edges. Any \\(2\\)-coloring of the vertices of \\( Q_n \\) is known to contain a monochromatic subgraph with \\( \\Omega(n^2)\\) vertices. This paper is concerned with the `\\(2\\)-dimensionality' of such subgraphs as represented by their tree-width. The authors prove that for any tree-width \\( t \\geq 0 \\) there exists an \\( n \\geq 1 \\) such that any partition of the vertices of \\(Q_n\\) into two sets has the property that at least one of the sets induces a subgraph of \\( Q_n\\) of tree-width at least \\(t\\). As a corollary, the class \\( Q_n \\), \\( n \\geq 1 \\), is not tree-width fragile. Unlike the previously known classes which are not tree-width fragile, the class \\( Q_n \\), \\( n \\geq 1 \\), has bounded maximum degree. It is also the first known class that is not tree-width fragile while being fractionally tree-width fragile. In addition, it is shown that any subset of vertices separating the vertices of \\(Q_n\\) into two subsets contains an induced subgraph of tree-width at least \\( \\frac{n}{\\sqrt{18}}-1 \\). The employed proof techniques include an interesting use of a discrete variant of homotopy theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2416442$90C90629-7979-432C-9708-20865A0B1F8A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2416442$F1731DEE-A9B4-48B8-8584-7312FBE4315C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"92fdc9036e64c972dddd917a937bda8fc8379ec4","datavalue":{"value":"7058213","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2416442$33BE20CB-C533-4F28-96C3-184764E6A2FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3dc05d0497e4605fde4276207e8e0b3665f62ff","datavalue":{"value":"3-dimensional grid","type":"string"},"datatype":"string"},"type":"statement","id":"Q2416442$85B1B44F-D022-4189-9927-704089BF2767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4ddb9001a4fb670917338446f2325c9c94cc52d","datavalue":{"value":"separating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2416442$AC6E0C55-CA63-488A-A4C2-F5A601C65D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q2416442$A5B2CD10-D5D7-480B-8C1E-DAF9A76A23FB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"35eaf61e442e867df19139f413c267c580a3f0bb","datavalue":{"value":{"entity-type":"item","numeric-id":162920,"id":"Q162920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2416442$CDF7F9ED-8092-401B-9E86-BC0FAA6BA035","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":"Q2416442$ECF1E82A-295D-4CA8-A54F-3E8DC9644FBE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bbe72aed4ec3f2b006cf47cfc32e578a64b68123","datavalue":{"value":"W2963873020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2416442$98DEC1C5-6439-4103-8BFD-BC9F6A24FA2F","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d5289d226d942ef31b8c682a713a53ac054ce4d3","datavalue":{"value":"Q128420021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2416442$BB34C535-064B-4256-B609-FA7515D757B6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"38d41e4045beb69d435e2cbc1e6f1169f538d615","datavalue":{"value":"10.1007/S00493-017-3538-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2416442$0B4A5BE6-D3AC-4304-9EEC-19C0BCE23FA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd3243b5fb05b905eb7a90f4665d612324312c32","datavalue":{"value":{"entity-type":"item","numeric-id":897618,"id":"Q897618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af0b0311d56ac183ff4c827812d0331d53e87844","datavalue":{"value":{"amount":"+0.7319591045379639","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":"Q2416442$1AA9226E-4B19-4188-BC46-9CA862366299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"293352a29d4634b5499f218727dc9e85105c062c","datavalue":{"value":{"entity-type":"item","numeric-id":2766682,"id":"Q2766682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4ce479e56540b3ee5949f09afce6da63784bb3b","datavalue":{"value":{"amount":"+0.7318751215934753","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":"Q2416442$D43CDE52-9842-4B0C-A971-4E06B0CA07DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfa38122c789916807b00273af6628f4a409cae9","datavalue":{"value":{"entity-type":"item","numeric-id":1024321,"id":"Q1024321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c104ec86228535ebb634b2cd0681e302cf3d649a","datavalue":{"value":{"amount":"+0.7310982942581177","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":"Q2416442$C12250FB-0268-426C-B69D-08E5879CD507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e1b83388987e4fb6cf6829ab856adb6f793bf26","datavalue":{"value":{"entity-type":"item","numeric-id":1306423,"id":"Q1306423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"926a563feb303f874b2b8bac9b3937de8ca848be","datavalue":{"value":{"amount":"+0.7260593175888062","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":"Q2416442$A57DE4D8-79F4-42B1-B247-15AC6D05C107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca67f7d8ff80f5d4752ec6a273751d659840a560","datavalue":{"value":{"entity-type":"item","numeric-id":5902522,"id":"Q5902522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"926a563feb303f874b2b8bac9b3937de8ca848be","datavalue":{"value":{"amount":"+0.7260593175888062","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":"Q2416442$4F56B522-145D-4575-A436-6B53735324AC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Treewidth of grid subsets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Treewidth_of_grid_subsets"}}}}}