{"entities":{"Q405095":{"pageid":406862,"ns":120,"title":"Item:Q405095","lastrevid":56901966,"modified":"2026-03-24T12:59:01Z","type":"item","id":"Q405095","labels":{"en":{"language":"en","value":"Biclique covers and partitions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340117"}},"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":"Q405095$F492DC39-E536-404E-A343-980B46D8D571","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7774e06446c6d515b47ac425c5f4abdcc5d35cd6","datavalue":{"value":{"text":"Biclique covers and partitions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405095$8309CF90-6FD8-4D7B-BCD9-024B2C67D08A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c9158b2c809e8976248846b2c22f57c04cab4f31","datavalue":{"value":"1300.05259","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405095$DB334191-6F75-484B-8F36-ECEFF2AB46A3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5985c7161eebaf971375c9442b20fa04a6467c35","datavalue":{"value":{"entity-type":"item","numeric-id":405094,"id":"Q405094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$ACE7647A-A19F-4801-959C-53FDF0565EB6","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":"Q405095$C5AC3645-E19C-4738-A6C9-29A5A24A0DDD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405095$D1B91F28-8D3D-496F-A6CD-9E5E094CBA49","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"389ab2b9bcaef4acc7843ea7f395fe81aa1654a4","datavalue":{"value":"https://arxiv.org/abs/1307.6363","type":"string"},"datatype":"url"},"type":"statement","id":"Q405095$48A030D3-6F8F-4660-83B0-B23F86885845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"b11709e8d8fe22e70d4f96425cdc2e8788c70004","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p19","type":"string"},"datatype":"url"},"type":"statement","id":"Q405095$2DB7ACCD-58F8-408E-A482-F9EA62FD39F8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"02c13000f435364c42815814f5bd9de07be675d2","datavalue":{"value":"Summary: The biclique cover number (resp. biclique partition number) of a graph \\(G\\), \\(\\text{bc}(G\\)) (resp. \\(\\text{bp}(G)\\)), is the least number of bicliques -- complete bipartite subgraphs -- that are needed to cover (resp. partition) the edges of \\(G\\). {  }The local biclique cover number (resp. local biclique partition number) of a graph \\(G\\), \\(\\text{lbc}(G\\)) (resp. \\(\\text{lbp}(G)\\)), is the least \\(r\\) such that there is a cover (resp. partition) of the edges of \\(G\\) by bicliques with no vertex in more than \\(r\\) of these bicliques.{  }We show that \\(\\text{bp}(G)\\) may be bounded in terms of \\(\\text{bc}(G)\\), in particular, \\(\\text{bp}(G)\\leq \\frac{1}{2}(3^{\\text{bc(G)}}-1)\\). However, the analogous result does not hold for the local measures. Indeed, in our main result, we show that \\(\\text{lbp}(G)\\) can be arbitrarily large, even for graphs with \\(\\text{lbc}(G)=2\\). For such graphs, \\(G\\), we try to bound \\(\\text{lbp}(G)\\) in terms of additional information about biclique covers of \\(G\\). We both answer and leave open questions related to this.{  }There is a well known link between biclique covers and subcube intersection graphs. We consider the problem of finding the least \\(r(n)\\) for which every graph on \\(n\\) vertices can be represented as a subcube intersection graph in which every subcube has dimension \\(r\\). We reduce this problem to the much studied question of finding the least \\(d(n)\\) such that every graph on \\(n\\) vertices is the intersection graph of subcubes of a \\(d\\)-dimensional cube.","type":"string"},"datatype":"string"},"type":"statement","id":"Q405095$3917D123-75DC-4B8D-B6C3-013783F2675E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405095$B13F7BFC-C260-44FC-BE4D-8AFF5D153EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405095$CA31F6D9-0DC0-4BC8-B693-7F4CB247338B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405095$B16E4B45-F31B-46C4-9C7F-18038353D40D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1502afc1def229361d2c146b94df51d36be24940","datavalue":{"value":"6340117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405095$BA222432-4580-49EC-8528-E659CE796D57","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cc38f9db1c6e40b87da866d11a5121993ae1d58","datavalue":{"value":"biclique covers","type":"string"},"datatype":"string"},"type":"statement","id":"Q405095$81D8B56C-3562-4DE7-A5B9-E26FE39DEFDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f293785e99246830f7d0a5e755e045c6bad5d88f","datavalue":{"value":"biclique partitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q405095$62E7B378-626B-4F09-8AEE-58BF0A4EBF2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"291db57c690eb2e76fd517be455ad6d5a117f646","datavalue":{"value":"local biclique cover number","type":"string"},"datatype":"string"},"type":"statement","id":"Q405095$E3655BDD-9F74-4C81-8F9A-DCA150F4D6D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc8c2faac343ebe7c2f6a95cce0d46990b7302e4","datavalue":{"value":"subcube intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q405095$628F24C2-FA65-4051-9B8E-7C61791D740B","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":"Q405095$C6D31EB7-D3D4-4195-B884-294F5100C6F5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1342a438bb7a9b9f168dd8d7c25bfa01c869bae8","datavalue":{"value":{"entity-type":"item","numeric-id":5688995,"id":"Q5688995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$0C9B41E5-8579-49FB-AFFE-F6A78A293030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"962bfe016847077cfb617ffdd441f5087ad5edd8","datavalue":{"value":{"entity-type":"item","numeric-id":1147719,"id":"Q1147719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$42029CA1-15CB-443A-B22D-5182D2F602C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6969029392565414a77e71ab58c65da310d6b909","datavalue":{"value":{"entity-type":"item","numeric-id":3312268,"id":"Q3312268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$7034F39A-4617-4F76-89EC-4DE3490D4178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c7d042fc04d8db7d92afe8a7d07ba65cfa052ea","datavalue":{"value":{"entity-type":"item","numeric-id":995755,"id":"Q995755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$83FADE20-4068-4891-A919-EC82B8E15FE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$50EF1464-173F-4D0A-B52F-9383FADF37E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886af137bcb1aefe3497adcd0ccaac391e73596d","datavalue":{"value":{"entity-type":"item","numeric-id":1363672,"id":"Q1363672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$4006B835-B7E1-454E-BA5A-2DB71386BAE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"260c22fcc0b2b8fe73e22a5fc6d05d81b513177a","datavalue":{"value":{"entity-type":"item","numeric-id":1126290,"id":"Q1126290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$61784340-94EF-4D90-9D07-90F41E19835A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82a9c8cc4cdcade87b9ccc515a00403d48d4459b","datavalue":{"value":{"entity-type":"item","numeric-id":5636776,"id":"Q5636776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$EC3B8DDC-85C1-456D-B2B6-BBCA8216E73A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd6dc65c4f324da2d7c71f8d1cbf6288168abc85","datavalue":{"value":{"entity-type":"item","numeric-id":4903262,"id":"Q4903262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$9B70D5F9-B203-4CD9-AD58-8E3186EFB6FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54d41d409db7916d572e3d934d60c57870c85c6d","datavalue":{"value":{"entity-type":"item","numeric-id":3633007,"id":"Q3633007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$916F06C0-B43F-4502-A143-C107EF8D1168","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"418337ec0556b92fd1368edf814c6a838bdd6350","datavalue":{"value":{"entity-type":"item","numeric-id":1025967,"id":"Q1025967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$992BCC76-4633-4EB8-9187-F3EB207BA30E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"962af24ef35cbbdc08e38befed8abe47bf20d9f5","datavalue":{"value":{"entity-type":"item","numeric-id":5525916,"id":"Q5525916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$CD2330BF-B871-4803-9A6C-7E99EA4DEC70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ec4896edc35f1e12505542682c8c6b6145a21f0","datavalue":{"value":{"entity-type":"item","numeric-id":4875692,"id":"Q4875692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$C85CFF33-745D-4A35-88CA-E915F04A879D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c64a061b83c0d49ff35b586ccc1c30fc3af9f1","datavalue":{"value":{"entity-type":"item","numeric-id":3236503,"id":"Q3236503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$F7BB0577-5439-4E75-94E4-F21563CA42B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2df50d8783feded12a64b982501eff223d28a73c","datavalue":{"value":{"entity-type":"item","numeric-id":4231782,"id":"Q4231782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$4094A217-1CF9-4D45-866C-84F0354736C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"314cfcba4675b0a89036ae371df409e0a107d9be","datavalue":{"value":{"entity-type":"item","numeric-id":2380224,"id":"Q2380224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$EB2D0125-4E85-47E4-85BA-6D4F7E97AB24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fdf5b8cde129dad7b1f19100a2902cfe3c73387","datavalue":{"value":{"entity-type":"item","numeric-id":1252795,"id":"Q1252795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$FB239411-371A-43B6-9C4B-5A2648622B4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5389d06792c72008a023c27113ddc546a19e533f","datavalue":{"value":{"entity-type":"item","numeric-id":4354593,"id":"Q4354593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$D374DC90-DD52-4272-95E3-B101CA572ECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f17cfea272eff349cb6f6d9413633017b4480986","datavalue":{"value":{"entity-type":"item","numeric-id":802577,"id":"Q802577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$3D99F771-158A-4E80-AD77-7413F6720C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9bb36bfa8ff9b999fd22009eb922d04862e30fb","datavalue":{"value":{"entity-type":"item","numeric-id":3967567,"id":"Q3967567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405095$E34FAC1E-DD8E-4648-8AAB-2F0AE1890943","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5468b297493cbcb0890a1f9f6fdb47592e73e52b","datavalue":{"value":"bafkreiafogzbwljp74kfxkbijiexmlvwfrpbtgcgonc3jo35r3g7geln7q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405095$21A7CA8F-BB19-4681-957A-38F6896028E1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df61f54bc5902d33614d7ea3dcc12b59cd473c4e","datavalue":{"value":{"entity-type":"item","numeric-id":1734028,"id":"Q1734028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5b18a95f733ae5d4dbcc7410d2a042d197ae5f8","datavalue":{"value":{"amount":"+0.8587329387664795","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":"Q405095$C0432E88-D501-4100-A502-848844B817EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d74832bd780d87b96e963b0d41431e4c5088a5db","datavalue":{"value":{"entity-type":"item","numeric-id":2121747,"id":"Q2121747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d89183b6cbaf0379a53463722e088f80939f1afa","datavalue":{"value":{"amount":"+0.8044874668121338","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":"Q405095$36634D91-AD32-4594-85E9-9BC5CABAA5C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78c2df836b878685d6675f63d3abf090571def41","datavalue":{"value":{"entity-type":"item","numeric-id":2831584,"id":"Q2831584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cc5984c905d77d37ff5758dc1b9f1d399f2a15d","datavalue":{"value":{"amount":"+0.795781672000885","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":"Q405095$AC469CB5-7943-4356-BA1A-0A4805F3AB91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"952fa3ea4d4cf9d665aa2aa912b1ecc8a11bba15","datavalue":{"value":{"entity-type":"item","numeric-id":1019181,"id":"Q1019181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e6a7be15989a1cd2c870c47f053b70224e033ca","datavalue":{"value":{"amount":"+0.795386552810669","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":"Q405095$9E850E02-3D82-4D2B-A40B-FA51B069ED4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4d7b4700fc90b2e63c18b4f534bab2582ad81dc","datavalue":{"value":{"entity-type":"item","numeric-id":3478420,"id":"Q3478420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ef8599fd0dfc9f8428005121f551e11b4d81a76","datavalue":{"value":{"amount":"+0.792838454246521","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":"Q405095$479E986A-4686-4506-9B4B-41FE3AA3AD6F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:405095","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:405095"}}}}}