{"entities":{"Q1046741":{"pageid":1048589,"ns":120,"title":"Item:Q1046741","lastrevid":69502827,"modified":"2026-04-13T07:26:30Z","type":"item","id":"Q1046741","labels":{"en":{"language":"en","value":"Quasi-randomness and the distribution of copies of a fixed graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5651823"}},"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":"Q1046741$81F969EE-F92F-4A5C-8B2D-C07F73A94E49","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6398d2f0ce50dad16f227da41a93f7dc6e113af7","datavalue":{"value":{"text":"Quasi-randomness and the distribution of copies of a fixed graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1046741$FE5BD8F7-C1EB-41AF-A255-8B467AF13CBC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"16a4e4946b18fc04786dc07fa746f2b4f3b35a33","datavalue":{"value":"1196.05090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1046741$66D1D824-3906-403E-8758-A29A5DF3DAA6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"63374f39c7f9618158f0fe867382b7bf912eea01","datavalue":{"value":{"entity-type":"item","numeric-id":313428,"id":"Q313428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$A7054E93-5C6D-4082-8811-ABC137186781","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":"Q1046741$9D8A41F7-663A-4AFF-8249-E89FE0A92A3E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"60ddcab37b05da2adf7c870c563469ec8d4476c2","datavalue":{"value":{"time":"+2009-12-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":"Q1046741$1798A979-1305-42DF-8D3B-8B3806036450","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cc319a4cf56f304a7504468c59a3ceace08b9f2b","datavalue":{"value":"The notion of quasi-randomness is due to \\textit{A. Thomason} [Surveys in combinatorics 1987, Pap. 11th Br. Combin. Conf., London/Engl. 1987, Lond. Math. Soc. Lect. Note Ser. 123, 173--195 (1987; Zbl 0672.05068)]. By the subsequent work of \\textit{F. R. K. Chung, R. L. Graham} and \\textit{R. M. Wilson} [Combinatorica 9, No. 4, 345--362 (1989; Zbl 0715.05057)] it turned out that a sequence of graphs is quasi-random if it exhibits some behavior of random graph properties asymptotically, and in fact a number of equivalent properties ensure this. For graphs \\(H\\) and \\(G\\) and \\(U \\subset V(G)\\), let \\(H(U)\\) be the number of labeled copies of \\(H\\) spanned by \\(U\\). Two properties that Chung et al gave were \\({\\mathcal P}_1(t)\\) and \\({\\mathcal P}_2\\).  \\textit{M. Simonovits} and \\textit{V. T. S\u00f3s} [Combinatorica 17, No. 4, 577--596 (1997; Zbl 0906.05066)] gave a different notion, which allowed a generalization of these results. For a fixed graph \\(H\\) on \\(h\\) vertices, the sequence \\(G_n\\) has the property \\({\\mathcal P}_H\\) if (1) \\(H(U)=p^{e(H)}| U| ^h+o(n^h)\\) for all \\(U \\subset V(G_n)\\). They showed that for any fixed \\(H\\) with \\(e(H) >0\\), property \\(\\mathcal P_H\\) is quasi-random. However, it was left open if one really needs the property \\({\\mathcal P}_H\\) for all \\(U \\subset V(G_n)\\), and they asked if less assumptions on \\(U\\) was enough for quasi-randomness. The author of this paper shows that the quasi-randomness of a sequence \\(G_n\\) follows if for a fixed, non-empty graph \\(H\\) (1) holds for \\(U \\subset V(G_n)\\), \\(| U| =\\lfloor n/(h+1) \\rfloor\\), where \\(h=| V(H)| \\). The proof utilizes simple counting arguments and an old result of \\textit{D. H. Gottlieb} [Proc. Am. Math. Soc. 17, 1233--1237 (1966; Zbl 0146.01302)] on the rank of incidence matrices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1046741$5111A237-1502-45F3-B2E3-AA87EF213543","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$294B4840-8154-4F78-963E-136D68C6A433","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1046741$6E5E689C-4C6B-4897-A623-17F0F506A650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1046741$099C018D-4AAD-4B07-8548-3AFDACB8F90B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e982c2fedaf73195b2453f8f27fd660556bda2f7","datavalue":{"value":"5651823","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1046741$DAA42796-C076-49ED-8993-219017747BA4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9c3b16e683c92cc1b76bd3b0904bc74d61be5b9","datavalue":{"value":"quasi-random","type":"string"},"datatype":"string"},"type":"statement","id":"Q1046741$C62B8C97-7BBB-4131-A1CC-FEC2B6491EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e7aa9261afd174c3e2f5b7f5c7e2a299a554644","datavalue":{"value":"subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1046741$61E11143-967D-4ED2-906A-C85F6153BC02","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":"Q1046741$319762E7-0E17-48D8-96BE-B9C81FDC6CED","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"425564ec632948bab540b8ba66fab509a68a1e19","datavalue":{"value":"https://doi.org/10.1007/s00493-008-2375-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1046741$1447CD1C-B4E0-47B0-8418-E0334AF4890A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"82fea81293e76fa65ce1cf76857663a4c6bd7cf1","datavalue":{"value":"W1981155052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1046741$0CF67F40-4CE4-4D3A-89DF-72DF198B0EFD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b677272a74318a9f34ee40d9a5474adca6c3a50","datavalue":{"value":{"entity-type":"item","numeric-id":5936673,"id":"Q5936673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$C4A2B783-542B-4BED-949D-B2A0D38F1C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"318f44d118522d39d50fc07f038a599427d02ea3","datavalue":{"value":{"entity-type":"item","numeric-id":4713353,"id":"Q4713353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$E8809493-5823-4D39-A559-6B73CD5CBD12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2742994e65d1f54899f4a2a63d8b3282bc3a3d9","datavalue":{"value":{"entity-type":"item","numeric-id":3351382,"id":"Q3351382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$CE917408-C576-42A8-B632-54CA96B932B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d90153c1718c0cdbe61e33989bb3f3029b7b4550","datavalue":{"value":{"entity-type":"item","numeric-id":3490029,"id":"Q3490029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$0D942AF8-8DA5-44A8-A366-649CC85F2950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f791412b285553b13dabedab6f9c7458ca857cd","datavalue":{"value":{"entity-type":"item","numeric-id":5895286,"id":"Q5895286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$4FDFF43D-31F5-4315-8BBE-07F74B85949B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e9b19b2bec5333f4867d91c200cfb399261ca47","datavalue":{"value":{"entity-type":"item","numeric-id":5522934,"id":"Q5522934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$BD3D114E-1B34-48CD-822D-BDBA882AC4D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbdff7ff1c3296a0720464e22f5d41d7983d0973","datavalue":{"value":{"entity-type":"item","numeric-id":3545904,"id":"Q3545904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$F8914CE6-207F-4482-BCC0-903568CA200D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb1522618db27e00224a0bcdaa7c4090c1096d3c","datavalue":{"value":{"entity-type":"item","numeric-id":2464159,"id":"Q2464159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$F3C19376-3B72-41D0-82D3-C30975EBA002","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42c0a7c010095f7d903e442b8caa7e259b99cfdc","datavalue":{"value":{"entity-type":"item","numeric-id":1276304,"id":"Q1276304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$D2ED9A55-A01A-4D5F-90D5-AC998F53F057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbda30c5040a234eebdd1ccfe3d414aa0e2ca962","datavalue":{"value":{"entity-type":"item","numeric-id":3825110,"id":"Q3825110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$1700FC9A-3C41-4C12-94BF-12F0514FAF07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93ef8bc849c5132d2a91c861867b4239e0e6597e","datavalue":{"value":{"entity-type":"item","numeric-id":1814091,"id":"Q1814091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1046741$650B19E5-58C2-40F0-AB30-233CF416AD6A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"19c8a26aa580b7910f19c0b85c14f6529ea11a24","datavalue":{"value":"10.1007/S00493-008-2375-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1046741$3218CBB8-A760-48DE-B726-9DE103DF5547","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37ded0a093dcbbb3e1c4817ab1ebdca9b30b3562","datavalue":{"value":{"entity-type":"item","numeric-id":3439469,"id":"Q3439469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06ef6f525c0c674e6dc2247512ddcc35a83684d2","datavalue":{"value":{"amount":"+0.9507508","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$386BB1B9-81C3-4525-A05B-E5FDDAF5C29A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44b4bc99df301f7781eb6399821df874d82fa613","datavalue":{"value":{"entity-type":"item","numeric-id":532131,"id":"Q532131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae181df8f063b63847b6eec333875ca485397b0c","datavalue":{"value":{"amount":"+0.9486333","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$4069C3AE-952D-4EA3-98A8-3BAAF946BE21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b2043c631b18c7fd8f936e7364a5d3a4ad2732b","datavalue":{"value":{"entity-type":"item","numeric-id":3541823,"id":"Q3541823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae181df8f063b63847b6eec333875ca485397b0c","datavalue":{"value":{"amount":"+0.9486333","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$187A4DF7-B274-4804-805D-9DF362EDC6C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a62e2ffb5d1285c651581bc93bc4db7c2ac9aec","datavalue":{"value":{"entity-type":"item","numeric-id":5895286,"id":"Q5895286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36da8754dbcabc31aa592085d6c76548e2f4dc56","datavalue":{"value":{"amount":"+0.92643607","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$2DAD6345-9419-4FC1-810A-59A244192FF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6df2b5f2ef53110a614872654950e0d3055e745","datavalue":{"value":{"entity-type":"item","numeric-id":5903501,"id":"Q5903501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36da8754dbcabc31aa592085d6c76548e2f4dc56","datavalue":{"value":{"amount":"+0.92643607","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$EDAC9D9A-42CC-4401-AD9E-7DDBADB0DFF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a67b1269b4363234d484d4f0044fd38f83025978","datavalue":{"value":{"entity-type":"item","numeric-id":5915722,"id":"Q5915722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"614123ef29dc6e156c953c80a198d58f27430489","datavalue":{"value":{"amount":"+0.9248489","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$F15E6529-6750-46D1-BE93-9EF6F19AD2B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0843f0c56e78f44e5010760e865063070a848664","datavalue":{"value":{"entity-type":"item","numeric-id":5970254,"id":"Q5970254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f88cefabbaea4d242f8dfd5124e58b67ab4bfa7a","datavalue":{"value":{"amount":"+0.92484885","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$AE18CC41-F50B-4E6C-9F49-E7B0F01AD62A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7db3d6635cdd36c0f9cb3277465c162294d03dcd","datavalue":{"value":{"entity-type":"item","numeric-id":5428859,"id":"Q5428859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"824a2428a8c7c5975d5b549a1262a554e1abd7ac","datavalue":{"value":{"amount":"+0.92194724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$D1D5C53E-9E37-4BAC-84AC-BAA9E174AB90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36fc26cb67815e474a55c4512559d4dc5864b601","datavalue":{"value":{"entity-type":"item","numeric-id":3068635,"id":"Q3068635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"824a2428a8c7c5975d5b549a1262a554e1abd7ac","datavalue":{"value":{"amount":"+0.92194724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1046741$5B60EE82-5383-4364-9FF2-8C286F2290F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Quasi-randomness and the distribution of copies of a fixed graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Quasi-randomness_and_the_distribution_of_copies_of_a_fixed_graph"}}}}}