{"entities":{"Q941369":{"pageid":943217,"ns":120,"title":"Item:Q941369","lastrevid":65538060,"modified":"2026-04-12T03:17:20Z","type":"item","id":"Q941369","labels":{"en":{"language":"en","value":"On embedding well-separable graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5321305"}},"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":"Q941369$67321541-27E0-42F1-BA9D-3E9EE108558E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"697a9cd2773b8ce643b2e22ce1dd637aaa3f81a5","datavalue":{"value":{"text":"On embedding well-separable graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q941369$BC7ED260-EF40-4D1D-A8CB-71BD6F4133D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1cf30a5cc3327c4ff22c56b2e4bc683a2d1e6d0e","datavalue":{"value":"1157.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941369$855E1F69-C0A9-4230-ABE7-B6B02027902A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1377da21651e905f48a4ad4865918cecbf085e48","datavalue":{"value":{"entity-type":"item","numeric-id":313784,"id":"Q313784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$06AD075D-F9A2-48CD-9D38-28C00E658C8D","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":"Q941369$2B281A49-59E2-40D8-BD73-9D9B6BCC503E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2bf0f0ee9c49018dff9c641c5da1a78a5da873e5","datavalue":{"value":{"time":"+2008-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q941369$A94320BB-E004-425D-ACE7-0F69A07C92D4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7dad586453bc73861fe75b725f802394e4bdcb34","datavalue":{"value":"https://arxiv.org/abs/0707.2522","type":"string"},"datatype":"url"},"type":"statement","id":"Q941369$E1A515DB-7E60-493A-925C-D400CE7330A4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05e39cf6139d4a30251b50ba20bcb3dfaa35001e","datavalue":{"value":"This paper is about guaranteeing that a given graph \\(H\\) is a subgraph of an arbitrary graph \\(G\\). The author considers graphs \\(H\\) that are ``far from being an expander'', namely \\(H\\) is well-separable if there is a subset \\(S \\subset V(H)\\) of size \\(o(n)\\) such that all components of \\(H-S\\) are of size \\(o(n)\\). Let \\(\\Delta\\) denote the maximum degree of \\(H\\) and \\(\\chi\\) its chromatic number. The author shows that if \\(H\\) is well-seperable, then for every \\(\\Delta\\) and \\(\\gamma > 0\\) there exists an \\(n_0\\) such that if \\(G\\) is of order \\(n \\geq n_0\\) and minimum degree \\(\\delta(G) \\geq (1 - 1/(2(\\chi -1)) + \\gamma)n\\), one gets \\(H \\subset G\\). This work can be considered as a generalization of Tur\u00e1n's Theorem, as well of a generalization of work by Erd\u00f6s-Stone-Simonovits.","type":"string"},"datatype":"string"},"type":"statement","id":"Q941369$302034EF-FB97-4875-A2AF-ABEC629EA1D9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$818FE655-9881-4DEB-B613-3E031FFCB5E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941369$C9522222-0B20-4937-AF62-50CAD6B46194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941369$5C93233C-B439-40B1-BAE6-A4BFD4DFF18A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f6b118431775423751e0aa69af5bf2f8d9297ab5","datavalue":{"value":"5321305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941369$B0D95496-ED8B-413D-9380-51059D9DBDDB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e87bb1aed89f5da6ee5d1aa38eb687932a17c03","datavalue":{"value":"subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q941369$E5FDCF0A-AF92-4B49-93C8-04097D18D124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b117b8630e1f61db1ab91f55745c8ad95b93513","datavalue":{"value":"well-separable","type":"string"},"datatype":"string"},"type":"statement","id":"Q941369$872F73D8-CBE7-472E-A575-13CE3EF8ACF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013a665df3872df6518b386ba286fc369d4eed69","datavalue":{"value":"extremal graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q941369$0E960243-028A-42E3-AC46-B5BE5145446C","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":"Q941369$42301E50-5371-4FCF-9307-04BEEDDF97EF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d5ac4956a49428fdffeb089e3fc88a870ea20ff5","datavalue":{"value":"W2009873575","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941369$6BD6F497-930E-4931-85A9-40D47ABA9771","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd5baa54703b928f85928158ae2dad491cdb62ea","datavalue":{"value":{"entity-type":"item","numeric-id":1196560,"id":"Q1196560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$FE66CD2A-7300-434E-943D-72B5836B1F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d02b5cfbab8c69ab36018329e3cb44e9026a1dd0","datavalue":{"value":{"entity-type":"item","numeric-id":1924126,"id":"Q1924126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$70CE629A-91D5-4245-9FE6-B51C6354078D","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":"Q941369$C57DC0D8-F5AD-4119-AEC3-1450B5DB14E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cdfea0e6cfc1bd712a7c70b0530571e7dc0f56f","datavalue":{"value":{"entity-type":"item","numeric-id":5443799,"id":"Q5443799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$EF7547C4-AE2E-420F-BD0C-78BBAC8584AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6da70f99fd4cf6ae4ab94d8010048be644fea36c","datavalue":{"value":{"entity-type":"item","numeric-id":5567712,"id":"Q5567712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$D849CB81-8576-4B13-A710-633A31E6EA82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b79004eec82002fc898d57feecbac5016d092acd","datavalue":{"value":{"entity-type":"item","numeric-id":5842850,"id":"Q5842850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$834CF4D3-30A0-4D36-8C21-AADDAFEFB401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64952174b7e458f68d238f7503791acd723ac33c","datavalue":{"value":{"entity-type":"item","numeric-id":5620621,"id":"Q5620621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$C65C6280-D83A-4B53-BC58-885F7CBF0F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36fc92558b128bc1eb971ffb301477b7654eea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4243077,"id":"Q4243077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$B0D555F6-55BE-4088-B48A-DD9B2406BB63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8619f14bf75ae0e981111cff4e1b35e041f69d58","datavalue":{"value":{"entity-type":"item","numeric-id":4862745,"id":"Q4862745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$C35DD05E-5736-43DC-82C5-739951874F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31ffcb65b5d111490042d472d548c61b4cfc45f0","datavalue":{"value":{"entity-type":"item","numeric-id":1375060,"id":"Q1375060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$F5167246-BCE6-495D-8F1F-314EE8CEA4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c7d93ddb982376b0ebbecfddc49e3e29c9816df","datavalue":{"value":{"entity-type":"item","numeric-id":4240605,"id":"Q4240605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$33B7992A-0EB6-4E4F-B19E-8C9F9C17A527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"308555f952ef3550aa5703dcf3a73e2fc609922f","datavalue":{"value":{"entity-type":"item","numeric-id":5937938,"id":"Q5937938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$61B49992-6786-4506-B8E3-A853B3097B93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a08b9faf31a5b65c606a29d3fa462024d86e61e","datavalue":{"value":{"entity-type":"item","numeric-id":2777891,"id":"Q2777891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$E3692941-4FCB-4EC9-8DC9-779146E0C8AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ed0b82ae82773b964a96367bdde8d8d4e478307","datavalue":{"value":{"entity-type":"item","numeric-id":4878666,"id":"Q4878666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$77F7247F-2F53-4924-8EFB-1235BCFA1B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"922598857b64c682415741da5fd4eb7cb848d71b","datavalue":{"value":{"entity-type":"item","numeric-id":4200109,"id":"Q4200109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$4AB78F20-2F6F-47E5-9402-EBC44F09D219","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe979badcb8bfb7a41b5de5f764eb66747617dd","datavalue":{"value":{"entity-type":"item","numeric-id":5781249,"id":"Q5781249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941369$723B571E-8909-4DF8-8563-3B792D4DB83D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8af2879eddef1b35a25725b48a85436e043d2e1e","datavalue":{"value":"10.1016/J.DISC.2007.08.015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941369$439BA1FF-AD4C-4AD4-B25A-42AFAD7DFFAD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fea3d92395398c2c1cf397aad96cf0de299dbd4","datavalue":{"value":{"entity-type":"item","numeric-id":3503507,"id":"Q3503507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f645ec73ac9df9be7cf755c7066aee1df0ceef3a","datavalue":{"value":{"amount":"+0.7572625279426575","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":"Q941369$71CDD30E-579A-48A2-9AE7-BCF310912A9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"591e15930f3e525098b05de2d94f9e935d3c3549","datavalue":{"value":{"entity-type":"item","numeric-id":3386528,"id":"Q3386528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9116d5176411a51aaea1d820c1234a0f7e76e400","datavalue":{"value":{"amount":"+0.7570996880531311","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":"Q941369$7C678D5D-1B30-4F97-8D75-8C785FBF1D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b913563cde39059f6e97298a2a824987edcc5b8","datavalue":{"value":{"entity-type":"item","numeric-id":4289355,"id":"Q4289355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"369c8f2eab8883198423b55acac247f58eb0f4ef","datavalue":{"value":{"amount":"+0.7539985179901123","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":"Q941369$26E929FE-4F92-43EB-9DCB-CB9E8361683C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f6a98bda771d74d90f9fccf7d578e499b7f816a","datavalue":{"value":{"entity-type":"item","numeric-id":3656239,"id":"Q3656239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03ba9875f680f0f68e7f9cda452d68c296713840","datavalue":{"value":{"amount":"+0.7527036666870117","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":"Q941369$F3CBFF63-4BF0-43A7-8C8E-A3AAB4EFF9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b7cc628abfcae439daf5b1c2b68656896a0dac6","datavalue":{"value":{"entity-type":"item","numeric-id":3119788,"id":"Q3119788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3c93160e7302f2d03b82c3514cc12f6ba906429","datavalue":{"value":{"amount":"+0.7525346279144287","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":"Q941369$7F46D5CB-7973-4F9E-900E-0C8BB7F8CE4B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On embedding well-separable graphs","badges":[]}}}}}