{"entities":{"Q1823262":{"pageid":1834004,"ns":120,"title":"Item:Q1823262","lastrevid":69039606,"modified":"2026-04-13T03:57:35Z","type":"item","id":"Q1823262","labels":{"en":{"language":"en","value":"Graphs with a small number of distinct induced subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4114691"}},"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":"Q1823262$6015DD5D-F3B8-4796-B3EB-30E09FA3B0E0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0eb5f5773127b5d014351014c47aff8072c04d89","datavalue":{"value":{"text":"Graphs with a small number of distinct induced subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1823262$742682F1-8629-4C66-AA21-F8CEEAB36203","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e6f0aa66faffd339c020e4e0199a3046efee1779","datavalue":{"value":"0681.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823262$DD4595DD-6911-4825-B4E0-19F12F677B5D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ab48dbf44b14b01d3802ad9f9c0da966fc15e545","datavalue":{"value":"10.1016/0012-365X(89)90074-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823262$751F10A9-DE27-4EFE-AB7E-C3F0C41245B9","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":"Q1823262$26B4F5E3-74D4-44A3-89B7-C232F0DAF93A","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":"Q1823262$B030B729-3608-4DD8-A337-BD3037EB7BB0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823262$AA8AFC2C-AB17-4F6C-AAED-08492C8D2C3C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1823262$9570A93D-0F96-4AD9-8C3E-350E4E964A8A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f155c6ee7d9a91750d7fad72625f215c762614e3","datavalue":{"value":"Let G be a finite, simple and undirected graph and i(G) denotes the total number of isomorphism types of induced subgraphs of G. An induced subgraph of G is called trivial if it is either complete or independent and let t(G) denote the maximum number of vertices of such a trivial subgraph of G. By Hajnal the conjecture is formulated that if G is a graph on n vertices and \\(i(G)=o(n^ 2)\\), then \\(t(G)=n-o(n)\\) holds. The proof of this conjecture is the main result of the present paper (Theorem 1.1). This proof is a very lengthy one and requires two steps which consist of results on graphs with large trivial subgraphs and on graphs without large trivial subgraphs; the second step is the more difficult and the more important one regarding to Theorem 1.1. For \\(i(G)\\leq \\epsilon n^ 2\\) and \\(t(G)\\geq (n-\\epsilon^*)\\cdot n\\) are given the two estimations \\(\\epsilon <10^{-21}\\) and \\(\\epsilon^*=4\\epsilon\\) which are not optimal values and which can be improved. The conjecture was also proved in a stronger form by Erd\u0151s and Hajnal. Finally this paper contains some interesting unsolved problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823262$A76715CD-F7B7-4ED3-87E5-24E4D2B38529","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823262$58611711-177C-45C2-990A-0C08E5350CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823262$D05D325A-E464-4BEC-92D7-D07F64456910","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63decbd1c60292c5389ecc65c168201927f4a85b","datavalue":{"value":"4114691","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823262$3D16FD8E-BA87-431D-BE62-CC56AF0E7CF0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7436405e1b5fb777d20b1edc84fa8075e64f3d83","datavalue":{"value":"isomorphism number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823262$46947DB0-0C5A-455E-8582-CCB1C7A11774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dd0d7043066fc18c97c64cc2373bc266c0fadc1","datavalue":{"value":"stable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823262$D784FAA7-A5D8-426D-BFBD-E8CA32808884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d75d0a2eadc18098a45986dbd49fc4b962c1e3a","datavalue":{"value":"independent set of vertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823262$A8CE6F31-BFBC-4F4A-8FA3-E96E0126335C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823262$F82318B5-21FE-436A-BCC4-510BFAF72DA1","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":"Q1823262$6ABFF519-A69B-4F7F-BCDD-3D299E55C51F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9edecb511440383399e02e73639f3f749f79ed35","datavalue":{"value":{"entity-type":"item","numeric-id":5512798,"id":"Q5512798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823262$65D54CBE-7DB3-43DB-A539-1D7B4A7F84CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a59347f73363b99fbc0fc253b8806d6552a0453","datavalue":{"value":{"entity-type":"item","numeric-id":4074927,"id":"Q4074927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823262$3652BC6F-EBFD-4A91-A940-43861141B41A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37b6cf6d905f6b5b0471ecba9cd20128b8c53455","datavalue":{"value":{"entity-type":"item","numeric-id":804596,"id":"Q804596"},"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":"Q1823262$BC5F0D21-DC07-4631-8B23-E49CBAA2822C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39ad1cb4de6af1453d99203d028e201e2de06787","datavalue":{"value":{"entity-type":"item","numeric-id":1117948,"id":"Q1117948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b6359f2ae76bba268fd82d8b0238e422603db34","datavalue":{"value":{"amount":"+0.8437024354934692","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":"Q1823262$82778788-C384-420E-952B-783813033345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df2f417061e309c70b8b7cd851eb6a474f93bccd","datavalue":{"value":{"entity-type":"item","numeric-id":3608312,"id":"Q3608312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d712161c4f07bbe4a0861320366f47545a09e3c","datavalue":{"value":{"amount":"+0.7927649021148682","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":"Q1823262$35B5FA68-2BB7-4A9F-86D0-0F6FE4181744","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":"03d37ceeeb526f6d2bb9499e832075979f842168","datavalue":{"value":{"amount":"+0.7925708293914795","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":"Q1823262$37707767-32B3-4A83-81D6-391B5FD3AEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af1f40b2c4aeafd41084dc12113c733ef35aa3e5","datavalue":{"value":{"entity-type":"item","numeric-id":5454277,"id":"Q5454277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79babbdc50069fed62398c79188db836cd05b8e7","datavalue":{"value":{"amount":"+0.7925221920013428","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":"Q1823262$37961B3D-6594-45CD-8AFF-381B6046D209","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs with a small number of distinct induced subgraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_with_a_small_number_of_distinct_induced_subgraphs"}}}}}