{"entities":{"Q1010905":{"pageid":1012753,"ns":120,"title":"Item:Q1010905","lastrevid":57327147,"modified":"2026-03-30T12:37:21Z","type":"item","id":"Q1010905","labels":{"en":{"language":"en","value":"Lower bounds for the size of random maximal \\(H\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5541069"}},"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":"Q1010905$CE3A9B90-6A4A-421D-A1BC-33F5A5D7B87F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3b3fe84122249b0693af8fe4af1e51f38216355b","datavalue":{"value":{"text":"Lower bounds for the size of random maximal \\(H\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010905$28109C47-58C4-4F88-A458-9060DD2082C5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09d447de8d75537bd24f1f9668e9c019a484b97d","datavalue":{"value":"1178.05088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010905$6256ADFD-B071-4B76-AB5D-EF66DA2715E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f0bfcc04ce9a1e257b6d03aae2e630c85fa34e2","datavalue":{"value":{"entity-type":"item","numeric-id":410734,"id":"Q410734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010905$83DD725E-706A-405A-B358-9D6238FEF24A","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":"Q1010905$9856CDDB-0568-4649-A7DD-42A56F707A9E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010905$E3ECE861-4E51-44E6-AFE8-FD917CEF4D75","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c80a5371dd49a6e88a7cbfdae414559ec18d42d7","datavalue":{"value":"https://arxiv.org/abs/0805.1747","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010905$A4C34F4A-C727-433B-8D30-B26905F3778F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c0ef438b7e2e0d8e4bf4848f79d50135e3a557ef","datavalue":{"value":"https://eudml.org/doc/117290","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010905$B38C5DBB-906D-47D4-BE4E-BEAAB5FEAD61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"63ad6cd77bafe2765b6b3be9fef47121c4131027","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r4.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010905$BBD9971D-5518-403D-AD87-39960A76BCB0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"474c4853b8713a07b764b2d3b0bac9b723848a51","datavalue":{"value":"Summary: We consider the following random process for generating a maximal \\(H\\)-free graph: Given a fixed graph \\(H\\) and an integer \\(n\\), start by taking a uniformly random permutation of the edges of the complete \\(n\\)-vertex graph \\(K_n\\). Then, traverse the edges of \\(K_n\\) according to the order imposed by the permutation and add each traversed edge to an (initially empty) evolving \\(n\\)-vertex graph - unless its addition creates a copy of \\(H\\). The result of this process is a maximal \\(H\\)-free graph \\({\\mathbb M}_n(H)\\). [This process was introduced by \\textit{P.Erd\u0151s}, \\textit{S. Suen}, and {P. Winkler}, ``On the size of a random maximal graph'', Random Struct. Algorithms 6, No.\\,2-3, 309--318 (1995; Zbl 0820.05054).]    Our main result is a new lower bound on the expected number of edges in \\({\\mathbb M}_n(H)\\), for \\(H\\) that is regular, strictly 2-balanced. As a corollary, we obtain new lower bounds for Tur\u00e1n numbers of complete, balanced bipartite graphs. Namely, for fixed \\(r \\geq 5\\), we show that ex\\((n, K_{r,r}) = \\Omega(n^{2-2/(r+1)}(\\ln\\ln n)^{1/(r^2-1)})\\). This improves an old lower bound of \\textit{P. Erd\u0151s} and \\textit{J. Spencer} [Probabilistic methods in combinatorics, Budapest: Akademiai Kiado (1974; Zbl 0308.05001)]. Our result relies on giving a non-trivial lower bound on the probability that a given edge is included in \\({\\mathbb M}_n(H)\\), conditioned on the event that the edge is traversed relatively (but not trivially) early during the process.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010905$4B1478F9-BEEA-4600-B5FB-0107A36A7762","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010905$0C096F47-F09D-4889-873D-E3FD1FC6186F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010905$B1394BB9-818B-4C29-AC85-FB99B582A6A9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"59634bef2c0574bf6cc40cce05cbf56a38454a5d","datavalue":{"value":"5541069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010905$6CEBFBD0-0196-459D-91E7-D429134FB799","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":"Q1010905$449A6719-B172-47B9-A17B-835DDA3F45A2","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c0dad6be7d14efda445361644a93cf8f7d90ff94","datavalue":{"value":"bafkreihpexyv55ckf3av4dlpwfvnauutreevrzog25ewolrc6qgx4pu2hm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010905$C7C9753E-AF6B-4FEB-A1E1-34E0542534EE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b57ed7537636c4e2ec0ae90e0f9c267cc1abc6f7","datavalue":{"value":{"entity-type":"item","numeric-id":982189,"id":"Q982189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a92681e2c42c0f6d9f3b6abf4bb821a342a3ca65","datavalue":{"value":{"amount":"+0.8796800971031189","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":"Q1010905$7D7C4E3F-68BD-49B7-A42A-4993A4E7D86A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bf475cd45e40369141895556b1a21b9505740e3","datavalue":{"value":{"entity-type":"item","numeric-id":4761358,"id":"Q4761358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcb607c0075862034376e8ce7ab39d56ebb4bd86","datavalue":{"value":{"amount":"+0.8568097949028015","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":"Q1010905$BDF8C61A-810D-4341-89DD-39125BE85D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6364f00c3d3b057e8d1087c4e59f796a2255e3ef","datavalue":{"value":{"entity-type":"item","numeric-id":1023043,"id":"Q1023043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d38326874be22f575eed0e79b60c003f143eb435","datavalue":{"value":{"amount":"+0.8091652989387512","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":"Q1010905$CB132EA3-2A26-4AF8-AEA0-C138E295B657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bae4f75f810c8c1f013d06d6e2b9179ae8b0981","datavalue":{"value":{"entity-type":"item","numeric-id":5251206,"id":"Q5251206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f2c745762e300cf46a84b887cf2b5592a359194","datavalue":{"value":{"amount":"+0.7893410325050354","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":"Q1010905$CF31A58B-83EF-409B-8874-65AEC3BFEC2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d95de73e1562f212c4ec701900a42100aa0d385","datavalue":{"value":{"entity-type":"item","numeric-id":409409,"id":"Q409409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"add1607ee5cda7aef899563d0e4ca3ee9abec457","datavalue":{"value":{"amount":"+0.7886387705802917","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":"Q1010905$5124FB32-EA04-4E45-9C1E-9771C921D0E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1010905","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1010905"}}}}}