{"entities":{"Q1301649":{"pageid":1312399,"ns":120,"title":"Item:Q1301649","lastrevid":68407158,"modified":"2026-04-12T23:30:10Z","type":"item","id":"Q1301649","labels":{"en":{"language":"en","value":"On an equivalence in discrete extremal problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1334473"}},"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":"Q1301649$13695E46-7FCC-4E95-B136-A64D86F279A3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"03a21528ca74e232b628cb9788293581aede76cf","datavalue":{"value":{"text":"On an equivalence in discrete extremal problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1301649$BA620073-8535-41FF-A06C-DEC4A5C8BC03","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fc793e0f078d26ab04fdfc8d6d9c9d6dacaa59fd","datavalue":{"value":"0932.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301649$54AA456A-0BDD-4766-B722-615AB47A306E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3abf4a329cdaa2c46c1984f3931ce33bf24a2005","datavalue":{"value":"10.1016/S0012-365X(99)00013-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301649$5357A3E1-739D-4ED2-87CD-838E78463D26","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":"Q1301649$D017A09E-D47F-4179-8212-3D941F9FC19D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b22f0234058b897ad308815846be004cdc7f94b2","datavalue":{"value":{"time":"+2000-03-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1301649$37B6752C-2113-4BF9-87C7-D5163B0DFA68","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e17bd0e91fc9f00a2084693456c3ea689df3ffb7","datavalue":{"value":"Let \\(G=(V,E)\\) be a finite graph. It has the nested solutions (NS) property (for \\(F:2^V\\to R)\\) if there exists a total order on \\(V\\) such that for any \\(t\\in\\{1,2, \\dots, |V|\\}\\) the collection of the first \\(t\\) elements in this order is an \\(F\\)-optimal subset, i.e., a subset \\(A\\) of \\(V\\) such that \\(F(A)\\) is maximal (minimal if we wish) among all \\(|A|\\)-subsets of \\(V\\). Having the NS-property is a common occurrence in the (obtained) solutions to several classes of extremal problems in graphs or posets (via Hasse diagrams mostly) and using this observation as a base of operations the author is able to obtain results on Cartesian-product graphs \\(G=G_ 1\\times G_2\\) in terms of results for the \\(G_i\\), \\(i=1,2\\). Thus, not only are classes of problems seen to be closely related (here: the edge isoperimetric problem; the shadow minimization problem; the maximum weight ideals in posets problem) but using a rather clever equivalence the author has produced he is e.g. able to handle the EIP-problem for \\(G=T_1\\times\\cdots\\times T_n\\), the Cartesian product of finite trees, showing that it can be viewed as equivalent (in his sense) to \\(Q=C_1\\times\\cdots\\times C_n\\), where \\(C_i\\) is the chain of order \\(|T_i|\\), i.e., a linear extension of \\(T_i\\). The key to the unscramble is the connection to posets and the MWI and the observation that in the NS-ness of the (extreme problems on) graphs Macauleyness of posets comes into play in a definitive and interesting way leading to ``solutions'' to these problems in several relevant cases.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301649$373A892C-64E9-4AD8-8340-B0F5B8FAD73F","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":"Q1301649$47DA13BD-106D-457F-8812-F01465492BDF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301649$861140BF-A0AA-4CD9-9D1B-C3E08427E580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301649$DF731893-255B-4268-8B2F-8CA1E601BD4C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5ccfdc5553b5d47b239d056d6ce477e988527d08","datavalue":{"value":"1334473","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301649$E50FEAB5-57EC-4680-A38B-817E8C5EE800","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56838317498e73183594198f81d607b510622d10","datavalue":{"value":"extremal problems in graphs or posets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301649$8566FC70-F129-4094-8ED5-644500C97DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f080b22ac194cf7585a56b63883129b1a17549b","datavalue":{"value":"equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301649$19B4E71A-CC0F-4741-B53B-F6B4244DA908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9b43ae0f190acb8d132b00fab08bb35283981fe","datavalue":{"value":"chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301649$F895E929-E18F-4656-B6A1-31388B7748B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf876d5ad6eef9728ef751040433c72acf680125","datavalue":{"value":{"entity-type":"item","numeric-id":187114,"id":"Q187114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$0D72598F-2572-4373-A128-84B3156A664E","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":"Q1301649$38DFAD05-B3D9-4521-AC14-46B963B205BB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"990aae89d59ccfd43d4ff686dbf16fc7108748c2","datavalue":{"value":{"entity-type":"item","numeric-id":1893693,"id":"Q1893693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$AB045594-9191-4144-86B0-57F88E22599A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"827971ddb0acf18031d31cffc4e727af92dcd766","datavalue":{"value":{"entity-type":"item","numeric-id":1242920,"id":"Q1242920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$429A71AD-7C16-4483-89F4-CDFC51690B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5957909e344df9fcaad75dfa3f246180768311af","datavalue":{"value":{"entity-type":"item","numeric-id":4712283,"id":"Q4712283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$D823E01B-CF45-49FD-809D-74CFD9C5AD95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa05948e8cd62d2b723343cc8fb9cb788ebca16f","datavalue":{"value":{"entity-type":"item","numeric-id":4250148,"id":"Q4250148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$82E3A1C1-9F8F-48CB-8039-0CCCE33E5A47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a235a5727604548d4191ab3a3b0fe1c32592f0a4","datavalue":{"value":{"entity-type":"item","numeric-id":4712355,"id":"Q4712355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$749087BC-A452-4E4C-8930-421CD798A5B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"936995435f8b730c65c2c1944d678924699fc387","datavalue":{"value":{"entity-type":"item","numeric-id":1181010,"id":"Q1181010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$45886B12-712D-482F-85D2-293DF48E2D5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c16a03e97ab21198aa4981dce3fe27917612684","datavalue":{"value":{"entity-type":"item","numeric-id":5579514,"id":"Q5579514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$81DE584C-F6B7-4B99-8665-06763A7119EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc7a0145a980c0d4a8a1d9acaa2d25b82b5f5003","datavalue":{"value":{"entity-type":"item","numeric-id":4338928,"id":"Q4338928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$CA81C269-6213-44D3-B4DB-C62E129D8786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dce4985f6cbf3d8009e6b46a8c38dfdc42d02e4","datavalue":{"value":{"entity-type":"item","numeric-id":5627967,"id":"Q5627967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$EC1CCA0C-0C7E-4FE1-B7E6-C4A618763660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8289d842bf7519cc14bae71e7f0a63337a163093","datavalue":{"value":{"entity-type":"item","numeric-id":3964577,"id":"Q3964577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$2DC20BDB-4938-4247-BBD6-91C9121B3640","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":"Q1301649$90305368-B88A-4EAD-A6BE-79B94EE6219D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d3f82e39132c280945a29966488439fb3e13fbb","datavalue":{"value":{"entity-type":"item","numeric-id":5870572,"id":"Q5870572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$F0508FEC-89D9-4DCF-A82D-F3597DB4187D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75e0aa33df61f842fad597cf4b3976cf9a1ad1ff","datavalue":{"value":{"entity-type":"item","numeric-id":4404912,"id":"Q4404912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301649$8C4825BF-37D1-423C-8FE2-024D4543E3F9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f32e87afa39802b0ff386183f625cfd40e99fd02","datavalue":{"value":{"entity-type":"item","numeric-id":1357262,"id":"Q1357262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"880e745ab7755ce8d3c60ead480bea9f5d4c5dbd","datavalue":{"value":{"amount":"+0.7738250494003296","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":"Q1301649$0FA12363-FAFF-42D7-B208-CDBF4B6CF592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15f5d2ea2690d7130d0ce4a58e165a1b901557b7","datavalue":{"value":{"entity-type":"item","numeric-id":1362991,"id":"Q1362991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de197d7e82a3a2dbdc3b873fe77695e0491e0a9d","datavalue":{"value":{"amount":"+0.7546567320823669","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":"Q1301649$D7299809-F377-4760-8BEF-F1F969DEFDCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a63b2843ad50dc433958bfd5b0b81f4b411205f1","datavalue":{"value":{"entity-type":"item","numeric-id":4448742,"id":"Q4448742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"193c33a7ba49b00a0de0f26b1da101d0d9ef757b","datavalue":{"value":{"amount":"+0.7501019239425659","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":"Q1301649$7AF68522-2524-480D-BF67-17D59B3D476A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On an equivalence in discrete extremal problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_an_equivalence_in_discrete_extremal_problems"}}}}}