{"entities":{"Q1097902":{"pageid":1108654,"ns":120,"title":"Item:Q1097902","lastrevid":70305858,"modified":"2026-04-13T13:52:33Z","type":"item","id":"Q1097902","labels":{"en":{"language":"en","value":"Greedy posets for the bump-minimizing problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035885"}},"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":"Q1097902$E539BF32-7E0E-4DB7-B1CD-75F6E7FA01D3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a742bad651ca5496f3a8a81b9aaac44aec008759","datavalue":{"value":{"text":"Greedy posets for the bump-minimizing problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097902$665DAAA0-47AE-481B-B462-2599E0AD0CD6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a0a06e109a84a34f9be348fe30085e5d31d9821c","datavalue":{"value":"0636.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097902$38B18DE5-193D-4FC3-BCBE-C4FE88356758","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f6f57c5e4894996f0c7176cf6d5482a064d50434","datavalue":{"value":"10.1007/BF00337888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097902$96F7BD4E-55C8-4B56-9D91-1F07CB134BEA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"717d1316694a09b72da7b907a09f6b8bfbc28007","datavalue":{"value":{"entity-type":"item","numeric-id":603887,"id":"Q603887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$439CA102-839A-4012-ACA7-19D44D9590E7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$C49EF025-3E69-4FB4-B855-6A54C2EB5E95","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1097902$8DDEE259-4981-4C5A-8919-82921C9B3A06","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3adf2fce33c085e949b34f085b549d53da87ea45","datavalue":{"value":"Given a finite poset P and a linear extension \\(L=\\{x_ 1<x_ 2<...<x_ n\\}\\), a bump \\((x_ i,x_{i+1})\\) occurs if \\(x_ i<x_{i+1}\\) in P (no covering implied). In contrast, a jump \\((x_ i,x_{i+1})\\) occurs if \\(x_ i\\nleq x_{i+1}\\) in P. Notice that bumps and jumps are complementary notions once we observe that \\(x_ i>x_{i+1}\\) is always excluded in P because of the choice of numbering for the vertices. Thus, if \\(b(P)=\\min \\{b(L)/\\) L is a linear extension of \\(L\\}\\), where b(L) is the number of bumps of L (relative to P), then determining b(P) amounts not only to minimizing bumps in extensions (or schedules) but maximizing jumps, whereas determining the jump-number is equivalent to the problem of maximizing bumps.    In terms of bumps, L is greedy if \\((x_ i,x_{i+1})\\) in L implies \\(x_ i<x_ j\\) in P whenever \\(i<j\\). Greedy posets in this setting are precisely those for which every greedy linear extension has a minimum number of bumps. In this paper the author shows that Thm 3: a poset P is greedy and \\(b(P)=0\\) iff for every x in \\(C_ k\\), where \\(C_ k=\\{x|\\) x is minimal in \\(P\\setminus C_{k-1}\\}\\), \\(C_{-1}=\\emptyset\\), \\(0\\leq k\\leq n\\), \\(C_ 0\\cup...\\cup C_ n=P\\), the following properties hold:  \\[  (i)\\quad | \\{y\\in C_{k+1}| y>x\\}| \\leq | C_{k+1}| -1  \\]   \\[  (ii)\\quad | \\{y\\in C_{k-1}| y<x\\}| \\geq | C_{k-1}| -2,  \\]  with equality holding only when \\(k>2\\), and if for every \\(y\\in C_{k-1}\\) such that \\(y<x\\), \\(\\{z\\in C_{k-2}| z<y\\}=C_{k-2}\\). Based on this very useful result and a decomposition theorem due to Al-Thukair and the author (Thm 2: Let P be a greedy poset with \\(b(P)=k\\). Then \\(P=Q_ 0\\oplus...\\oplus Q_ k\\) (\\(\\oplus\\) linear or ordinal sum) where \\(Q_ i\\) is greedy and \\(b(Q_ i)=0\\) for every \\(i\\in \\{0,...,k\\})\\), it follows that there is an effective characterization of greedy posets.    The characterization of the greedy posets for the jump-number problem is different and, as the author among others has demonstrated in a great variety of papers, a problem which is apparently much more difficult to handle. Comparing the definitions of bump and jump against the background of arbitrary posets in their astronomical variety, this may not seem too surprising upon consideration.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097902$AA1C4AFB-F34F-4108-B0F5-8BBE8399A6BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097902$9EC3E594-BD21-4BEC-91C8-67860ED83253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097902$011822A7-3C6A-413B-B6EB-EC82DD47CEB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097902$54AFA71F-9AB8-4778-906A-5E003DFA68B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be1e6329545ecce08db0bcfb2d21d9f78db319f0","datavalue":{"value":"4035885","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097902$BBD0DCD5-9E27-4B74-A38F-DB937B1DE2EE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6575997fe34f5b3b31e4bef320f03458bbb69c1a","datavalue":{"value":"finite poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097902$3943B860-F180-41B9-9739-4E64BD3E3295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"311b860a0597dd249b584149fd2ab2e7e5bfa5ec","datavalue":{"value":"linear extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097902$9B1C21B5-8885-4004-AF21-248B393CCBBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"287c96936542f8973f641ff1291a0758a0fa0d8d","datavalue":{"value":"bump","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097902$A66E9553-E089-4DDB-A95A-86999DCA597B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79c86270e2052af073ed93b4b537376e78238196","datavalue":{"value":"jump","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097902$DF63C873-B264-4A1C-98B5-D2648A6DC3AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42b19506d61017ffef67952613b4a41e0975a521","datavalue":{"value":"greedy poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097902$CE15B6FD-8B7E-44BF-9363-1FDE70BD4915","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b626688718ca3d61fce8479b1c17fa40d92d8dda","datavalue":{"value":{"entity-type":"item","numeric-id":233347,"id":"Q233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$31F352A9-1FC2-48B0-B4F6-748C1E04F2D5","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":"Q1097902$44F4E7E9-FCBA-411C-98B0-A45804B3DC51","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e962f046ef41f34e1e9feff88168c6a946752ad","datavalue":{"value":{"entity-type":"item","numeric-id":1092935,"id":"Q1092935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$BB02DB80-1AAF-43C6-80E7-CC89F2BDE371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"817bfd57fb9a66f0cba09e73dc428065f8c2dafb","datavalue":{"value":{"entity-type":"item","numeric-id":3890731,"id":"Q3890731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$DE21A96B-0B66-458D-ADFB-CE65BE32B811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89d18f16e8c7f370dfcb7fb9d88b670fd5f0dc27","datavalue":{"value":{"entity-type":"item","numeric-id":791537,"id":"Q791537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$919BFCFD-45E2-4BCD-87A9-6A5E93B4C0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"433aacb3b753ddf861d4b3d2e5750f83f114a9ac","datavalue":{"value":{"entity-type":"item","numeric-id":4200070,"id":"Q4200070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$77AF0427-60C9-43D0-B68C-BC46F37BFEFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"264e1cc4d5b5edaf92740589f5202d1c1d957871","datavalue":{"value":{"entity-type":"item","numeric-id":762183,"id":"Q762183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$72E1F0E9-E3A9-448E-8E84-EB9436F1D095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8553feea678bc899d05f5a147512f8d0b1b46f91","datavalue":{"value":{"entity-type":"item","numeric-id":3960747,"id":"Q3960747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$F0BC4E9F-1A29-407B-8F87-CEDDF6C35EBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f159aacfddbc201f6b79ecf804a940116897f8f","datavalue":{"value":{"entity-type":"item","numeric-id":1061150,"id":"Q1061150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$83C1224F-12FA-4E1A-87DE-D6398164A50F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c89eaca0c637703f9ae0cc66672c6857df95bf8b","datavalue":{"value":{"entity-type":"item","numeric-id":802585,"id":"Q802585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$47523D53-6146-4C0D-B6DA-88763DACA23D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b944833fa97de961f22b519a3ec130cc1d9cba93","datavalue":{"value":{"entity-type":"item","numeric-id":1077441,"id":"Q1077441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$2F984D77-AF2A-4472-A5BE-A64498A30E01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9e52059a589250b5c3bf927a52af00cebfb990d","datavalue":{"value":{"entity-type":"item","numeric-id":3665161,"id":"Q3665161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$FF6D8711-19CD-4E58-9682-610559F765F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886ba032e540aea708d21bd27fbc92799a765ca4","datavalue":{"value":{"entity-type":"item","numeric-id":3686754,"id":"Q3686754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$CEF67DCA-E5CD-436B-BB81-DC561E138123","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d4c3394fe33a803d44b9613be7e42b3f4c68ee4","datavalue":{"value":{"entity-type":"item","numeric-id":3674720,"id":"Q3674720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$FC868B41-D88B-4DE5-9E49-390C62060483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5805238c0fe4905dee22c3e5f8aa9b182c98878a","datavalue":{"value":{"entity-type":"item","numeric-id":1087566,"id":"Q1087566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$9FAED2F7-FCF6-4772-9868-5C47ABCF6D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"573d580db937b144c4e3c67d0ca4132151edf27d","datavalue":{"value":{"entity-type":"item","numeric-id":1821122,"id":"Q1821122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$CA81CFC3-78ED-4D39-8394-A3F1C78BBC37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d932d2dd9959d01e52a083bc9b3ddf17f04db94","datavalue":{"value":{"entity-type":"item","numeric-id":1092072,"id":"Q1092072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$04EF83FE-E593-4FAB-9CBB-BB182B77F6F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d5b3cac9d7fa9b0244c1deee93551fd12a68a92","datavalue":{"value":{"entity-type":"item","numeric-id":3676161,"id":"Q3676161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$DF02520D-6E85-4BF0-872A-513B24E2A871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e583c6fcdec1f2af46629c50832b9198e1a4430b","datavalue":{"value":{"entity-type":"item","numeric-id":1057289,"id":"Q1057289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$132844C2-E4D1-4CF4-AB52-48464EE3703F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de15d26ad6d10743bee1267fea360305492a057e","datavalue":{"value":{"entity-type":"item","numeric-id":1114719,"id":"Q1114719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097902$6B4D231B-B138-4639-9249-97647F1C3EF8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8bcae5f6aa7c90f998aad975158d60e14f638ade","datavalue":{"value":"https://doi.org/10.1007/bf00337888","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097902$B052BA4C-1D4C-4DD3-9BBA-8BDB391766B8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"61b09cb6792e5ff6ffd7aa8958b563abafb6f743","datavalue":{"value":"W2033549036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097902$54823BCC-E27D-4774-9FAC-41372113164B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed7a26f1e23ac2f3ea5b69e922109d096a867a80","datavalue":{"value":{"entity-type":"item","numeric-id":1092935,"id":"Q1092935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37c9e89ba739bfabf86bd6c8acfe6dbc9e8cb995","datavalue":{"value":{"amount":"+0.9428046941757202","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":"Q1097902$12C86FCA-B4A2-4F66-A954-C43786B67B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51eeff64f65f4d72594430123ac56a95692418b8","datavalue":{"value":{"entity-type":"item","numeric-id":4697213,"id":"Q4697213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1c9ee8e4f3bc1113d70b054469e63e2479cae9d","datavalue":{"value":{"amount":"+0.8563787341117859","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":"Q1097902$2E28BBF6-209A-46D7-A1CB-C3AEA450FC2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5420ef410220cf74704bda451d24b8a0dee7e471","datavalue":{"value":{"entity-type":"item","numeric-id":1077441,"id":"Q1077441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4f0816af07f8b35f3d6721f4d5936d4dee5cbf9","datavalue":{"value":{"amount":"+0.8533008098602295","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":"Q1097902$EBF44DA6-F0D7-4964-9CBA-4EFC36063030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23314e29c87e3498a125fa1e1e58c0163e9977f5","datavalue":{"value":{"entity-type":"item","numeric-id":1111581,"id":"Q1111581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46a933ce892f3483b38067b2a8ec82c8fce4dab3","datavalue":{"value":{"amount":"+0.8359168171882629","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":"Q1097902$31C984FB-B056-4191-B96F-20CF3D3A8B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b624680d8fc574517d233b9fe063f2924eed5ebf","datavalue":{"value":{"entity-type":"item","numeric-id":1114719,"id":"Q1114719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71eb0e296fd69562026d1874212925f0679c4c77","datavalue":{"value":{"amount":"+0.824568510055542","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":"Q1097902$477EC31B-D204-414F-9013-B0FBA0D69316","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Greedy posets for the bump-minimizing problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Greedy_posets_for_the_bump-minimizing_problem"}}}}}