{"entities":{"Q640407":{"pageid":642255,"ns":120,"title":"Item:Q640407","lastrevid":63215562,"modified":"2026-04-11T11:23:29Z","type":"item","id":"Q640407","labels":{"en":{"language":"en","value":"A note on the speed of hereditary graph properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5960019"}},"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":"Q640407$1C6DA062-8B41-4DAA-BABB-DDF2A65D20A7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"01c3d3bd6e360bf77146118a0af97a1e654f27b0","datavalue":{"value":{"text":"A note on the speed of hereditary graph properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q640407$8BCE36D4-ADC0-4F09-AF52-BAFF726A1BAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e070f079de8d06a6646e9376eb6ca24df1ad9881","datavalue":{"value":"1230.05164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640407$C09BA385-42F7-410E-9A82-812C7E779C8E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9924970a3259a1323042c8227a65163844bb317","datavalue":{"value":{"entity-type":"item","numeric-id":317397,"id":"Q317397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640407$C44E9364-AD64-4776-BC19-F353C1E7D31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d67f2e114037028e25a17f7604b8cbc141be0de","datavalue":{"value":{"entity-type":"item","numeric-id":402473,"id":"Q402473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640407$E6F360D8-6B57-4CEE-82DF-7BE33F549972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5ce2336c6a65611e3dffdf02ab1a7d5c2b50cd7","datavalue":{"value":{"entity-type":"item","numeric-id":402474,"id":"Q402474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640407$6ACD2C62-74F3-482C-827A-44185D1CE6A2","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":"Q640407$82A8515B-1567-4907-AEA0-2AB9AA005F7E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9767fe8dd1d6f9791ae763e9a67550b5f9aa27e1","datavalue":{"value":{"time":"+2011-10-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":"Q640407$BD0B11C9-A079-4D66-9C9C-6BA10B7839D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a79c2e9a8a272994b5f40daa8098407a961750bb","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p157.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q640407$D4E8BAB7-FCB3-4E57-ADB5-B6E9F616B809","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"43d6d293fbc8e52f6cc076ba8c4aafa40320ff07","datavalue":{"value":"Summary: For a graph property \\(X\\), let \\(X_n\\) be the number of graphs with vertex set \\(\\{1, \\ldots , n\\}\\) having property \\(X\\), also known as the speed of \\(X\\). A property \\(X\\) is called factorial if \\(X\\) is hereditary (i.e. closed under taking induced subgraphs) and \\(n^{c_1n} \\leq X_n \\leq n^{c_2n}\\) for some positive constants \\(c_1\\) and \\(c_2\\). Hereditary properties with the speed slower than factorial are surprisingly well structured.    The situation with factorial properties is more complicated and less explored, although this family includes many properties of theoretical or practical importance, such as planar graphs or graphs of bounded vertex degree. To simplify the study of factorial properties, we propose the following conjecture: the speed of a hereditary property \\(X\\) is factorial if and only if the fastest of the following three properties is factorial: bipartite graphs in \\(X\\), co-bipartite graphs in \\(X\\) and split graphs in \\(X\\). In this note, we verify the conjecture for hereditary properties defined by forbidden induced subgraphs with at most 4 vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q640407$AE85AD1E-1C85-410D-A87A-54258F0CFDB7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640407$61E90D1F-C89B-4B84-9364-3A0213A0E362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640407$DAE3EBF8-77A9-4F65-84EB-BFA5F424E237","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e4f129123b524eff93b24fb3750d244ed320aec","datavalue":{"value":"5960019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640407$87A79318-3D43-47ED-BB55-F8DF2418BFC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c206c2787904fb86f4cb4565dce6cf245bac10ca","datavalue":{"value":"hereditary class of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q640407$420EE0D7-0753-4C4F-8CF0-9ECCC8A4897A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd470c0c66c11b2de482db16ed67be2daf23abb0","datavalue":{"value":"speed of hereditary properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q640407$F951E8C7-FDC3-43DE-AE69-D993CC50745E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"896c54b5332b344459fd92295a195ae204825dd8","datavalue":{"value":"factorial class","type":"string"},"datatype":"string"},"type":"statement","id":"Q640407$BB8FEF11-1884-449F-A93C-1A30070E83FE","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":"Q640407$3EE45265-7E35-4808-B5C6-AE406C85C8AC","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"1773c013b59b7257b02a3690e4f71efab130af2f","datavalue":{"value":"bafkreida62yq47fe5eqr22dpvfl4yrogolabqctiscbscp6pn5i3ygwok4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640407$76C96C20-6348-4A8E-9E58-7AB2D3AF538D","rank":"normal"}],"P1643":[{"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":"5d4813978f947eaff44e3bbd6adc22d288704696","datavalue":{"value":{"amount":"+0.8688820600509644","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":"Q640407$12E06E18-EB45-4485-BE98-7E0B41939B5C","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":"5d4813978f947eaff44e3bbd6adc22d288704696","datavalue":{"value":{"amount":"+0.8688820600509644","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":"Q640407$D1A380A6-F260-491E-90DA-1DF442B4A7A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23c788cfbaad672e2936678d888b3a546d30b172","datavalue":{"value":{"entity-type":"item","numeric-id":5421808,"id":"Q5421808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9585cb9494283033cc450efd33fd0eba74810c07","datavalue":{"value":{"amount":"+0.8392711877822876","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":"Q640407$4BC0B7C5-DB0A-4697-8A9F-E3E1DA87241D","rank":"normal"},{"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":"2f555a525b3c3b8ff1727c1cf69227be0cb57388","datavalue":{"value":{"amount":"+0.8315147161483765","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":"Q640407$B9464C90-FCE7-42A1-974D-10A1EBD544D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2933591deb4d2730abee7f5b4e1401d3bfefeed","datavalue":{"value":{"entity-type":"item","numeric-id":412246,"id":"Q412246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c6ce22e8e158e8532f7876771a65b38b2df78d6","datavalue":{"value":{"amount":"+0.8296056985855103","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":"Q640407$5ED19C6D-8190-4BDA-9942-794FB2DD00DD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the speed of hereditary graph properties","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_speed_of_hereditary_graph_properties"}}}}}