{"entities":{"Q804596":{"pageid":806444,"ns":120,"title":"Item:Q804596","lastrevid":49504444,"modified":"2026-01-07T09:05:50Z","type":"item","id":"Q804596","labels":{"en":{"language":"en","value":"Ramsey graphs contain many distinct induced subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4202301"}},"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":"Q804596$4B435B0E-19B1-4B0A-8892-C57A9A0C5CF4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5fd912b79a302dc9e17a779c33a1a7a72b962d44","datavalue":{"value":{"text":"Ramsey graphs contain many distinct induced subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q804596$D3F1366B-F304-4B11-96EF-B72B61419BA6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f92ed2030555f6db215abf862ecd75450922650","datavalue":{"value":"0728.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804596$F1FB6F49-688E-4838-AC06-EF81B19499FE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ffc9e6a19a2fbf6b704e6258fd99d34bc87e0af4","datavalue":{"value":"10.1007/BF01789457","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804596$4EB52D6C-0827-4724-A4E9-9E8E5C37D860","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$F448BB49-42B0-4EAB-B478-79F62521890C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q804596$623C05E8-BC0A-4B5C-A3F5-AD4E42EF3734","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e4bbff5582ce6b6b9731b4a908743d118eb19e2","datavalue":{"value":"Let G denote a finite, simple, undirected graph, and let i(G) denote the total number of isomorphism types of induced subgraphs of G. An induced subgraph of G is said to be trivial if it is either independent or a clique. Let t(G) denote the maximum number of vertices in a trivial induced subgraph of G. One of the well-known results in Ramsey theory is that t(G)\\(\\geq (1/2)\\log n\\) (where n is the number of vertices in G and log is the logarithm to the base 2). The graphs G for which t(G) is very small with respect to n are sometimes called Ramsey graphs. The main result of this paper (Theorem 1.1 below) shows that these graphs behave like random graphs in that the number of distinct induced subgraphs is large. Theorem 1.1. For any graph G on n vertices with \\(t=t(G):\\) \\(i(G)\\geq 2^{n/2t^{2O\\log (2t)}}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q804596$C869B7E7-94D8-4ADA-AD3D-1D6AFCFF8276","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f44ccef182344d8f5e725874f8db6776f4090ec1","datavalue":{"value":{"entity-type":"item","numeric-id":323047,"id":"Q323047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$E835C789-663E-422E-81EB-154F053DC045","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804596$8091B0DA-9D8C-4A94-92DF-45C636E1037B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cc89ae882ca65dca6bc63a60436b8def4c96fa8a","datavalue":{"value":"4202301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804596$E87363E1-DEF4-4FA9-824E-96F3217CAC6E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d2bafd2fded13d40803bb553b449b4ab90b8fa6","datavalue":{"value":"number of isomorphism types of induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q804596$B6E0B290-15B0-413A-A153-96A72A6163FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8779bd443f3bc54c1af1cfede1cd705c6508ea62","datavalue":{"value":"maximum number of vertices in a trivial induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q804596$3DDEFBBE-5CDC-45B5-88A0-C74DF6C4B089","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea33b309306e49b597817f466193bd42e7d9d48d","datavalue":{"value":"Ramsey graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q804596$387A365A-A1EF-4A91-BD0F-7AC9F28D164C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$5C7EF927-4A6A-4D64-9EDD-9907A70A8667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee49ae8f184177da0258b703b63e44e5249936ca","datavalue":{"value":{"entity-type":"item","numeric-id":1226099,"id":"Q1226099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$D1F3A2B6-AA8D-43C5-BA67-8A0173FC64EC","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":"Q804596$01F82DF0-8B0E-43CB-BF4D-C7016C670C4D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0c1e508a7a767d5f28b0d96be280ab85d97d321","datavalue":{"value":{"entity-type":"item","numeric-id":3970897,"id":"Q3970897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$241A7E37-E759-4C19-A227-35F1866D5806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f695bb473050c155f5a480fc79f69cf00edd6099","datavalue":{"value":{"entity-type":"item","numeric-id":1823262,"id":"Q1823262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$4FE96875-3B7A-485E-A107-32034AD4400C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fca512bd62ef81317baaf07336a09e35ab66e1e","datavalue":{"value":{"entity-type":"item","numeric-id":5789964,"id":"Q5789964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$051D6445-19A2-4F75-9D7B-952FF0C0F5EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dea6ee8014164ea0b4ab25365a13b2deaaced58b","datavalue":{"value":{"entity-type":"item","numeric-id":751670,"id":"Q751670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$25ECE0A5-B1CB-4149-AB55-E3725C603BC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1816840e3810158a365583145caabbefd138ed2a","datavalue":{"value":{"entity-type":"item","numeric-id":1117948,"id":"Q1117948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$2619C1E3-DE19-476F-AF26-BA568E9C36E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ec854804833f468ba7b791a0729e9f4ac96005c","datavalue":{"value":{"entity-type":"item","numeric-id":3656899,"id":"Q3656899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804596$94C34283-601D-4667-B599-96183191EA10","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"105bae939bdf3adb26215509c1449e715d4b8957","datavalue":{"value":{"entity-type":"item","numeric-id":3552509,"id":"Q3552509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d60ad16af42df5fb65f2cca18f04620a677227e0","datavalue":{"value":{"amount":"+0.8860562443733215","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":"Q804596$502E03D9-03FE-4B16-99C9-72A7A25F298C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16bdeef58811c1477fa276e9874c2771ac111565","datavalue":{"value":{"entity-type":"item","numeric-id":5240169,"id":"Q5240169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dfc361b9bbe3fe1cc81a227ef3579ba1d4783eb","datavalue":{"value":{"amount":"+0.8646981716156006","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":"Q804596$C7487CF2-A05F-4E05-92ED-5DD88937A865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5dc43fb9d1c74e99a6c62e20ff3671e0bbb1688","datavalue":{"value":{"entity-type":"item","numeric-id":5108320,"id":"Q5108320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab6bbf1bfbcb1e7ecdd66b087e1c7e184d5411a7","datavalue":{"value":{"amount":"+0.8527459502220154","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":"Q804596$A7938102-7A81-4798-8F23-A8BC77B5C57F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef0159a1555c5f1c4a92ca4334dab06d0c809409","datavalue":{"value":{"entity-type":"item","numeric-id":1823262,"id":"Q1823262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5a6bce828f96b57b7c34788020629d767c98ed4","datavalue":{"value":{"amount":"+0.85089510679245","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":"Q804596$05036636-F412-4CD0-A946-2C3F0F72BEE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3425cf40c09aec751b6940b0550c18cd708ed238","datavalue":{"value":{"entity-type":"item","numeric-id":885296,"id":"Q885296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b50f80bee6ddfb85613051ac9fc750b8992acc2","datavalue":{"value":{"amount":"+0.847130537033081","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":"Q804596$92D162A3-CDF1-470C-8B2D-CF45F06B6252","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:804596","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:804596"}}}}}