{"entities":{"Q2409841":{"pageid":2420584,"ns":120,"title":"Item:Q2409841","lastrevid":57901611,"modified":"2026-04-03T00:37:58Z","type":"item","id":"Q2409841","labels":{"en":{"language":"en","value":"Smaller subgraphs of minimum degree \\(k\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6791424"}},"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":"Q2409841$1911C99F-F1B4-487D-B132-1736DA30795E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee702f943719a4352ba238febf6d269e8f9ab0fb","datavalue":{"value":{"text":"Smaller subgraphs of minimum degree \\(k\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2409841$288A232E-BACF-4597-8D08-683901E19397","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b6d0522bdd5681cee0b40a989b5a6f0f658d0a4","datavalue":{"value":"1375.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409841$2938E11F-B8C3-4881-9A69-81E8B14A9B76","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc4d66bfe8a3b8816a49b3ee57d66f387a2d633b","datavalue":{"value":{"entity-type":"item","numeric-id":350718,"id":"Q350718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409841$2D84C188-D6B4-402D-A9B1-039E4D3B67D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d48de915aa01a02038a0ae1831e2489aecfb3653","datavalue":{"value":{"entity-type":"item","numeric-id":1742760,"id":"Q1742760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409841$7A5D6022-EBF0-4476-A423-FBF8EE51024B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ea66980f249afa49e0a3f1803e49954a74fc2c2","datavalue":{"value":{"entity-type":"item","numeric-id":322226,"id":"Q322226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409841$0BB8A460-1A41-46A7-865C-9302BFD368AA","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":"Q2409841$BF28507F-E539-4F8C-9791-9689F859E083","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6c5297401e02788bd3f4d1f30d634c2fb25880e4","datavalue":{"value":{"time":"+2017-10-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2409841$6DB1F1AE-9E83-4CE8-82D9-6690C9EC0787","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"41c955498f7e306b2bf6513382003133a6a53e10","datavalue":{"value":"https://arxiv.org/abs/1703.00273","type":"string"},"datatype":"url"},"type":"statement","id":"Q2409841$4D4C43AC-807B-4A3D-925F-86AECBB31E0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"0aa8d5adb32bc566549b1b9a629781c3018dcbd6","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p9","type":"string"},"datatype":"url"},"type":"statement","id":"Q2409841$93067076-B57C-4943-8B4A-52F5B102D87F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1acd2156c99c43a5c13785ce3238710d58af2de9","datavalue":{"value":"Summary: In [Discrete Math. 85, No. 1, 53--58 (1990; Zbl 0714.05033)], \\textit{P. Erd\u0151s} et al. proved that for \\(k \\geq 2\\), every graph with \\(n \\geq k+1\\) vertices and \\((k-1)(n-k+2)+\\binom{k-2}{2}+1\\) edges contains a subgraph of minimum degree \\(k\\) on at most \\(n-\\sqrt{n/6k^3}\\) vertices. They conjectured that it is possible to remove at least \\(\\varepsilon_k n\\) many vertices and remain with a subgraph of minimum degree \\(k\\), for some \\(\\varepsilon_k0\\). We make progress towards their conjecture by showing that one can remove at least order of \\(\\Omega(n/\\log n)\\) many vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409841$BB33D3F2-F024-4E7F-BB40-F691A44BFDCD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409841$509088E3-3EF7-4D0B-ACCC-74CF5237851D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409841$5D72B984-A5DF-4FCE-ABA9-B4E24FD4FB02","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c0bd4ad8507cbac3a3494d88bb9352871f12ef49","datavalue":{"value":"6791424","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409841$582927F2-8D5D-497A-BB87-7F220009E023","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409841$9E4E0AC6-5821-43EF-B37D-798416A77298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409841$2592DD15-9698-42E4-AA61-667D102413E8","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":"Q2409841$94BB8BC4-B523-4A65-9900-A518F8E72F56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e08f436a158b95e5a5013bc7e5fc58e281cf44fe","datavalue":{"value":{"entity-type":"item","numeric-id":4288049,"id":"Q4288049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409841$43126F7D-ACD5-4756-8B0C-A4638E0123F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a0e8040730a50f5935890d581679bf207fc519f","datavalue":{"value":{"entity-type":"item","numeric-id":750456,"id":"Q750456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409841$49C605B5-50F0-4361-827D-F16141509B14","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"2f76083fc61d4902f5689ece7dd409c33e8bf15d","datavalue":{"value":"bafkreic3y4jdpioi4wtok2ouvu724gbe4ovbu463oml6akxkd6ktakzfa4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409841$0299B6DA-3C5C-4B8C-9F0F-D17F4B9887E0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82f00662fc7ddc15a058de5475075585b63c9cce","datavalue":{"value":{"entity-type":"item","numeric-id":1633743,"id":"Q1633743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"943840773c93e6ed5d52e05599e170eb468be8c4","datavalue":{"value":{"amount":"+0.8935999274253845","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":"Q2409841$6B109816-E201-47DB-9840-9C9B89D23699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17277ec129e031f52228eaf90e0ab0237bb9c577","datavalue":{"value":{"entity-type":"item","numeric-id":750456,"id":"Q750456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"962f2e589599063b9a3a9d721755d3712d1fc139","datavalue":{"value":{"amount":"+0.864321768283844","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":"Q2409841$8F2AD477-AA5D-421C-BF40-C4E27C82AAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42f86f3c95b7c0c3beaaa6d10063e8bf01907fa4","datavalue":{"value":{"entity-type":"item","numeric-id":3728027,"id":"Q3728027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab5bb3fb01c54d31f780d499c6ec82b5e9676cdd","datavalue":{"value":{"amount":"+0.80650395154953","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":"Q2409841$45F36066-408B-4C6B-9294-1069737BB6FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e9c3476853cf5bb123c5193cd9471415011c9bf","datavalue":{"value":{"entity-type":"item","numeric-id":5284560,"id":"Q5284560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9a84f4eca45301e76d2c57e7679a41b3cdc3cf7","datavalue":{"value":{"amount":"+0.7826415300369263","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":"Q2409841$91F5781B-6C41-45E6-A825-43897C080D2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd994d8c0e84802d473bec87697308f6dd8bf662","datavalue":{"value":{"entity-type":"item","numeric-id":1815328,"id":"Q1815328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19aa9a559148c6ddef5a1700beb75ec9addedced","datavalue":{"value":{"amount":"+0.7798532247543335","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":"Q2409841$CAABAC33-CC71-4C77-9E75-582FC5DD8BF9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2409841","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2409841"}}}}}