{"entities":{"Q668066":{"pageid":669915,"ns":120,"title":"Item:Q668066","lastrevid":63519984,"modified":"2026-04-11T13:43:20Z","type":"item","id":"Q668066","labels":{"en":{"language":"en","value":"Algebraically grid-like graphs have large tree-width"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7032087"}},"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":"Q668066$D81EE4FB-D0CA-41A5-993D-D237F4EE0916","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"768e3f307128472153d726fa9b010ff2d8cd6b0a","datavalue":{"value":{"text":"Algebraically grid-like graphs have large tree-width","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q668066$6C4992CE-B604-4573-866F-E6D613536BFA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7dab95dc3c207da2752a4141f0411ad108860459","datavalue":{"value":"1409.05193","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668066$9578A5C6-C41C-4E3A-B5E2-6C86EBE05550","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea87ea4e3b94d0da7f659ddc29b208d6219ed2f5","datavalue":{"value":{"entity-type":"item","numeric-id":668065,"id":"Q668065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668066$11E59E8F-57FA-4329-9FB0-0AB235967A3A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668066$935EF375-6143-461F-8BEF-349C47CB34B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c236a5296bce37f0e3594963375752714d7f6e86","datavalue":{"value":{"time":"+2019-03-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q668066$9894B725-F872-4162-A802-CB128101F65E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fe2166398b3c6054cba43b7e0cb8351e29e3e1b6","datavalue":{"value":"https://arxiv.org/abs/1802.05158","type":"string"},"datatype":"url"},"type":"statement","id":"Q668066$DE2B690C-D16C-4204-8944-D7BABE6C7AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ed827b09f7921bbb5c81b9d4e3afa944a3d312b","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/7691","type":"string"},"datatype":"url"},"type":"statement","id":"Q668066$49409148-5097-469B-B39B-C89FBB7D776A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e513d266908e72bdf60dd68c9c8bfedaf02ceaab","datavalue":{"value":"Summary: By the Grid Minor Theorem of Robertson and Seymour, every graph of sufficiently large tree-width contains a large grid as a minor. Tree-width may therefore be regarded as a measure of `grid-likeness' of a graph.  The grid contains a long cycle on the perimeter, which is the \\(\\mathbb{F}_2\\)-sum of the rectangles inside. Moreover, the grid distorts the metric of the cycle only by a factor of two. We prove that every graph that resembles the grid in this algebraic sense has large tree-width:  Let \\(k\\), \\(p\\) be integers, \\(\\gamma\\) a real number and \\(G\\) a graph. Suppose that \\(G\\) contains a cycle of length at least \\(2 \\gamma p k\\) which is the \\(\\mathbb{F}_2\\)-sum of cycles of length at most \\(p\\) and whose metric is distorted by a factor of at most \\(\\gamma\\). Then \\(G\\) has tree-width at least \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q668066$01FCECFE-FE57-4F78-89F2-C139149721D2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668066$3A2F1C6C-FD2B-407B-8512-275863F1E43B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668066$F9195F69-5689-471E-BBF4-BA75B15290C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668066$690E497D-19A8-49F0-8B7E-D1F7AA8AF2EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d553a3ebf90290f49d0291d403d6dc0a9a4ace19","datavalue":{"value":"7032087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668066$B14B3E43-78A8-4893-9A67-5789EB589E25","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":"Q668066$3E7A25B7-C073-4A09-ADE0-97C28343D4ED","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"192025b117aaf511bddf039f84017cef10bae5f0","datavalue":{"value":{"entity-type":"item","numeric-id":5741084,"id":"Q5741084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668066$1EEEF7CD-7820-489C-9B6B-FCCD794A8B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6760c1a0ed84f473ebf9c19dbb4d05bbf42b9a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3751592,"id":"Q3751592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668066$62B76C70-B2F6-473F-8A5E-5A8FB9B3BA9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0f6dd793166a567719b2fb5d958eb883aea03d","datavalue":{"value":{"entity-type":"item","numeric-id":1079583,"id":"Q1079583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668066$5D678605-2017-40A5-A553-83C693AD2169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"650620a8abff65a78f27b6d9c816323baf828dab","datavalue":{"value":{"entity-type":"item","numeric-id":2829286,"id":"Q2829286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668066$512415DC-CECF-4DD8-94E8-033DA0C823B5","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3c1a101ef0d70c4fd3b6f96da1450d0b3ea64999","datavalue":{"value":"bafkreibtge3gpxlynclrzfjuqrj4zsz3p5na2nln3iemtfegvo6wbfacr4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668066$DBCEADD5-B9A1-4C41-A1C3-0416402AA520","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88be93f4e51673042956e188219050a3e6f37282","datavalue":{"value":{"entity-type":"item","numeric-id":661945,"id":"Q661945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02af361ca20d38d06352510ede2a0401247a98c0","datavalue":{"value":{"amount":"+0.8058841228485107","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":"Q668066$C5FC76FC-92B0-44E4-A3AC-6F4E11C18A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0c95af1e8e5b9578ac7d7255218e784a79af69e","datavalue":{"value":{"entity-type":"item","numeric-id":5403052,"id":"Q5403052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a3a9632e260b0d05c363b992437a2cf756ad74a","datavalue":{"value":{"amount":"+0.7998917698860168","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":"Q668066$0DD364D4-2B52-46C7-A8A9-A27543A9C99B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b85c2815f98e5d2891ea6148c76d1b1e3e5cc3d7","datavalue":{"value":{"entity-type":"item","numeric-id":949776,"id":"Q949776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1291779d721aa631883c7c90cd7f426fc9947ca9","datavalue":{"value":{"amount":"+0.7782288193702698","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":"Q668066$B88B72C4-1CD2-4DE5-B127-A0B544C76F32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51050e18ee81df941018260825e076dc21aa92e0","datavalue":{"value":{"entity-type":"item","numeric-id":2839208,"id":"Q2839208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07c11e2a8590c0dfcaa84e10f52f3e660cd78085","datavalue":{"value":{"amount":"+0.7733640670776367","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":"Q668066$1D7DD2FE-0A8F-4DA5-BCD7-784F3488A1DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a01e76501bf8368fbee914b1e930154f7b500c8","datavalue":{"value":{"entity-type":"item","numeric-id":3177816,"id":"Q3177816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2dd15730b1926db01c491864634cf67e4eee0cd","datavalue":{"value":{"amount":"+0.7723809480667114","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":"Q668066$253A54D2-91D3-4056-9693-66A4DEABDAB1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algebraically grid-like graphs have large tree-width","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algebraically_grid-like_graphs_have_large_tree-width"}}}}}