{"entities":{"Q1576569":{"pageid":1587309,"ns":120,"title":"Item:Q1576569","lastrevid":67911459,"modified":"2026-04-12T20:09:45Z","type":"item","id":"Q1576569","labels":{"en":{"language":"en","value":"How tight is the Bollob\u00e1s-Koml\u00f3s conjecture?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1491656"}},"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":"Q1576569$A741C7FD-C7C3-4684-A2AB-6A870E9799CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5363b770712d015479105fec14765c3f0a1ebbb7","datavalue":{"value":{"text":"How tight is the Bollob\u00e1s-Koml\u00f3s conjecture?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1576569$1A3D6D17-9A04-4AE4-B165-12F4C1E75151","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"28f3abeb539b6ea330b00ce3d7e3869277ff6fb4","datavalue":{"value":"0961.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1576569$A8B235FE-88CE-459B-A706-2814FE233F2C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab18d1e448edc056b23e686ba29743caa5b24e99","datavalue":{"value":{"entity-type":"item","numeric-id":290229,"id":"Q290229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1576569$4CDE1B0F-74E9-47F8-A08B-4C9DB2B8DC8B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1576569$F2760264-004E-4DB1-BE90-F084CCD1C056","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1197f4709d23e03f650c941d8cf07bc927e0c1a9","datavalue":{"value":{"time":"+2001-05-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1576569$D11756A9-34CA-4F7F-8F30-BF5B603620E7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c06053efdd644a2b5a14e3c31d8497466c9ddc24","datavalue":{"value":"The bipartite case of the Bollob\u00e1s-Koml\u00f3s conjecture states that for every \\(\\Delta_0\\), \\(r>0\\) there is an \\(\\alpha= \\alpha(\\Delta_0, r)> 0\\) such that the following statement holds: If \\(G\\) is any graph with minimum degree at least \\({n\\over 2}+ rn\\), then \\(G\\) contains as subgraphs all \\(n\\) vertex bipartite graphs, \\(H\\), satisfying \\(\\Delta(H)\\leq\\Delta_0\\) and \\(b(H)\\leq \\alpha n\\). Here \\(b(H)\\), the bandwidth of \\(H\\), is the smallest \\(b\\) such that the vertices of \\(H\\) can be ordered as \\(v_1,v_2,\\dots, v_n\\) such that \\(v_i\\sim_Hv_j\\) implies \\(|i-j|\\leq b\\).   This conjecture has been proved by the author in the submitted paper ``Embedding low bandwidth bipartite graphs.'' The author proves the following theorem: For any \\(0< r\\leq{1\\over 100}\\) there is a \\(\\Delta_0\\) such that following statement holds for infinitely many \\(n\\): there is a graph \\(\\text{BK}_{n,r}\\) on \\(n\\) vertices with minimum degree at least \\({n\\over 2}+ rn\\) and a bipartite graph, \\(H\\), on \\(n\\) vertices with \\(\\Delta(H)\\leq \\Delta_0\\) and \\(b(H)< 4rn\\). Yet \\(H\\) is not a subgraph of \\(\\text{BK}_{n,r}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1576569$EC282088-AE04-458E-8542-997644FBF7EB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1576569$6B0E7030-18F3-43B5-B3B3-00E0C7A90C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1576569$1A245BAC-4874-4B5C-A285-D2C821526A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1576569$6D1D1F41-BCB1-459C-A685-8D675F7A0DCF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"64bd621e9a9a1f21ff7259ac77965fe6ec171470","datavalue":{"value":"1491656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1576569$B0C6B955-23E1-402E-BAFF-8B92E608A664","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d68605bf297e6c7b30c24c24a8124af057eda451","datavalue":{"value":"Bollob\u00e1s-Koml\u00f3s conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1576569$ED0FA311-B721-4094-827A-BA6EB4481F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72494967642b9ea1b87091d53eb77ad552577f43","datavalue":{"value":"bandwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1576569$C3685CF2-02C0-4095-A8FF-16B476B3046B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4357779dcf19cdb89d5a6057aa8d0856859559aa","datavalue":{"value":{"entity-type":"item","numeric-id":218263,"id":"Q218263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1576569$E84B44AD-027B-4165-B939-D9B242561220","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":"Q1576569$C380DBE5-2254-400E-B9D8-2880E0D6193D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb8c1d2f3222ba66108d78c4bd808d1880a9bb3a","datavalue":{"value":{"entity-type":"item","numeric-id":957895,"id":"Q957895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec81b26afd9e9e3d510e9c2635924bc298fe6447","datavalue":{"value":{"amount":"+0.8896229863166809","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":"Q1576569$04BDDB79-D95C-4D4A-9840-8FE65A6B8234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fea3d92395398c2c1cf397aad96cf0de299dbd4","datavalue":{"value":{"entity-type":"item","numeric-id":3503507,"id":"Q3503507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"085628ed9d1072690102edd498ec5d6ebd4c66b5","datavalue":{"value":{"amount":"+0.8679070472717285","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":"Q1576569$F26DE618-E3C3-45D7-A439-E5287E1C93EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"150febe59808a02c0258e6e667df1fd15bd417d2","datavalue":{"value":{"entity-type":"item","numeric-id":3013126,"id":"Q3013126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"410f9725d25c1fe7462cc4429d5499d5c13fac6c","datavalue":{"value":{"amount":"+0.8333108425140381","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":"Q1576569$9E93BE2E-3DFA-437B-A658-B7F5057A78A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dae8d52225d084992f10e885c98e855a09bb0f0d","datavalue":{"value":{"entity-type":"item","numeric-id":4903263,"id":"Q4903263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b9f5d1028264ff368385bfdded94bcb5fad7900","datavalue":{"value":{"amount":"+0.8283603191375732","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":"Q1576569$29590150-AA7D-4F42-9B98-CC6A083021A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ab8d2f844ae82d59bc75d628cd66143679c0763","datavalue":{"value":{"entity-type":"item","numeric-id":2934645,"id":"Q2934645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"358d12abf041d9daac311c41e43e9166e38409b9","datavalue":{"value":{"amount":"+0.8256439566612244","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":"Q1576569$FE91EF1A-F6BF-49EB-9FF3-D11073BD2A1A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"How tight is the Bollob\u00e1s-Koml\u00f3s conjecture?","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/How_tight_is_the_Bollob%C3%A1s-Koml%C3%B3s_conjecture%3F"}}}}}