{"entities":{"Q2094882":{"pageid":2105625,"ns":120,"title":"Item:Q2094882","lastrevid":57725283,"modified":"2026-04-01T02:57:31Z","type":"item","id":"Q2094882","labels":{"en":{"language":"en","value":"Improved bounds on a generalization of Tuza's conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7613669"}},"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":"Q2094882$537D0CC6-31F6-4F76-8C18-E2091BC58994","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9641e12ea03e9cad1e4a4461e1e01467ee338765","datavalue":{"value":{"text":"Improved bounds on a generalization of Tuza's conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2094882$CA911FAF-AA9C-4078-92DE-BA4886DDBDF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"db0997a2251a086420513724aef27885de62987e","datavalue":{"value":"1503.05094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$39B98F26-9FB6-4294-86A7-0A0111EF9C37","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c8ad43d619e42882bab0531d6f5d120919947ba","datavalue":{"value":"10.37236/10829","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$880127C3-C313-4B57-B4C6-3FBF09B1310C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$1CE29E90-66FF-4D27-9FC4-F90E87F33681","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":"Q2094882$09E2B17A-5097-4253-9F8B-DD626E52E541","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41c2d4b2b9eee3d1d4724659108ff6928154d594","datavalue":{"value":{"time":"+2022-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2094882$3F236FFC-FC88-4ED0-A8AD-0A48C3082AA5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bc0a80a322b3d977fd546abb42b44965bd3fa3b4","datavalue":{"value":"https://arxiv.org/abs/2110.10095","type":"string"},"datatype":"url"},"type":"statement","id":"Q2094882$D1A9A0A6-B53E-4335-89FA-0B210A4FC782","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"79eea85e3316aab239125c773b2021645b8abd96","datavalue":{"value":"Summary: For an \\(r\\)-uniform hypergraph \\(H\\), let \\(\\nu^{(m)}(H)\\) denote the maximum size of a set \\(M\\) of edges in \\(H\\) such that every two edges in \\(M\\) intersect in less than \\(m\\) vertices, and let \\(\\tau^{(m)}(H)\\) denote the minimum size of a collection \\(C\\) of \\(m\\)-sets of vertices such that every edge in \\(H\\) contains an element of \\(C\\). The fractional analogues of these parameters are denoted by \\(\\nu^{\\ast(m)}(H)\\) and \\(\\tau^{\\ast(m)}(H)\\), respectively. Generalizing a famous conjecture of \\textit{Z. Tuza} [Graphs Comb. 6, No. 4, 373--380 (1990; Zbl 0724.05059)] on covering triangles in a graph, \\textit{R. Aharoni} and \\textit{S. Zerbib} [J. Graph Theory 94, No. 3, 445--462 (2020; Zbl 1485.05077)] conjectured that for every \\(r\\)-uniform hypergraph \\(H, \\tau^{(r-1)}(H)/\\nu^{(r-1)}(H) \\leqslant \\lceil{\\frac{r+1}{2}}\\rceil \\). In this paper we prove bounds on the ratio between the parameters \\(\\tau^{(m)}\\) and \\(\\nu^{(m)}\\), and their fractional analogues. Our main result is that, for every \\(r\\)-uniform hypergraph \\(H\\), \\[\\tau^{\\ast(r-1)}(H)/\\nu^{(r-1)}(H)\\leqslant \\begin{cases}\\frac{3}{4}r-\\frac{r}{4(r+1)}\\,\\,\\text{for}\\,\\, r\\,\\,\\text{even}, \\\\ \\frac{3}{4}r-\\frac{r}{4(r+2)}\\,\\,\\text{for}\\,\\, r\\,\\,\\text{odd}. \\end{cases} \\] This improves the known bound of \\(r-1\\). We also prove that, for every \\(r\\)-uniform hypergraph \\(H\\), \\(\\tau^{(m)}(H)/\\nu^{\\ast(m)}(H) \\leqslant \\operatorname{ex}_m(r, m+1)\\), where the Tur\u00e1n number \\(\\operatorname{ex}_r(n, k)\\) is the maximum number of edges in an \\(r\\)-uniform hypergraph on \\(n\\) vertices that does not contain a copy of the complete \\(r\\)-uniform hypergraph on \\(k\\) vertices. Finally, we prove further bounds in the special cases \\((r,m)=(4,2)\\) and \\((r,m)=(4,3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094882$B418D3BB-DD60-43F1-8CE8-CAD792993FEA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$864FE4CA-A0E3-4A12-BA2D-A65F76B43E62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$7B2F49B0-3EAE-4968-ACA4-1D5AFCD050A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$42DD217A-615B-4C92-9285-15FAC6E36397","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"23a83225cfbf376001d3060f1d04da21b7dd41fc","datavalue":{"value":"7613669","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$88264736-11A2-465B-B1A0-F29A84C055F4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fc6d24812670ab234e441a881881c607b2f5852","datavalue":{"value":"covering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094882$9B2092FF-C0CB-4FAA-898B-C62045ECF448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"935a1e4392411598666fb8b7b6967cac971329f3","datavalue":{"value":"\\(r\\)-uniform hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094882$04046CDD-DD12-44FF-9A0C-EA0563FC445A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"cc71de58cf49d5d5bab04d4b9a7b7497c30a2d54","datavalue":{"value":"Q123230781","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$A8DD445F-0E97-4FAA-AB14-38E6E0400B93","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":"Q2094882$20B0F529-8CC0-47C4-AA2F-18DF29E98DFE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c455bed359f20895bf75083ce8568c5e5f65398c","datavalue":{"value":"W3205324233","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$EEFA65EE-12B2-4950-AD3B-4533A654D239","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0dac66412f512eccdf0fac61b9b6eb6cb3aa1f6","datavalue":{"value":{"entity-type":"item","numeric-id":5066897,"id":"Q5066897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$4CC93B45-DBB3-403C-9778-3E5B93A7AAF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2061d359752f6d08cabbe8c88a6d5764fcc7bc09","datavalue":{"value":{"entity-type":"item","numeric-id":4413572,"id":"Q4413572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$C8C317CD-175C-4967-B6A5-D14B55AE9B74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7c2f3b97f741405855bdd4377a208f1592816f0","datavalue":{"value":{"entity-type":"item","numeric-id":1304632,"id":"Q1304632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$8D71EEC2-C2EE-498C-9B9B-D02A4C2BE66D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c52d08209d30f8fdaf90ef458e8872659f33a659","datavalue":{"value":{"entity-type":"item","numeric-id":1065822,"id":"Q1065822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$7462A176-F1E1-499C-BD76-54F01D2DA048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5670f34f7f97e1f73ed327c2ad2e07b09b07d505","datavalue":{"value":{"entity-type":"item","numeric-id":1168988,"id":"Q1168988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$BE8BD59B-8A74-4BFF-850E-9128843F33F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1c7a59309da8d55110d89d8f09f3f27182b8166","datavalue":{"value":{"entity-type":"item","numeric-id":1296990,"id":"Q1296990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$31BC584D-12CE-49E1-8E8B-89C0697B3D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d697550d37ae21605b9d83f20769b433b90c36bd","datavalue":{"value":{"entity-type":"item","numeric-id":412272,"id":"Q412272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$4AAD6D5F-C76A-47CA-8851-9F09AA167F11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d866171feaee30f5f3fb82d727fc7a09b46fff1","datavalue":{"value":{"entity-type":"item","numeric-id":3089368,"id":"Q3089368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$7204FE5B-0A06-4500-A1BB-02B5E3AA7657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"584405ef177399c83c85401af6d2adebebda204a","datavalue":{"value":{"entity-type":"item","numeric-id":1896363,"id":"Q1896363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$FC00CABD-8107-4BF3-87A3-B8D566B832E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dde0102abc44f910a2066e8b6a2996bfaa05fb8b","datavalue":{"value":{"entity-type":"item","numeric-id":4060999,"id":"Q4060999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$3FBECF2A-DE36-4417-A7D1-5B06951CF00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f3ee0aae57c733a5877e651aada74e85d736f9","datavalue":{"value":{"entity-type":"item","numeric-id":1044999,"id":"Q1044999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$83899861-30D9-468D-9596-A04FC215CFD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e74f6c2e844aad1e90d6fc6480dae778b9ccabc0","datavalue":{"value":{"entity-type":"item","numeric-id":1051653,"id":"Q1051653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$9C6913C7-EA76-4876-87A0-8139565F27C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43418a58973bef401867b47368b5b83e0621f33","datavalue":{"value":{"entity-type":"item","numeric-id":5961541,"id":"Q5961541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$C8AF6BEB-0D82-4323-92E9-163B8434BDA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16551f729343fd783a5b4df128ff48ebd493ca6b","datavalue":{"value":{"entity-type":"item","numeric-id":2409540,"id":"Q2409540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$1D49EA02-396C-4485-9B10-A6C74AC5010D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe979badcb8bfb7a41b5de5f764eb66747617dd","datavalue":{"value":{"entity-type":"item","numeric-id":5781249,"id":"Q5781249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$21916191-1BF9-4BD0-A619-8BF699138472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a577bb43dc8225a677b2200e99cb448f777ba629","datavalue":{"value":{"entity-type":"item","numeric-id":2276982,"id":"Q2276982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$30027293-8B55-4F66-96EB-94E47FF8242C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"bcf10d9c25f7f7f55469c5d5f4838df636775300","datavalue":{"value":"bafkreicgghscneqas5uxd36y2bg3icwxrdeckg52aopgjuhufzimdwqoua","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094882$F798A93B-3767-4C4C-9D67-B8FC017A93C1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df0d4b7708bf21f5dcb6cfd33dc7ef4358277bae","datavalue":{"value":{"entity-type":"item","numeric-id":5066897,"id":"Q5066897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab4a31ce2f2cea699947693ef4fa5686b989ab6b","datavalue":{"value":{"amount":"+0.9136930108070374","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":"Q2094882$7012C86A-328F-4D46-BC84-D4D3E315321E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd5e2d40e69a19f2da479af37c099707588132bb","datavalue":{"value":{"entity-type":"item","numeric-id":499465,"id":"Q499465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee5e0e6f313c054517f2247b942d72c32478cf75","datavalue":{"value":{"amount":"+0.8027154803276062","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":"Q2094882$1CEE4E68-FA6A-48EE-BF9B-6EC6F8F262EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"197795d432e1ae2ac3750ad8c125ee9295e88d09","datavalue":{"value":{"entity-type":"item","numeric-id":1850546,"id":"Q1850546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7610b32ba0f22d4cd9cdd891b8965f82ae5a070","datavalue":{"value":{"amount":"+0.8001320362091064","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":"Q2094882$FE068FE2-FE7B-4CDE-A56D-5E53EC98D7AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84ceab447840ccef8b806e0d861cbdc05a3f4f63","datavalue":{"value":{"entity-type":"item","numeric-id":1813713,"id":"Q1813713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"223783cd263d116706103fe4fbc1b6a53ece97a1","datavalue":{"value":{"amount":"+0.7987233996391296","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":"Q2094882$D3258CA5-19A5-4839-B106-8D0EDC2B497B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16cb4d93facfcf46950576738e3b32d406693555","datavalue":{"value":{"entity-type":"item","numeric-id":3147240,"id":"Q3147240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85fdd72ecf7fdb2540bbd7154299173f125cb681","datavalue":{"value":{"amount":"+0.7973955869674683","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":"Q2094882$2F4A5CD3-2C2E-468D-AE9F-B72F31D98035","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094882$ABA4E5A8-44F5-4E4B-86FE-08F244AB8D74","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2094882","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2094882"}}}}}