{"entities":{"Q6599814":{"pageid":14210971,"ns":120,"title":"Item:Q6599814","lastrevid":100215407,"modified":"2026-06-05T21:37:58Z","type":"item","id":"Q6599814","labels":{"en":{"language":"en","value":"\\((k-2)\\)-linear connected components in hypergraphs of rank \\(k\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7908429"}},"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":"Q6599814$0D5313B4-F5B7-40D1-B4BE-05F799AE43AD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0ec5cd0e19c56d12cf6cc9066b481c46ea967c01","datavalue":{"value":{"text":"\\((k-2)\\)-linear connected components in hypergraphs of rank \\(k\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6599814$ABFFF78E-C8AD-4A7C-B6DA-F826B0CADD2F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d17645cd60662632ff31ac217860cfc315c13b6","datavalue":{"value":"1547.0521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6599814$3CE576FE-60EB-421A-BD30-02747ACECB67","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfc33fc722c2b590506dd899a70b04e2c1e6c54f","datavalue":{"value":{"entity-type":"item","numeric-id":6411980,"id":"Q6411980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$623F54BF-7965-425B-BEB1-52F2A173B55E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"692ce2048991e39aaf8d5623dc50cd220956e79b","datavalue":{"value":{"entity-type":"item","numeric-id":189438,"id":"Q189438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$9F5FF5AD-C919-4BC3-913B-11E441D987F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa4fccec2578b40144de4fb573e93498557dbec6","datavalue":{"value":{"entity-type":"item","numeric-id":244974,"id":"Q244974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$A4FC2611-65E8-420A-B7BB-8FAD5C65AE8B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c130b4c249cf6a7198c786d015c9f03c3441d6e","datavalue":{"value":{"entity-type":"item","numeric-id":6599785,"id":"Q6599785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$E28A06F1-F7D2-4D69-B861-0EC84CED163D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"74b4fed82336f4fd3de28daa42f3cd971eb88d0d","datavalue":{"value":{"time":"+2024-09-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6599814$2B308E54-E9AF-4B77-A76B-655C43F12377","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8c9a008716dd653a0f6c21c1db99a80c6017203","datavalue":{"value":"A linear path in an undirected graph is a sequence of edges such that any two consecutive edges intersect on exactly one vertex and any two non-consecutive edges do not intersect. The existence of such paths is the subject matter of several extremal results. The connectivity problem associated with linear paths in 3-uniform hypergraphs has stimulated the authors to do this work. To probe the linear connected components to elucidate their structure, the authors develop methods that generalize to hypergraphs of rank \\(k\\geq 4\\) when replacing linearity with a notion of \\((k-2)\\)-linearity. They introduce the general concept of a \\(q\\)-linear path, where any consecutive edges intersect between 1 and \\(q\\) vertices. The proof of their structural result allows them to compute the \\((k-2)\\)-linear connected components in polynomial time. This led to interesting sequels on two algorithmic problems that have existed in the literature for a long time. The first one is the problem of deciding the winner of the Maker-Breaker positional game. The second one is the ``paths avoiding forbidden pairs'' problem which, given two vertices \\(x\\), \\(y\\) in a graph \\(G\\) with blue and red edges, asks whether there exists a blue-induced path between \\(x\\) and \\(y\\) in \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6599814$30E916C4-D345-47CF-A920-382088561CAC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c754ec9fae75fbeaa94e089f2452dc68e1235b5c","datavalue":{"value":{"entity-type":"item","numeric-id":198726,"id":"Q198726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$EF4B23CF-FE88-4033-AB01-AA098D3ED3B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6599814$9FFE49E7-0849-4D91-B9BB-52697BBBF175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6599814$7ABCA2B0-DFB0-4A25-A1BB-E1CBF43635DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6599814$1417AABC-F62E-4044-B4D4-A369D7D988DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c74366160a9e6b2dc8a8a18f6280f93e87cf71ea","datavalue":{"value":"7908429","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6599814$B571B5AE-07D2-403A-9BB0-F0BD2A932164","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a48df0d8bdf1aa17b8f379600344c150e4abf352","datavalue":{"value":"3-uniform hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6599814$35E55E68-4D88-4C99-8BCC-6905767A1CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q6599814$831EF395-8C01-41E9-A0D5-96CBB80C896D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4b7154bd2d949bfec1797c90e4e25c3a12f45c4","datavalue":{"value":"linear path","type":"string"},"datatype":"string"},"type":"statement","id":"Q6599814$8E597B2D-2640-49FE-A9D7-00CE15BCA2C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9b43ae0f190acb8d132b00fab08bb35283981fe","datavalue":{"value":"chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q6599814$5B51D495-9F2C-472E-A6C9-A9A08289EF3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6599814$37175CC3-89A8-4364-A04A-4F0B3A28B6E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q6599814$9C79AFA9-1EB3-43C9-A43E-D22B4E21D15D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03fcb7d5fa9ef80777cea6b044b412c996cab74d","datavalue":{"value":"Maker-Breaker positional game","type":"string"},"datatype":"string"},"type":"statement","id":"Q6599814$72263A4B-4BDB-48B7-8B01-81A0E679DF70","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":"Q6599814$DBA2E499-F297-47DA-ADF1-7FC785C22C15","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"701b9767da9fa693d0772cedd2e5b756201984b4","datavalue":{"value":{"entity-type":"item","numeric-id":517789,"id":"Q517789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$FAE2E231-BBF6-416D-947C-2F699BB3288F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f63e38e4851ca0e3a13042d4f415c0b9fe4f5434","datavalue":{"value":{"entity-type":"item","numeric-id":5601346,"id":"Q5601346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$98C7B5B0-B184-414F-8CF8-D37C139EA3F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c23ff02a9289ca77610f00f721e01986dd43768c","datavalue":{"value":{"entity-type":"item","numeric-id":5360878,"id":"Q5360878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$0B61E4C6-D2F7-40FA-9078-447DBDF52A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7413f857f9c84644446f94a47c178ac05bb6a12f","datavalue":{"value":{"entity-type":"item","numeric-id":397075,"id":"Q397075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$C45A25B6-2275-4E2E-BDA7-54508F9EEA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55513ac0d8c3a56962aba277d470c4150e1c41d","datavalue":{"value":{"entity-type":"item","numeric-id":1803674,"id":"Q1803674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$D2D90B1B-E5DF-4C5D-BB8A-71085EE1430B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f37dbe15663414502328135853db0b258817b4ef","datavalue":{"value":{"entity-type":"item","numeric-id":5212951,"id":"Q5212951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$84E00F51-0DF1-4254-970A-07FCFBE1B695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7cd7b7c12384bee4ae0b0cc0262e20c7a990628","datavalue":{"value":{"entity-type":"item","numeric-id":714790,"id":"Q714790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$772B43B4-7C83-4748-9523-A84251A41DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e09a032f88bd9db4ac84a9d493faaac6a79d3a5e","datavalue":{"value":{"entity-type":"item","numeric-id":4373683,"id":"Q4373683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$4A5DC11F-E6E4-4FA6-B815-375B3BF7BF62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dab747c4bfd2edc0af7888b28bfe7f18ffc3bec0","datavalue":{"value":{"entity-type":"item","numeric-id":3451460,"id":"Q3451460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$0472B71A-D4DF-4C82-AF31-1D5949D98824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba3bd7ad81d7e232c0dc0967e6b46667df299874","datavalue":{"value":{"entity-type":"item","numeric-id":286115,"id":"Q286115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$8BC07667-AEAB-40F1-94A0-F13CCEEDA5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d0db7040feff8c3d36b4ae5c23650528d913da4","datavalue":{"value":{"entity-type":"item","numeric-id":967328,"id":"Q967328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$3E8FE33C-0E6C-46CB-9638-3E1729318D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5392509354156617804b7f5ab0f4b8e01b17f50e","datavalue":{"value":{"entity-type":"item","numeric-id":4351311,"id":"Q4351311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$77E7F838-2C99-464F-B930-2A51D4C209BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4dae2da69dfa67f7b35c62c2d984d052f0cbae5","datavalue":{"value":{"entity-type":"item","numeric-id":1167187,"id":"Q1167187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$B8F62532-253C-4065-97B8-B19C0062AB2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f7476f2f3a9b40c8ba14b104256b87be2be17be","datavalue":{"value":{"entity-type":"item","numeric-id":392807,"id":"Q392807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$0809F219-C265-4ECE-B7DC-2C7008D34BBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d535a4c42af949e3f7ababc0e454448bd9935e8","datavalue":{"value":{"entity-type":"item","numeric-id":1158768,"id":"Q1158768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$5ECFE9BB-C616-4B88-A7D6-0E2BC3F6A844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5efc810a0dab740d788edec9e4fae86bff339d58","datavalue":{"value":{"entity-type":"item","numeric-id":2081631,"id":"Q2081631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$A7DF00FF-1B9E-4ECF-96CB-ED7A15D81BB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c7692a8f217531494bd533fcebe774fe9cf5fa","datavalue":{"value":{"entity-type":"item","numeric-id":5902100,"id":"Q5902100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$777F8D81-EFD5-4B80-B9F5-E7282DD9365C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fdb8fb2279232d4e680accae8df20b670fe56c6","datavalue":{"value":{"entity-type":"item","numeric-id":1029330,"id":"Q1029330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$A913D0CD-5838-4231-8331-F708D4875879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9513ce131c0be3d8f8b0b8dbad8f9df8e3c1341a","datavalue":{"value":{"entity-type":"item","numeric-id":426896,"id":"Q426896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$A67D2A60-875D-47F8-A6EC-81A84BA6EF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b14927dcddeede2141306189b52b442cbad4d934","datavalue":{"value":{"entity-type":"item","numeric-id":2045366,"id":"Q2045366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$1E050912-7802-463D-BC4E-DB6526B0F334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3585bbaf4103bad430323a4d8ec5d8173799a2b8","datavalue":{"value":{"entity-type":"item","numeric-id":678872,"id":"Q678872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6599814$45D5CA9F-ACE8-4500-B1F8-5559B72FDA8D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1ae3e422fb3d1e59181f356cfc74f5be46d90315","datavalue":{"value":"10.46298/DMTCS.10202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6599814$EC18F5C3-3A07-45E1-B290-D3AA8DE36E1A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d67235349f9a072f26fc6f014dd967e02b60dc2e","datavalue":{"value":{"entity-type":"item","numeric-id":397075,"id":"Q397075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acbaf34c323411d4c2058cdceb29e0572d55412e","datavalue":{"value":{"amount":"+0.7267818450927734","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":"Q6599814$FC8E4D8D-D5FF-431B-AA85-B5C6A3D26C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ed7c459f18d5806aa373b5a8940497702d092a7","datavalue":{"value":{"entity-type":"item","numeric-id":3576655,"id":"Q3576655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3f19945fee903bda353f402ceed3b809297161b","datavalue":{"value":{"amount":"+0.7251293063163757","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":"Q6599814$440D678E-FA9C-4F84-856F-C373F0EC634C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00e6ce3afc9d0684ff937d790090523a5551d4e3","datavalue":{"value":{"entity-type":"item","numeric-id":2857374,"id":"Q2857374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0607fc6b8b5de4726c0b789c9f5d368df256d618","datavalue":{"value":{"amount":"+0.723031222820282","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":"Q6599814$7FBFCBB2-B86D-4E54-8553-58AEBF58552A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"665b135b99478993637f8a9ff493d0e8f2303689","datavalue":{"value":{"entity-type":"item","numeric-id":724883,"id":"Q724883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e1f59d6c94bbf64310a999eecb51ca3e1391406","datavalue":{"value":{"amount":"+0.7200757265090942","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":"Q6599814$1FA1E235-DD40-4249-A303-F50402EABDAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c0f13001bbbe3e216d6f948443f46f1eab9a701","datavalue":{"value":{"entity-type":"item","numeric-id":6657252,"id":"Q6657252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45db6dd8a9fc91282053ae8b57a312b71e9759ab","datavalue":{"value":{"amount":"+0.7184849381446838","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":"Q6599814$8D36C1FF-AE60-493D-A324-B2B82BCCAE3F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\((k-2)\\)-linear connected components in hypergraphs of rank \\(k\\)","badges":[]}}}}}