{"entities":{"Q396846":{"pageid":398613,"ns":120,"title":"Item:Q396846","lastrevid":61621845,"modified":"2026-04-11T00:32:28Z","type":"item","id":"Q396846","labels":{"en":{"language":"en","value":"Greedy trees, subtrees and antichains"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330300"}},"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":"Q396846$D562F358-3CC1-4581-97AE-792145B427EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a355f0f8911430d0d0da535d0e6905ae54c64673","datavalue":{"value":{"text":"Greedy trees, subtrees and antichains","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q396846$FC728276-1020-426E-8943-164B73CC1245","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e250ad4c36745d4d0b8a0fcaee3a6eb7ffdd75b3","datavalue":{"value":"1295.05076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396846$D6B9D9D7-AADC-4B40-A27A-9496727C30FF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"482a50f2fb6f566c14b7f1d73b3f2eae47904aa7","datavalue":{"value":{"entity-type":"item","numeric-id":396845,"id":"Q396845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$6979BE78-E2A1-42B1-B4A6-FBFA4924513D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"72cdb3994a08adddf2003c5c8d4203b0b5449874","datavalue":{"value":{"entity-type":"item","numeric-id":260057,"id":"Q260057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$907BA5BB-7885-4FF4-92D0-27CDCACE7409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b91203c68e3451b4eff6295035ff58f17818cb2","datavalue":{"value":{"entity-type":"item","numeric-id":1028036,"id":"Q1028036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$5A90C548-179C-43E2-910E-2CD1801D183C","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":"Q396846$B863B3E0-F614-4F49-AEE0-AA86F674138D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"014386d1e7349618004d8e2aa9650d7520cb60bd","datavalue":{"value":{"time":"+2014-08-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q396846$FCB2ECB4-0573-4FEF-AD5A-EEBF04549B67","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4dcd65f876b86abe3cc546a676a1566588e5622","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p28","type":"string"},"datatype":"url"},"type":"statement","id":"Q396846$2B349340-4019-4491-93CE-CBDD5B6B99D5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"add177bb4d4b3e959064a5f182f21ab0d5ce43c8","datavalue":{"value":"Summary: Greedy trees are constructed from a given degree sequence by a simple greedy algorithm that assigns the highest degree to the root, the second-, third-, \\(\\dots \\)highest degrees to the root's neighbors, and so on. They have been shown to maximize or minimize a number of different graph invariants among trees with a given degree sequence. In particular, the total number of subtrees of a tree is maximized by the greedy tree. In this work, we show that in fact a much stronger statement holds true: greedy trees maximize the number of subtrees of any given order. This parallels recent results on distance-based graph invariants. We obtain a number of corollaries from this fact and also prove analogous results for related invariants, most notably the number of antichains of given cardinality in a rooted tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q396846$5ACAB227-2FA9-4F1E-A934-888C8472015E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396846$7E363121-DFF7-4CF9-983D-96F51D527CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396846$727C2B69-39E6-4812-BB46-56553A18F0BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d996fbbf6c7a4d0d397c86d9322c23f0ae58feba","datavalue":{"value":"6330300","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396846$9A4F7925-16F2-47FE-93E7-9413541F90CB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0675d27ab501b8612cc65e65965daaad20e54791","datavalue":{"value":"greedy trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q396846$CC923CEF-D3C5-40CE-AB37-399259B56C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d67aea78932b35b41389284d895628a7a3db6ffb","datavalue":{"value":"degree sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q396846$356E8341-1072-4CC0-9348-154A7854E42C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90af77ac698b920eceb0e62df4048a1c5c23d60d","datavalue":{"value":"subtrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q396846$FC176A5B-8260-4FEB-A0E6-9692BDF9EA37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"922c01258e140214b68568956989c4ba97b3c6f4","datavalue":{"value":"antichains","type":"string"},"datatype":"string"},"type":"statement","id":"Q396846$B76E7656-5790-4BE4-BA1D-EF74260F54F0","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":"Q396846$5B94F375-8D29-4C8A-8677-1AE02EADC805","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"becba373e8a11bccdb290c68a8e183e3fc2f9c79","datavalue":{"value":{"entity-type":"item","numeric-id":3394467,"id":"Q3394467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$63C58552-BEA6-49D7-8DAC-84E95BB0CEC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcafebe857700fea8b6b00a353b4179b659253e5","datavalue":{"value":{"entity-type":"item","numeric-id":1010854,"id":"Q1010854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$894378C3-4BAD-401E-8B30-B313F0B6551D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4298f2d5beda7c18a7b53aad4ebe58cc956c0df4","datavalue":{"value":{"entity-type":"item","numeric-id":1904390,"id":"Q1904390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$FFA64C1D-0CF9-4DFD-BFB6-DD66239F0548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e773a2e0a22c1d662277b591f5de12147a971e21","datavalue":{"value":{"entity-type":"item","numeric-id":1838491,"id":"Q1838491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$839F01FE-65A7-4E05-9E58-F4378BE0336C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbc5f7c256f97c9a41684f18843d1db40a6c9ae","datavalue":{"value":{"entity-type":"item","numeric-id":796552,"id":"Q796552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$1A5A7DCD-5F68-410E-A8AB-D41F583DF1A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f0755e44a6e3d9306456d48ead77864fbd7d3ec","datavalue":{"value":{"entity-type":"item","numeric-id":674629,"id":"Q674629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$EC385A90-0431-485C-923F-67731A72AB77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18b4b5ebe18bb54953323b54585061e8e8420c7a","datavalue":{"value":{"entity-type":"item","numeric-id":1953360,"id":"Q1953360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$00240081-8B05-4EC1-BEE7-B07D3D7322DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e7175af9a581a39801be6e49c9aaffe6154b60c","datavalue":{"value":{"entity-type":"item","numeric-id":2474494,"id":"Q2474494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$741236A0-6030-412F-A6AC-07236357CCD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8595e6202180ca8a3f981f3dc9db74cd3b94b54","datavalue":{"value":{"entity-type":"item","numeric-id":2856723,"id":"Q2856723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$3883CF61-4CE1-43C4-AA71-96470ECCE4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5a5a7e3148fe54cfed98e18dc16f71358fc11a","datavalue":{"value":{"entity-type":"item","numeric-id":1775731,"id":"Q1775731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$CB13D214-E96D-4B4F-92AB-AF83A0018890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8600ec0dfb51d1f632a20f1adc116426e7711835","datavalue":{"value":{"entity-type":"item","numeric-id":539876,"id":"Q539876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$C6B158EC-166E-403C-8AD3-0EE3E6F26B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"113f6010bcd0c9b9dccea91af952abeb18887324","datavalue":{"value":{"entity-type":"item","numeric-id":1223323,"id":"Q1223323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$EFBA5320-9F51-4A51-BC04-E25AD6890DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adba5481e88b58986960b7b6b7a9b030b9a8cc13","datavalue":{"value":{"entity-type":"item","numeric-id":2464644,"id":"Q2464644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$A41F7E58-D393-4B1B-881D-F4EED8E65C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d7da439b9a4167363a853f4989c60f12c690875","datavalue":{"value":{"entity-type":"item","numeric-id":965244,"id":"Q965244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$4A44E752-0A72-403A-8A47-4184A5C30080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"767bb08eecec0d36724953314f934dd67a673ffa","datavalue":{"value":{"entity-type":"item","numeric-id":948686,"id":"Q948686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$EAD9A2AD-8A8C-47F8-8A72-D613936A7172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"116e11f5cdc6fbab83f959965658807410b98b89","datavalue":{"value":{"entity-type":"item","numeric-id":861266,"id":"Q861266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$00E132EC-4314-46B0-A68C-9E1E2448A1A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aef30ceb4249b424cb0dd547dfd25fb72e8be9b8","datavalue":{"value":{"entity-type":"item","numeric-id":932582,"id":"Q932582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$8F0EFA71-CF15-4320-AC59-914B73343E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4ccf383939418f13e1957b9e30fa7df2e81af92","datavalue":{"value":{"entity-type":"item","numeric-id":3643759,"id":"Q3643759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$61DF6D9F-C088-4BEA-9CC6-8875C78F686E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeb26f3c23ff879af0e7c078f7857550e3f30531","datavalue":{"value":{"entity-type":"item","numeric-id":5325940,"id":"Q5325940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396846$F6F025CA-2747-4143-A113-E6C0F0D4D03C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3341dea7be8235d215f356b0fb3ec5a9dba87c89","datavalue":{"value":"bafkreid2uvp657o4y5krpmbpjl3mqqs6pen2d7ry6jihrgzo5ms2muozva","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396846$BCFCF582-25F6-4EF0-9DA8-C710E3E1A86A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0dda08d47f8655d52d49330ead81664d9747699","datavalue":{"value":{"entity-type":"item","numeric-id":2223451,"id":"Q2223451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb41e3d511561fa684bf95627174f4f07acc109a","datavalue":{"value":{"amount":"+0.8471828103065491","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":"Q396846$24D18158-1748-409F-BA72-CB133902C479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e92b4634a81a42839019d9395201d10d46d2ba2","datavalue":{"value":{"entity-type":"item","numeric-id":2856723,"id":"Q2856723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e97a734dc99928835e70a136706225fbd1b62b90","datavalue":{"value":{"amount":"+0.835658848285675","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":"Q396846$82437E7A-F20F-49B9-AA99-3B80975F742F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4623df5b22045eca4a11b0205540f066bac65756","datavalue":{"value":{"entity-type":"item","numeric-id":1953360,"id":"Q1953360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efe530a9d662ac6799f7b6f154b6bef892e36cd5","datavalue":{"value":{"amount":"+0.8147886991500854","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":"Q396846$0D99B894-13A2-4A67-B277-BBCACE5E8104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acdacd577651bf0b6a3882b62f6cb247da93c016","datavalue":{"value":{"entity-type":"item","numeric-id":1937356,"id":"Q1937356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f13007008d82cecadedca703d2cb511e02856b2","datavalue":{"value":{"amount":"+0.811316967010498","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":"Q396846$84A070D0-A81B-4ADC-9202-7BD53ACFDA9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8870ffb6027357fd3ab46a898cd37ebee0f6ea73","datavalue":{"value":{"entity-type":"item","numeric-id":3394983,"id":"Q3394983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0f888e5f818f41b58b666def8dd28c190373ee2","datavalue":{"value":{"amount":"+0.7912036776542664","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":"Q396846$5C5CC9B4-215C-416D-8326-EFF30AE13F4E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Greedy trees, subtrees and antichains","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Greedy_trees,_subtrees_and_antichains"}}}}}