{"entities":{"Q653990":{"pageid":655839,"ns":120,"title":"Item:Q653990","lastrevid":51389543,"modified":"2026-01-18T01:18:54Z","type":"item","id":"Q653990","labels":{"en":{"language":"en","value":"The number of \\(K_{m,m}\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990947"}},"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":"Q653990$C3280E8A-88B2-4509-8D38-7F8515F59AA2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a659679e159975265b859874f6678ea355ee3293","datavalue":{"value":{"text":"The number of \\(K_{m,m}\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q653990$6D457E37-D1DD-4B65-A36F-55C447989034","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1ac95a84d6ac4694a8dc952a68c493102f1f6937","datavalue":{"value":"1249.05190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$881D4F3A-F081-452F-82FF-9996AABFA301","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9158385d8dfa25fd1cbf34c726849285f5355cf","datavalue":{"value":{"entity-type":"item","numeric-id":189372,"id":"Q189372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$83ACB5E5-E422-4F87-8414-976B800E6ADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8013bc00783240c57786649bc43e422121684be","datavalue":{"value":{"entity-type":"item","numeric-id":285062,"id":"Q285062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$6593E383-3C5F-4FEB-B120-4BCB4C86EE24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$A8A32524-25F9-4A16-983A-79B551A40F16","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e9a9ebdc8bdc44c407c473bf89fbe244ce057f32","datavalue":{"value":{"time":"+2011-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q653990$FD220633-55C0-4F26-97BA-04319A11457B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"74f886c72fc92f3f9d30f7f287871707810e4df5","datavalue":{"value":"For any forbidden subgraph \\(H\\), the authors denote by \\(f_n(H)\\) the number of labelled \\(H\\)-free graphs on \\(n\\) vertices; this is the \\(F_n(H)\\) of \\textit{P. Erd\u0151s, P. Frankl} and \\textit{V. R\u00f6dl} [``The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent,'' Graphs Comb. 2, 113--121 (1986; Zbl 0593.05038)]. In Theorem 1.6 of the cited paper it was proved that, when \\(\\chi(H) \\geq 3\\), \\(\\log_2\\left(f_n(H)\\right) =\\text{ex}(n,H)\\cdot(1+{\\text o}(1))\\) as \\(n\\to\\infty\\), and conjectured that the same result should hold also when \\(\\chi(H)=2\\). For complete bipartite graphs whose parts have the same size the present authors prove (Theorem 1.2):  \\[ \\log_2\\left(f_n\\left(K_{m,m}\\right)\\right) \\leq(1+{\\text o}(1))\\cdot\\frac{m(m-1)^\\frac1m}{2m-1}\\cdot C_m\\cdot n^{2-\\frac1m},  \\text{ as }n\\to\\infty, \\]   \\[ \\text{where }C_m=\\sup_{x\\in(0,1)}\\left\\{x^{-1+\\frac1m}\\cdot\\left(-x\\log_2x-(1-x)\\log_2(1-x)\\right)\\right\\}. \\]  They also address a conjecture of \\textit{P. E. Haxell}, \\textit{Y. Kohayakawa} and \\textit{T. \u0141uczak} [``Tur\u00e1n's extremal problem in random graphs: Forbidding even cycles,'' J. Comb. Theory, Ser. B 64, No.\\,2, 273--287 (1995; Zbl 0828.05056)]. The authors report that, subsequent to submission of the present paper, they have, in \\textit{J. Balogh} and \\textit{W. Samotij} [``The number of \\(K_{s,t}\\)-free graphs,'' J. Lond. Math. Soc., II. Ser. 83, 368--388 (2011; Zbl 1227.05170)], generalized their results to complete bipartite graphs \\(K_{s,t}\\) where \\(2 \\leq s \\leq t\\) .","type":"string"},"datatype":"string"},"type":"statement","id":"Q653990$C96D9068-CB95-4C7F-AD9A-B7279DC1A772","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$0FEF5D25-719B-4390-96DF-BF18C8359BF8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$C40527F7-5D0C-45D8-A848-E275B1FA6143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$EE5731B7-6FAD-49A9-845C-FF188AA67AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$8A681BC7-C506-48BE-8F50-AD6709CD2FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$9774B0A5-FE75-4876-A00A-34941A8CB2E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$0AFAFBEC-1663-4BBA-8E70-FCFAD11144AC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8be59fe79b4e04f5ec749436889581d90eba5d6e","datavalue":{"value":"5990947","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$94246E2C-4F1C-4B05-9E7F-7A9C806E8EA3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a884d7316fe6861d2b1f9894781f1a6ada8d8719","datavalue":{"value":"\\(K_{m,m}\\)-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q653990$ABFE62B7-3F6F-4AE3-8D98-CD63787ED75A","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":"Q653990$327E321E-9202-448D-AD61-B8A35BDD2D55","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a160901408917d70c1540cd9ea816c89aa6e67e8","datavalue":{"value":"https://doi.org/10.1007/s00493-011-2610-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q653990$FC3CB2F5-C650-41F0-B67D-516E7D19D99D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"268a130fef53ab21b8daa5de3f46e9513faf509f","datavalue":{"value":"W988817357","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$9A307DDB-0301-4509-8682-A95219A952E7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"98677fbb9529997bece218a56a0b173d3b586128","datavalue":{"value":{"entity-type":"item","numeric-id":631642,"id":"Q631642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$9072E7FD-154B-47A6-A544-DE2EDE2A683B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a355ea13c3ed372b34436d05518ee3ae9aa00744","datavalue":{"value":{"entity-type":"item","numeric-id":1826950,"id":"Q1826950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$AAF2F5C3-3E77-4114-A480-4FC2370B2D5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b019a379fc01faedb5cf672f77fc7c9024f49de1","datavalue":{"value":{"entity-type":"item","numeric-id":3633015,"id":"Q3633015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$451B2E79-BF08-4FD1-9BF6-CA6D6D8457AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4abb591e2821a070c3f5f1804c8e042255b8fbb5","datavalue":{"value":{"entity-type":"item","numeric-id":3008023,"id":"Q3008023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$8DF8FD8C-AF70-4674-B086-2B056459D28B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8402909d7c243f063788852ea31591eef8f9b30","datavalue":{"value":{"entity-type":"item","numeric-id":5392190,"id":"Q5392190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$8B53B08C-9CE8-411A-B9C6-CC2BB7DBC140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87fa7aaad816c3dd2f710e6967960077a3508ab7","datavalue":{"value":{"entity-type":"item","numeric-id":3972139,"id":"Q3972139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$9C31A8E6-E35F-4D5A-9097-7968E006CD9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"344f697a74f08c27dbfe2d6124ad1eb1876a2d05","datavalue":{"value":{"entity-type":"item","numeric-id":5567713,"id":"Q5567713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$B6C52AE1-3AD0-4676-8905-F18AA9D17EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d4b8048f6210c471ad38d88b52197aa2bd692d2","datavalue":{"value":{"entity-type":"item","numeric-id":4337503,"id":"Q4337503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$2C9B9F03-B93B-4A20-BD63-826AE0337F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6e580263632d711d06d8abc330a8825dcebd83a","datavalue":{"value":{"entity-type":"item","numeric-id":350550,"id":"Q350550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$064EF7BC-38F1-4199-9662-C5C6DA3FE01E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"345c41968f3aeebd152e751368a44b16d079dc5f","datavalue":{"value":{"entity-type":"item","numeric-id":1076037,"id":"Q1076037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$FF32215E-6421-4673-A526-5DC0749C73CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b79004eec82002fc898d57feecbac5016d092acd","datavalue":{"value":{"entity-type":"item","numeric-id":5842850,"id":"Q5842850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$F0D0F741-EA0E-410D-A129-C0367216414E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"926e901fda1d453e47538fe39c14ad844730359c","datavalue":{"value":{"entity-type":"item","numeric-id":1318835,"id":"Q1318835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$129E42B7-E164-4C02-A709-481F6EFA6BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"182f8f862b2f8bc639de168e9a5175cac01ece4a","datavalue":{"value":{"entity-type":"item","numeric-id":4883060,"id":"Q4883060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$CC63E3A9-AEAF-4F91-AE5E-8F19774073C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32bed574c88f34cd7ad5d941a2626c0b0c13e475","datavalue":{"value":{"entity-type":"item","numeric-id":1898722,"id":"Q1898722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$4E079D48-1A9B-43E0-BF46-47D145AE171E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b9ad0745eeb1a5992c2ac50f85cc1c770cf4302","datavalue":{"value":{"entity-type":"item","numeric-id":1167182,"id":"Q1167182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$9B045913-B1A7-4DA5-9ABF-E7593D91D504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d7b148514aa4b4dcacad6368bf9e1aff70768ef","datavalue":{"value":{"entity-type":"item","numeric-id":1280282,"id":"Q1280282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$CDCA8D83-E97E-462F-A22F-59C83E38B5B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8603e95a59637f07853abdfa96637d0cfbb1d082","datavalue":{"value":{"entity-type":"item","numeric-id":3781776,"id":"Q3781776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$12410962-B1CC-47F4-B821-E7089A15E33A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82ba3bd74ef41e0757015be3b53bca7ad9cb71ba","datavalue":{"value":{"entity-type":"item","numeric-id":5463630,"id":"Q5463630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$13A98164-B305-4A6F-8E64-BF01480EAE7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33597eb53d35de713b7f13306e07cf0a7a5da5c8","datavalue":{"value":{"entity-type":"item","numeric-id":5931454,"id":"Q5931454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$C6E36DC0-C5A0-497A-9298-CE690C188472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"927a3ac6f2c906b6c110feac716962be0d7e3374","datavalue":{"value":{"entity-type":"item","numeric-id":350549,"id":"Q350549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653990$AD428F34-BBDD-4A74-A628-14C5DA7B195B","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":"Q653990$FEE731A4-778C-4238-9353-1413904625B2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d286c2ca057931b56e56aa6df1d8d56e43964e4f","datavalue":{"value":"10.1007/S00493-011-2610-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653990$C1A77309-9B21-4869-B47E-AB1849E03573","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0cf3d2ed42a03200a2e1fc56170024bee4ecdad","datavalue":{"value":{"entity-type":"item","numeric-id":5392190,"id":"Q5392190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3993f648127fdaa3104c5f0e5e4db36e919a6faf","datavalue":{"value":{"amount":"+0.8510015606880188","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":"Q653990$8070B804-3BE6-4261-A3EF-CB306C8AB91E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff8bbef1351c54dcf48ec441a81a89db145faff2","datavalue":{"value":{"entity-type":"item","numeric-id":4133658,"id":"Q4133658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"976e9e2874e5a9f2535a084deeae67250c5b512b","datavalue":{"value":{"amount":"+0.8263002634048462","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":"Q653990$6893F722-6642-4AD7-804A-4F87AD7D406A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4b72d256598ce55ab6a7089c368731d9771a3ed","datavalue":{"value":{"entity-type":"item","numeric-id":3137178,"id":"Q3137178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9993ce700d09a03b69e085b3e19a5d680a8df59f","datavalue":{"value":{"amount":"+0.8063676953315735","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":"Q653990$57B78948-0AF0-4A17-B606-4E4B1435B9DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"526082f3887f6bd83f08b97879acad332d40dd61","datavalue":{"value":{"entity-type":"item","numeric-id":710718,"id":"Q710718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9993ce700d09a03b69e085b3e19a5d680a8df59f","datavalue":{"value":{"amount":"+0.8063676953315735","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":"Q653990$051A5BFF-4CC3-42AA-A55E-94E5507DE3DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5fc1ba6e4ecb236ca34ac589d9e25df10f3e428","datavalue":{"value":{"entity-type":"item","numeric-id":4975587,"id":"Q4975587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3c67c9bcad57a8b94099f82a8b2b3e9e32e78e7","datavalue":{"value":{"amount":"+0.8053858876228333","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":"Q653990$E2AE846B-2D54-44BC-9DDF-0667FF5EB23F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:653990","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:653990"}}}}}