{"entities":{"Q6654120":{"pageid":14265277,"ns":120,"title":"Item:Q6654120","lastrevid":55811983,"modified":"2026-02-17T23:13:31Z","type":"item","id":"Q6654120","labels":{"en":{"language":"en","value":"On isomorphism-invariant antistochastic properties of random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7959407"}},"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":"Q6654120$9126B602-96AB-4792-8F4E-41CB4DA50F9E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac4e1766c8a88c442521d5b105b775d92afc9838","datavalue":{"value":{"text":"On isomorphism-invariant antistochastic properties of random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6654120$7579E863-772E-4F2A-B5CF-A76E5BCAC239","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4848e047a9c277c72032ad27eb943e1ba998ceb5","datavalue":{"value":{"entity-type":"item","numeric-id":2075510,"id":"Q2075510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$B2E3CA00-AFEF-468E-B410-F7AC755752C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6975d3915f5b83b7ed8c3595b03a0b1035010455","datavalue":{"value":{"entity-type":"item","numeric-id":591850,"id":"Q591850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$3C83DC2A-DC75-4967-9051-468381B96ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d4e03f109ceb4ac5ef6232e2470c42de5582cda","datavalue":{"value":{"entity-type":"item","numeric-id":259080,"id":"Q259080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$ED89C385-97F1-43F3-B5C2-6901A5B4E5D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"214e732b9ee41b2396f55de0fe64813983a0ad39","datavalue":{"value":{"entity-type":"item","numeric-id":265976,"id":"Q265976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$3F68C9FD-DAF4-4B2E-AD7B-B165D6A141CC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39a509948a5fd41054da3e7af81581f39adaebc1","datavalue":{"value":{"entity-type":"item","numeric-id":2706174,"id":"Q2706174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$EDA71368-CA95-438A-AE46-36558F7735EB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e1a1dde559919fe84de6d7ed8372e728bb6adc88","datavalue":{"value":{"time":"+2024-12-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6654120$CE7E25D6-B972-4B11-BF11-53E4598C56B5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"99e5839b4fc14aa695f045f6ae21b989eb4046d3","datavalue":{"value":"This paper considers a class of graph properties which are defined as anti-stochastic. A graph property (that is, a subset of graphs on a given vertex set that is closed under automorphisms) is called anti-stochastic if it does not hold with high probability among the set of graphs on \\(n\\) vertices (selected uniformly at random), and there is a function on this set of graph which modifies only one pair of vertices and, thereafter, the property holds with high probability as \\(n \\to \\infty\\). This function can be thought of as an adversary who makes a local change which results in the destruction of the property. The first result of the paper shows that there is such a property that occurs with probability \\(\\sim 2/n^2\\). (Note that a property with an asymptotically smaller probability of occurrence cannot be anti-stochastic.) They also deduce this for the anti-stochastic properties of unlabelled graphs. The construction of this anti-stochastic property (for the labelled case) relies on covering codes with optimal density. Roughly speaking, such a code is identified with a set of labelled graphs and its closure under taking isomorphisms. The issue with this approach is that the property that will be created will not occur with low probability and hence the set of graphs needs to be sparsified, with the use of a certain construction. The authors also construct another anti-stochastic property that is expressed in terms of the degree sequence - this occurs with probability \\(\\sim 2/(n\\ln n)\\). Moreover, they show that every such anti-stochastic property holds with probability at least \\(\\sim 1/(n\\ln n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6654120$7491EFD4-19C7-45D2-9AD9-2E2B47B6841D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee5ba7f50bd271f0d45cb8360d5c0d385d238ae","datavalue":{"value":{"entity-type":"item","numeric-id":490411,"id":"Q490411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$79B0D905-874E-4DA3-BF2A-660E7F1C9C3A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6654120$001C4E81-C7F2-4910-BBFD-B4959C7A6178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd80e9ade304e6b9b43fd50d0c3436276c3c217e","datavalue":{"value":"68M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6654120$0D30B238-7A14-450E-BFB7-F11879A1C1CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6654120$7B5687FA-5460-4D28-BF9E-A160B505B340","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e53363a5623da646f0ef4e8b83f6aee95d94b035","datavalue":{"value":"7959407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6654120$93165A87-59D3-4C24-B523-35B8858B4818","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3939983d8a567b8cfe63f369001fff5690ff290f","datavalue":{"value":"network resilience","type":"string"},"datatype":"string"},"type":"statement","id":"Q6654120$F5F74CAB-9505-4A34-8EB5-766D38CC0711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6654120$8684E6F4-6694-4F6A-B4CC-FF9F744EC1C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f1df13d04523cac6506c837a9a53b1d036ae39e","datavalue":{"value":"canonical labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q6654120$6F1E13AB-CC11-4F8E-9910-619A91F8B299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96e65b84eb6b911451fdc63d78150ade63c72bb9","datavalue":{"value":"covering codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q6654120$3708554D-F5DA-4063-B0B7-5F857B4E7B1E","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":"Q6654120$800DA797-DE9F-47AF-A63B-DB45ACBF11E5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d77e9ffcf490432ab87bb197c96f2943b4e5b7b","datavalue":{"value":{"entity-type":"item","numeric-id":5096587,"id":"Q5096587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$5C715580-7054-41E6-BC7B-C2044FA092A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1bb63192136286ee2b68ee1b226f2d4a02b4b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3901544,"id":"Q3901544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$987CFFAC-FF2D-4E55-B3E9-C79327604906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39f9d10eb707668c935937ec2666a063d80e5521","datavalue":{"value":{"entity-type":"item","numeric-id":1146197,"id":"Q1146197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$86693D1E-3C38-42EE-980A-36F223B81555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c701fcaba4e939dc2ac7d37951bb51d61c93b431","datavalue":{"value":{"entity-type":"item","numeric-id":4665449,"id":"Q4665449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$B7E83CC3-3691-4AD6-BF3A-591376BFEA43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9857835f2fbb70e39920ffb2c1506a4670e8a576","datavalue":{"value":{"entity-type":"item","numeric-id":4673812,"id":"Q4673812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$BEA1A497-5F97-4295-8FD2-0D7B7E190166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"012d7d134e842ccbbed97375bbcfb08901132f0b","datavalue":{"value":{"entity-type":"item","numeric-id":5013044,"id":"Q5013044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$B9757075-27BD-46AF-87CA-6424E496F35A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2553a85c0a1015fcfa80873ffd8c0ab14277d9a","datavalue":{"value":{"entity-type":"item","numeric-id":5295413,"id":"Q5295413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$64D82252-3FE4-43CC-A2F7-802094495F3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cff90b53746deaf40f0bd975035788d645dc76ab","datavalue":{"value":{"entity-type":"item","numeric-id":5682013,"id":"Q5682013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$FF9AA473-122F-439C-BDD5-69DB1240A68D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747287d951bc0727d2faf0ea3bf65fd6de73c2b1","datavalue":{"value":{"entity-type":"item","numeric-id":2808289,"id":"Q2808289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$4141D634-33C6-4A31-B917-BF6BFD1D37C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$140C23B5-5F7F-4EE3-99F0-E1E306CDA075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4e779be5bbf59a5d5835c4a93280a8f3783f15f","datavalue":{"value":{"entity-type":"item","numeric-id":1823223,"id":"Q1823223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$B466FA08-B977-41B5-B59D-DB95C24ED85D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e248c2c8bd114f7aef643c772a725a8d66f932db","datavalue":{"value":{"entity-type":"item","numeric-id":6039431,"id":"Q6039431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$25B5ABAA-1D10-4057-AA5E-621EA0A52EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1881c5760c84c07d4da87958f3ef422650e9306","datavalue":{"value":{"entity-type":"item","numeric-id":3547185,"id":"Q3547185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$654F159A-9117-41EF-B081-81B7BB002042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d848923825d5db7f12322d73e3c7d54f151c640c","datavalue":{"value":{"entity-type":"item","numeric-id":6151860,"id":"Q6151860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$BA3B420B-C8F5-414F-B50F-CCA3A791684C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52a11691d27dfd44b14e5a0e14462216cb2fd7a0","datavalue":{"value":{"entity-type":"item","numeric-id":1814088,"id":"Q1814088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$079FE610-F11D-44DE-B84C-8C957AF10972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09ac3d4954947d1cf7abac4ad34fb6712dccd1af","datavalue":{"value":{"entity-type":"item","numeric-id":4358436,"id":"Q4358436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$B326403B-238F-4F83-87EB-2284CC9EF5DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0da16e2f10b28bcbf80a35d578bcf68a1a5ff54a","datavalue":{"value":{"entity-type":"item","numeric-id":4958825,"id":"Q4958825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6654120$E5EB0893-B422-40C7-A75A-D554EC657008","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c1e5ac55d043ac5371d526094e24002a73394f3e","datavalue":{"value":"10.1137/23M1575287","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6654120$62568E93-4183-483E-99C6-9F6C46D94935","rank":"normal"}],"P1643":[{"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":"7ae6a1e1080045e37789647c1eb1199016418e4c","datavalue":{"value":{"amount":"+0.7072095274925232","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":"Q6654120$57175885-73D3-49C3-9C72-140A5930BF5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b52c2c2a2c0e855fc7504fd4574f211468ac116","datavalue":{"value":{"entity-type":"item","numeric-id":4943756,"id":"Q4943756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7914cb9fe04c18f5beb960fd7616daaae191121f","datavalue":{"value":{"amount":"+0.7051261067390442","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":"Q6654120$29C86628-0FDD-4048-B332-0288733DD83D","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":"be70b2f6a7a7193e7c9dd68a09cb37b9a94232a9","datavalue":{"value":{"amount":"+0.7039135098457336","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":"Q6654120$697AF02D-FE98-48E6-B3D4-40026788661D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd1ffb9c99050284ea229d3921751c88dfa9d544","datavalue":{"value":{"entity-type":"item","numeric-id":3652542,"id":"Q3652542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba08ba6fd1c2bf6207b638d9e0036a38236eb4ae","datavalue":{"value":{"amount":"+0.7016980051994324","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":"Q6654120$ACA20F42-7EE0-4066-B5B2-667E6B6BA805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"486c5e308e38541aa430afeb35f77fe47d90d80a","datavalue":{"value":{"entity-type":"item","numeric-id":3608302,"id":"Q3608302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae449072bd0aa0a5672d31e55ec7f64db3b4a460","datavalue":{"value":{"amount":"+0.6976324915885925","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":"Q6654120$8A5219FA-90B3-45F3-A5A1-E0D018ED090B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6654120","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6654120"}}}}}