{"entities":{"Q793731":{"pageid":795579,"ns":120,"title":"Item:Q793731","lastrevid":48707962,"modified":"2026-01-05T16:31:43Z","type":"item","id":"Q793731","labels":{"en":{"language":"en","value":"A new short proof for the Kruskal-Katona theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3857117"}},"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":"Q793731$570D16AC-47B6-440E-93FF-BEB6FE5DACA1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"55cccd9d33917c3e4eaec28a2db72ccc1f118a88","datavalue":{"value":{"text":"A new short proof for the Kruskal-Katona theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q793731$812B93D8-5905-41D8-A9ED-01F4F2CBBBCB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dc9e0a2b3e3570fab2800a9b3dce21201d467902","datavalue":{"value":"0539.05006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793731$279B45F9-DC59-482F-8D54-802B3309B9C9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6c987f38183121acd21cffd52a7b2464e7a47726","datavalue":{"value":"10.1016/0012-365X(84)90193-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793731$AD434F28-41F9-4700-AD2C-06FCD151797A","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":"Q793731$BBBADBBE-086E-4DE7-9238-BF6F715D57C4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q793731$8612D29B-8128-47E7-B4C9-CECE4802327B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b24d6e13c694b66ffa72d1159ea2d2339e4705e7","datavalue":{"value":"Let \\({\\mathcal F}\\) be a family of subsets of an n-element set X. Define \\(\\Delta\\) (\\({\\mathcal F})=\\{E\\subseteq X\\); for some \\(F\\in {\\mathcal F}\\), \\(E\\subseteq F\\), \\(| F-E| =1\\}.\\) The well-known Kruskal-Katona theorem states: If \\({\\mathcal F}\\subseteq\\left( \\begin{matrix} X\\\\ k\\end{matrix} \\right)\\), \\(| {\\mathcal F}| =m=\\left( \\begin{matrix} a_ k\\\\ k\\end{matrix} \\right)+...+\\left( \\begin{matrix} a_ s\\\\ s\\end{matrix} \\right),\\) then \\(| \\Delta({\\mathcal F})\\geq\\left( \\begin{matrix} a_ k\\\\ k-1\\end{matrix} \\right)+\\left( \\begin{matrix} a_{k-1}\\\\ k-2\\end{matrix} \\right)+...+\\left( \\begin{matrix} a_ s\\\\ s- 1\\end{matrix} \\right).\\) \\textit{L. Lov\u00e1sz} [Combinatorial problems and excercises (1979; Zbl 0439.05001)] proposed the following slightly weaker form of this theorem: Suppose \\({\\mathcal F}\\subseteq\\left( \\begin{matrix} X\\\\ k\\end{matrix} \\right)\\), \\(| {\\mathcal F}| =m=\\left( \\begin{matrix} x\\\\ k\\end{matrix} \\right).\\) Then \\(| \\Delta({\\mathcal F})| \\geq\\left( \\begin{matrix} x\\\\ k-1\\end{matrix} \\right)\\) where \\(x\\geq k\\) is real. In this note the author presents a very short proof for both these theorems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q793731$143D1973-DB50-4898-B23E-BCC67C8EC28B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793731$89452850-F774-4FF1-877B-F5B58F01B4D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"da00c812255bd7f02dddc14c65a56e042cf0446e","datavalue":{"value":"03E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793731$81C014BC-0A8D-47B3-AC60-B9B3D6A044DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fef8696489047f5b81eda320ad959cbafeb6a3ff","datavalue":{"value":"3857117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793731$EFF764F8-AED2-4F17-8337-8A038AF0B017","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f08afcdf058072e0491babb026633cefd7c28b55","datavalue":{"value":"Kruskal-Katona theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q793731$668C9110-7094-41F3-A3F9-1E5D0ABE9E05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09564715942b790a3f101f69615baae04641b148","datavalue":{"value":"family of subsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q793731$0FEA887B-1625-4D36-8E65-9379A0DF0BE1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"474b63f13ec1c96912ef94cce56a54863e3a574f","datavalue":{"value":"Q89355068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793731$DFA2468D-00EC-486F-83E8-8F73688F477E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"330058a2d277124515714c2f9b0298bfef969143","datavalue":{"value":{"entity-type":"item","numeric-id":168624,"id":"Q168624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793731$CBA80F85-8C00-454E-B69E-4B66D2170503","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":"Q793731$077F58B8-FF0C-4649-8274-4B126FB89923","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb0e2a8307868758c8cd2ab77f4a92ac09dcac71","datavalue":{"value":{"entity-type":"item","numeric-id":1845728,"id":"Q1845728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793731$0D294E76-5702-4F5B-9165-5F091FDD7FBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d96fe1377adf4bc2473cc2c298e11ba7b240673b","datavalue":{"value":{"entity-type":"item","numeric-id":4071752,"id":"Q4071752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793731$CB741D68-8B71-4AF9-9A1E-11EB4EE0D040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f452cfc46c61b9aec3f0c92cdf87b0bd8c84f73","datavalue":{"value":{"entity-type":"item","numeric-id":5726070,"id":"Q5726070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793731$1D18AC3D-BFBA-467B-A826-D2DFBCF15B4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793731$5C1A1376-0015-4FE0-BB73-C46F7FF07BA5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b3e617b5d38f65946afada6f2a73ffdb84d0193","datavalue":{"value":{"entity-type":"item","numeric-id":1073037,"id":"Q1073037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f4714cfc748907b93714797ab49a7277921a23e","datavalue":{"value":{"amount":"+0.839111864566803","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":"Q793731$8BD51BD1-BF94-4BDD-95F8-EBDF22920DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51694ee295d15c636b1d367ce5ca9c73f3fc1f02","datavalue":{"value":{"entity-type":"item","numeric-id":793732,"id":"Q793732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"164b9416ba3ef14e73a61ad30326a995bbd6c53a","datavalue":{"value":{"amount":"+0.8272281885147095","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":"Q793731$1505E595-FE51-4BD2-9AB1-D3A13985F414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35c01c7e8e8366e86a74e5eed61e30ce242428d0","datavalue":{"value":{"entity-type":"item","numeric-id":1336454,"id":"Q1336454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f938c7129ee075b7cc1be6d1d3abfbad0dff854f","datavalue":{"value":{"amount":"+0.8181307315826416","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":"Q793731$0BADE2CB-D1F6-4531-B7D3-6198E148C273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c85879c4464dfcc43046de4f18c97fd932922dc7","datavalue":{"value":{"entity-type":"item","numeric-id":1584224,"id":"Q1584224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43a9e0818010e3b736ded42e9320c3c409a386cd","datavalue":{"value":{"amount":"+0.8089891672134399","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":"Q793731$76943512-B55D-46AE-AE04-588B761A15D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3f1ae6fc25d35b68fb46eeb29f08766bccd2925","datavalue":{"value":{"entity-type":"item","numeric-id":2910934,"id":"Q2910934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"935275038c6438242ccda8013b003bd273ad86dd","datavalue":{"value":{"amount":"+0.8080869317054749","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":"Q793731$DBFDBD4C-F89B-4353-B28E-3FA5F2018E8F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:793731","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:793731"}}}}}