{"entities":{"Q2722658":{"pageid":2733397,"ns":120,"title":"Item:Q2722658","lastrevid":41930169,"modified":"2025-05-16T13:29:06Z","type":"item","id":"Q2722658","labels":{"en":{"language":"en","value":"A large deviation result on the number of small subgraphs of a random graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1613338"}},"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":"Q2722658$7FF36071-17D4-433F-A116-91FF5B384B83","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eb2a7ae1cfa777412f88df03fb41240ea852ef44","datavalue":{"value":"0982.05092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2722658$C0533723-CD0C-44B5-AA2C-52860E27E0C5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf218fae682d40d66951fcb7e258d179f09cc5eb","datavalue":{"value":"10.1017/S0963548399004095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2722658$1BE7215C-B0C1-480B-997E-39BF1530365E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ac20003147c5e8ffc37ced247b8446bd4defdc1","datavalue":{"value":{"entity-type":"item","numeric-id":178484,"id":"Q178484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2722658$CE00F508-B06E-4779-B526-48588AAF4EA0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc98aa839a361f8a72b00376d60e99225cffa57","datavalue":{"value":{"entity-type":"item","numeric-id":2703019,"id":"Q2703019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2722658$ADA0A55C-B3FE-49DB-B34C-C24B7CDD2B6D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d523614f519ec0feabed1eeb5eb67171dc8b190","datavalue":{"value":{"time":"+2002-03-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2722658$1A2AC5AF-4D92-4083-AF3D-06F1B7F653B8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2722658$260218AD-96E7-4921-BB00-224013D2615D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2722658$FFDAC4D2-695D-4368-B630-6C9974CC3C82","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e264fec57a47313c9c57c9a24681f13c00e7b78","datavalue":{"value":"1613338","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2722658$3A31FDEA-CF37-4556-B37D-C6BA8E271FFC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98240ea97fd3fa9f339aeab1e6b7922bef3e8fba","datavalue":{"value":"density of a subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2722658$EADB86F2-1912-4E96-867C-5291994C1198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"381d86d27f9c50be79c3a10ac82e16377544a9d0","datavalue":{"value":"balanced graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2722658$D00FDC09-2FB6-44CA-9CB6-D9F537F341CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72f4b01f25cd1d63e30141b34aa4c233ed314405","datavalue":{"value":"large deviations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2722658$7853C3A5-7421-44AF-9B15-6BF089B40AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ab6f75c4081c16792868d3a0a53478dcbf0fbde","datavalue":{"value":"fractional independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2722658$6DB54D93-0ABB-4C81-B368-B607F8D16AB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"956011c114e6dd22e97d3f55a2cdcb05b32ae2df","datavalue":{"value":"sub-gaussian random variable","type":"string"},"datatype":"string"},"type":"statement","id":"Q2722658$19242F99-BCFC-431D-BA4E-6416E5E2A193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2722658$8A08B973-85A4-403C-8AC0-99E414004501","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":"Q2722658$14F8F2BB-D6F9-4500-9AD4-1B343C7F209E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7a94faf6e07305947e373df67865be61c7fa7afa","datavalue":{"value":"https://doi.org/10.1017/s0963548399004095","type":"string"},"datatype":"url"},"type":"statement","id":"Q2722658$3064CF71-2BDC-428B-919F-BA1751471235","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8901aac83c163e5c1b7acc7b36a6ca3088db6bb3","datavalue":{"value":"W2089062694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2722658$6AB27FAC-8D8D-418A-B79A-21C6C456CCB5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"149732a311b8d51002448a7e190c7296c63f239c","datavalue":{"value":{"entity-type":"item","numeric-id":3145838,"id":"Q3145838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81f382dedeaf17c8450421a56455e8a4a1cee1d0","datavalue":{"value":{"amount":"+0.8022699","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$EDE73CCC-30FF-4337-AD02-DF5CEE5B1D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e171a70120097952c09969cfede66828563b50a","datavalue":{"value":{"entity-type":"item","numeric-id":1881736,"id":"Q1881736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64a5c93f6c93050e87f3d7f90e375edf1ffadc35","datavalue":{"value":{"amount":"+0.80069184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$E3622F17-BA9A-4851-8492-E92692B5AC80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"487bf4a383d51cd550593dcb388bf65480ef6376","datavalue":{"value":{"entity-type":"item","numeric-id":3781137,"id":"Q3781137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67308b58170d3f384e97576507422621003c5978","datavalue":{"value":{"amount":"+0.79547065","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$05068977-A3D6-46F8-B1E5-5BC7D9BE5697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f08e7a82f7a3b475899db85efd3f0cf035feb87","datavalue":{"value":{"entity-type":"item","numeric-id":4207934,"id":"Q4207934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4234c295bed860bbe5274fc569edbc9387adfc8f","datavalue":{"value":{"amount":"+0.7884823","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$E0E5E3E2-7417-48AB-A0A6-C47AFE4959DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59cfeeadb29abefd8fcd3d288c2bcad8dedf78ad","datavalue":{"value":{"entity-type":"item","numeric-id":1612953,"id":"Q1612953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a27049ce4bc5c8600bfa3e7ff0b830a09bd8bb65","datavalue":{"value":{"amount":"+0.77995336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$486F619C-B0B4-405D-BA57-144A5046C0A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19ce9fd7acd32de3e503c24b0af8b3075a69e08f","datavalue":{"value":{"entity-type":"item","numeric-id":1092512,"id":"Q1092512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00367823d027bab8f988c26b48357579c0691cce","datavalue":{"value":{"amount":"+0.77856576","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$7BB81340-A891-4846-A606-8DE3CE914D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d15e81008d982c4469c3a7f9186fdafd59fa57a7","datavalue":{"value":{"entity-type":"item","numeric-id":6101707,"id":"Q6101707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cac394747b73e6a1035c9ad2c4d245f90dbfa5e","datavalue":{"value":{"amount":"+0.7763782","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$DE20F1C2-F4E7-4AAF-93FE-59229BDC92F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76926d67733b0a5bb9aaa9e8af7ff06d23eda9b8","datavalue":{"value":{"entity-type":"item","numeric-id":5750022,"id":"Q5750022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1709fafeb9e62ac5b5c870a1f373d6cc488060a","datavalue":{"value":{"amount":"+0.77634984","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$160063A7-7581-4485-A105-00A1D9032669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"747db1ca94d6911c40818a1bc421258e8004ade4","datavalue":{"value":{"entity-type":"item","numeric-id":2039444,"id":"Q2039444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59a9578e0914aa1264de7b8c06b3b3c3b0fc8118","datavalue":{"value":{"amount":"+0.7734805","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2722658$56BA9C6D-95BA-4940-8B17-D7A411E9ED55","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"28864b4c4ebf1ebd47e2e31dbeeba812d1cca102","datavalue":{"value":{"text":"A large deviation result on the number of small subgraphs of a random graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2722658$383CE47A-46F0-4157-836C-B83ECD2F6786","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8ce432117a8f2ea0bc4971b9b6f3d0dfe505c11c","datavalue":{"value":"This paper applies a new martingale inequality of \\textit{J. H. Kim} and \\textit{V. H. Vu} [Concentration of multivariate polynomials and applications, Combinatorica 20, No. 3, 417-434 (2000; Zbl 0969.60013)] to the following random variable: Given a fixed graph \\(H\\) and given a positive integer \\(n\\) and \\(p \\in [0, 1]\\), let \\(Y_H\\) be the number of copies of \\(H\\) in a random graph \\(G_{n,p}\\). There are a number of papers on this r.v\\(.\\) for \\(H\\) balanced. This paper concentrates on the upper tail of \\(Y_H\\): the primary theorem says that for appropriate \\(\\varepsilon > 0\\), if \\(H\\) is balanced and has \\(k\\) vertices, and if \\({\\mathbf E}[Y_H]\\) grows sufficiently rapidly as \\(n \\to \\infty\\), then \\({\\mathbf {Pr}}[Y_H \\geq (1 + \\varepsilon){\\mathbf E}(Y_H)] \\leq \\exp(-\\text{ const}\\cdot \\varepsilon^2{\\mathbf E}(Y_H))^{1/(k-1)}\\). A corollary of this result---involving the fractional independence number of \\(H\\)---is somewhat sharp. The proof of this result proceeds via a generalization of the primary theorem to a r.v\\(.\\) counting the number of extensions of a subgraph of \\(H\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2722658$DF029053-41CF-4030-B153-AEC1306C9BAB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4c2e453a383fe1e064f27e4ca3ff49f8a1646b9","datavalue":{"value":{"entity-type":"item","numeric-id":587174,"id":"Q587174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2722658$C78F74C7-927C-442F-B4EE-1392464AD7D2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2722658","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2722658"}}}}}