{"entities":{"Q5937420":{"pageid":8114222,"ns":120,"title":"Item:Q5937420","lastrevid":39867810,"modified":"2025-01-27T19:18:59Z","type":"item","id":"Q5937420","labels":{"en":{"language":"en","value":"The penultimate rate of growth for graph properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1619142"}},"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":"Q5937420$0CB50F06-5E69-4704-9064-5706147BBA0C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d44101e8ba48b744f658e3f4294ad79715481f41","datavalue":{"value":{"text":"The penultimate rate of growth for graph properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5937420$74355CF4-8EEA-4032-BBC2-1282BC8A738A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e530476ee6e540c2788147c1f6d829a4bd3917c","datavalue":{"value":"0979.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937420$F0A646DD-C4F0-4565-A3E4-F46A94E50C00","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":"Q5937420$6352DC5D-421D-470F-A26F-B8E848CC30F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a14bac90927db699ac4af297f1d406f2762c11d","datavalue":{"value":{"entity-type":"item","numeric-id":168581,"id":"Q168581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$BDE8894B-2C92-44F0-8F44-1AAF7D4DCEB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e57ace02d1dad65d60633918cc61576ea5b0ac9","datavalue":{"value":{"entity-type":"item","numeric-id":189373,"id":"Q189373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$EE5EC4C6-692D-4ECD-9568-C20CEEA904AF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$1FA0ABD4-ABAD-4689-9E99-3FCCAB3B8CD7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e79d707db8a7dd0c9320fe70c045f43c844f1ed5","datavalue":{"value":{"time":"+2001-09-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5937420$E131B1B0-8197-4BF2-880B-6BBD209E7E11","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1fd492c01b83f8de403493c24639ac74b6de803b","datavalue":{"value":"https://semanticscholar.org/paper/fffb6069e3e6ca4c64653493a9b6cfbf36cb325d","type":"string"},"datatype":"url"},"type":"statement","id":"Q5937420$179FE43A-F9CD-44D8-B06E-2A8AF7E4DEE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2fe238f23d30726786bdbdfa7847ff48311c8dac","datavalue":{"value":"A hereditary graph property is an infinite family of (labelled) graphs closed under isomorphism and induced subgraphs. The growth rate of such properties, that is the numbers of graphs with \\(n\\) vertices belonging to a fixed property, has been object of considerable study; it is known that not all growth rates can occur, and that some growth rates imply structure theorems for the properties. The subject of this paper are hereditary graph properties with growth rate near the top: in the range \\(n^{(1+o(1))n}\\) to \\(2^{({1\\over 2} +o(1))n^2}\\). The authors show some restrictions for the growth rates in these intervals: especially for monotone properties (closed under arbitrary subgraphs) they show that if the growth rate is \\(2^{o(n^2)}\\), then it is \\(2^{n^{2-(1/k)+o(1)}}\\) for some \\(k\\), which they conjecture to hold for all hereditary properties. Then they construct hereditary graph properties whose growth rate oscillates almost across that whole interval, giving a counterexample to the existence of some limits conjectured by \\textit{E. R. Scheinerman} and \\textit{J. Zito} [J. Comb. Theory, Ser. B 61, No. 1, 16-39 (1994; Zbl 0811.05048)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937420$229BA8C3-09C3-4659-825C-E822A92FE305","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"13b2797137908bf085ac37482e4ca3bd3f2ade57","datavalue":{"value":{"entity-type":"item","numeric-id":587716,"id":"Q587716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$764D9866-2382-40E7-AB49-DD8675C3BA57","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937420$A14F56F7-35FA-4130-BA51-C13204F3C487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937420$C3A87025-2CFA-40EC-85FB-C4E667AC31FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937420$460760C6-6B86-4D8E-AAB2-72AD3740B384","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4fbe6c06797a65468db3b754c28e8570dc035cd6","datavalue":{"value":"1619142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937420$832EE826-595B-4BA5-B19A-73E6F5F1E7D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ff660537c46a0ea02613438ef354efbfd3b43bd","datavalue":{"value":"hereditary properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937420$9B80839A-C627-468A-9F2C-7389677AED99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e4048fb3bfeb12f1e8c632141b78129e67aee7a","datavalue":{"value":"graph properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937420$97C193F8-C8C0-41EE-8483-AB2F80056CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"668c80a37c2dc29632ae9cb7b7fc7977c957d4d3","datavalue":{"value":"rate of growth","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937420$CA531875-4123-4AC3-A040-0947F9596351","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":"Q5937420$7E6FA901-73E8-4079-A2FA-DBEC7A2F9C63","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b99964cc3f35549a8f87315d4327e470ef2ce57c","datavalue":{"value":"W1997003521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937420$6A428A5F-4074-4EB0-B59C-754C53D4FC4B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b05686315e2af89527066e498bb70884fa94394","datavalue":{"value":{"entity-type":"item","numeric-id":1850473,"id":"Q1850473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$A4A58CF7-2071-48D6-A66C-7548D8495F71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7f14b1a2acb8bdc9be3628d83bd4b21fddf88e8","datavalue":{"value":{"entity-type":"item","numeric-id":5957296,"id":"Q5957296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$AD531F21-CC80-4152-83E5-279D3BBD63A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$41BD20FB-A2EC-4328-A980-58C9F1E59915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a704198da27f51a523769de240a677b950b9d5ff","datavalue":{"value":{"entity-type":"item","numeric-id":4863823,"id":"Q4863823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$0656BFC6-A123-4D7C-A2D8-09533B1724AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b813a75cb6ff12274c158509fab3ef710a1e248","datavalue":{"value":{"entity-type":"item","numeric-id":2564771,"id":"Q2564771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$1B594535-C70A-4468-B731-AB2B3DB2334D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0893f06f165134598a1fdbebb0666712d7a2e96b","datavalue":{"value":{"entity-type":"item","numeric-id":5928567,"id":"Q5928567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$A6A5024C-8D51-458B-A2AD-9769FA103403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ada53980e8d3e7e8a0a401742a431780860804","datavalue":{"value":{"entity-type":"item","numeric-id":5825672,"id":"Q5825672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$D951AF78-57CC-497C-9853-0608A14EBDF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f74985c921ba19e96ddaffec2c2a237b92755bb","datavalue":{"value":{"entity-type":"item","numeric-id":1328380,"id":"Q1328380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937420$BDFE72CD-962E-46D2-88CB-B7FAD4CD33E6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b16bf79ed182bb461a6042af1e5e7189137b1b32","datavalue":{"value":"10.1006/EUJC.2000.0476","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937420$B9F0442A-74E4-4EE6-BACE-41A9566DCD2C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15b076ccd86849949d2d30137913e6a07f2cda77","datavalue":{"value":{"entity-type":"item","numeric-id":1328380,"id":"Q1328380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab3f39a79e22421b47b5066815ae190e13299211","datavalue":{"value":{"amount":"+0.84417915","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":"Q5937420$232298AA-465A-4D20-9F05-16FEB0F6F830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4333798d55b692ce6018690dd2c0c75ffff03fd","datavalue":{"value":{"entity-type":"item","numeric-id":1850473,"id":"Q1850473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5efc425626ab1a5d37aa63e24a63f403cdb09012","datavalue":{"value":{"amount":"+0.80794907","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":"Q5937420$99C1385D-8197-4197-A16D-4D418A5E8653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a007aabffda53c1367a3a8e2fc756f581615d052","datavalue":{"value":{"entity-type":"item","numeric-id":631643,"id":"Q631643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea4d397a798ac2e363f75c8626f8dd6ccbed2335","datavalue":{"value":{"amount":"+0.7906407","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":"Q5937420$9C894728-A6FA-476E-90C7-659AD4CD519B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae61c6e11c8124f5c34a4bb8d3fe3a53b14386d3","datavalue":{"value":{"entity-type":"item","numeric-id":1126826,"id":"Q1126826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d508be991468b2b5c87ffc11b0578cc4f86ec12","datavalue":{"value":{"amount":"+0.78668576","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":"Q5937420$D67DA1CA-068C-49F1-BCB3-840A22A1C134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"708c6a84308e07165aa3ea98245f577befcef89b","datavalue":{"value":{"entity-type":"item","numeric-id":2565685,"id":"Q2565685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15116a5b292acbe9efa3f677a10fdc8ec1cc1d64","datavalue":{"value":{"amount":"+0.78357065","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":"Q5937420$C0E1A2D3-D474-4290-86C8-737A4BC3273C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a56fe813a80436b9c8487051e988652111b641e3","datavalue":{"value":{"entity-type":"item","numeric-id":5688999,"id":"Q5688999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e792c92f940d1a420f96b8ccb5758a9779178223","datavalue":{"value":{"amount":"+0.7831484","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":"Q5937420$D42017D0-19F3-4073-BCD3-0C9B149A878C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec71981a57f5ef5a1ab1da59583ed5e694cb6365","datavalue":{"value":{"entity-type":"item","numeric-id":896080,"id":"Q896080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17ebaa943c703b1876ed609d9fbfcb315f2457b9","datavalue":{"value":{"amount":"+0.7731866","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":"Q5937420$2B3C004E-CB3B-4487-8AB7-159324E7B0F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9cd00388e750a041825717b75d9eacd5dab7f01","datavalue":{"value":{"entity-type":"item","numeric-id":4604027,"id":"Q4604027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cec3be20aad680118649df5521f2482879b19a4","datavalue":{"value":{"amount":"+0.7648069","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":"Q5937420$3E3DEDEC-2C48-4C5E-9C9D-4A6DBB8F6985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a728a3b356dfdcf35ace709996393a9747998963","datavalue":{"value":{"entity-type":"item","numeric-id":2519010,"id":"Q2519010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d4232a8fa109d9d6a877bfd4ecc28ccf8c9098d","datavalue":{"value":{"amount":"+0.7578017","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":"Q5937420$6535441B-F28E-46AF-A934-32AEECC47DF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db36cc7fcb4a33251f950a16fa4736d9867e115f","datavalue":{"value":{"entity-type":"item","numeric-id":5434263,"id":"Q5434263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d95fc2bf6305905cfc06c21b680dce9bcaff0a11","datavalue":{"value":{"amount":"+0.7568568","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":"Q5937420$D3A1884D-49E5-49DB-9FE7-858D6177B77E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5937420","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5937420"}}}}}