{"entities":{"Q1362991":{"pageid":1373730,"ns":120,"title":"Item:Q1362991","lastrevid":46930812,"modified":"2025-12-25T21:18:16Z","type":"item","id":"Q1362991","labels":{"en":{"language":"en","value":"General edge-isoperimetric inequalities. II: A local-global principle for lexicographical solutions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1045830"}},"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":"Q1362991$4E25DCA5-066A-4EFC-80D7-5259B897B243","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b32d55c1b8d62bbb9a1ac5436a4f928ef9d8fd4","datavalue":{"value":{"text":"General edge-isoperimetric inequalities. II: A local-global principle for lexicographical solutions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1362991$1AC4EB7C-EBA1-4A68-9DCB-B35189C590CF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3a4db3da9bacec67785539b1cd0fed3f4fd895ff","datavalue":{"value":"0878.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1362991$C96A243A-F543-4387-93F6-B065A3596E97","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a11f02928f08cada9680e0c4ddbd9f84fb4b9bf5","datavalue":{"value":{"entity-type":"item","numeric-id":833564,"id":"Q833564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1362991$91FD3806-0FA6-4B26-92E1-CB3BCBB614B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"13e78d027f9957631248b78948d4df59b38cd87f","datavalue":{"value":{"entity-type":"item","numeric-id":6481941,"id":"Q6481941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1362991$AFC86142-212A-4DBC-8709-968FFBF24F90","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1362991$4102B9EA-D506-4052-91A0-865D159D41F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"91876c0ae2fdf3d4b98e339829630a9e4f67317c","datavalue":{"value":{"time":"+1997-11-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1362991$39CAA8BB-84E2-4854-BC54-E65AFB772423","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dadcf604cdfe787b5c3cce491812d8f52069d255","datavalue":{"value":"The lexicographic order \\({\\mathcal L}\\) on a sequence space \\({\\mathcal H}^n=\\{0,1,\\ldots,\\alpha\\}\\) is defined by \\(x^n<y^n\\) iff there exists a \\(t\\) such that \\(x_t<y_t\\) and \\(x_s=y_s\\) for \\(s<t\\). There are two kinds of edge-isoperimetric problems (EIP) that can be represented as extremal problems in graph theory. For a graph \\(G=(V,E)\\), for any \\(A\\subset V\\) the sets of all boundary and inner edges are defind by \\({\\mathcal B}(A)=\\{xy\\in E:|\\{x,y\\}\\cap A|=1\\}\\) and \\({\\mathcal I}(A)=\\{xy\\in E:x,y\\in A\\}\\), respectively. The boundary-edge-isoperimetric problem (BEIP) and inner-edge-isoperimetric problem (IEIP) are defined as follows: for a given graph and positive integer \\(m\\), find a set \\(A\\subset V\\) of cardinality \\(m\\) with minimal (maximal) possible value of \\(|{\\mathcal B}(A)|\\) (\\(|{\\mathcal I}(A)|\\)).   In this paper the following problem is considered: ``Is \\({\\mathcal L}\\) optimal for an EIP in \\(G^n\\)?'' (\\(G^n\\) denotes the \\(n\\)th power of \\(G\\) relatively to the Cartesian sum of graphs.) If \\(N=\\{1,2,\\ldots,n\\}\\), for any \\(A\\subset{\\mathcal H}^n={\\mathcal H}^N\\), \\(A_T(x^{N\\setminus J})\\) is defined as \\(\\{x^J\\in{\\mathcal H}^J:x^N\\in A\\}\\) for \\(x^{N\\setminus J}\\in{\\mathcal H}^{N\\setminus J}\\) and for any set function \\(\\phi\\) on \\(2^{{\\mathcal H}}\\), \\(\\phi^n(A)=\\sum_{t=1}^n\\sum_{x^{N\\setminus\\{t\\}}\\in{\\mathcal H}^{N\\setminus\\{t\\}}}\\phi(A_t(x^{N\\setminus\\{t\\}}))\\).   The main result of the paper is the following one: Let \\(|{\\mathcal H}|\\geq 3\\), \\(n\\) be any integer \\(\\geq 2\\) and \\(\\phi\\) be any set function \\(\\phi:2^{{\\mathcal H}}\\rightarrow\\mathbb{R}\\) satisfying: I (nestedness): for all \\(k\\in{\\mathcal H}=\\{0,1,\\ldots,\\alpha\\}\\), \\(A\\subset{\\mathcal H}\\) with \\(|A|=k+1\\) implies \\(\\phi(A)\\leq\\phi(\\{0,1,\\ldots,k\\})\\); II (submodularity): for \\(A,B\\subset{\\mathcal H}\\), \\(\\phi(A)+\\phi(B)\\leq\\phi(A\\cup B)+\\phi(A\\cap B)\\); III: \\(\\phi(\\varnothing)=0\\). Then \\({\\mathcal L}\\) on \\(X^n\\) is optimal for \\(\\phi^n\\) iff \\({\\mathcal L}\\) on \\({\\mathcal H}^2\\) is optimal for \\(\\phi^2\\). (Condition I says that \\({\\mathcal L}\\) is an optimal order for \\(\\phi\\).)   Notice that this family of set functions on \\(G^n\\) includes ``boundary-edge'' and ``inner-edge'' functions. Finally, as an example demonstrating the power of this local-global principle, an edge-isoperimetric theorem for the powers of complete bipartite graphs \\(C_{m,m}\\) is given: the first segments in lexicographical order \\({\\mathcal L}\\) give optimal sets for the (inner and boundary) edge-isoperimetric problems for \\(C^2_{m,m}\\), and therefore for \\(C^n_{m,m}\\). Notice that \\(C_{m,m}\\) being a regular graph, BEIP and IEIP are equivalent.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1362991$87BF9D5D-1C05-44E4-9E6D-E1A96E380433","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1362991$20C1BECA-8805-4FFB-BC7D-5D3EBE7E22A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1362991$85E94C77-076A-4F76-ACE0-F3BC70337D13","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4342cd48dd9fb52225396141317014e68edea026","datavalue":{"value":"1045830","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1362991$C7751A04-B7F7-4044-9C36-AEC471FC7E97","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82d2dd51ca15375c538ca246eb94903cb422c405","datavalue":{"value":"lexicographical order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1362991$75B2C454-B324-4C4D-9C85-34DFB1DB3302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"094720b58f8bf8260833ee6d55b9c6eb8876a5a7","datavalue":{"value":"boundary edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1362991$9A0F54D9-3E03-4547-ACC5-3026F4512F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5382d4b1ff0334d807c6ed68b7d0d3e49d39fb3d","datavalue":{"value":"inner edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1362991$284328F7-97EC-4EAF-A9FE-BA92E5770ACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ee34c3c0e942ee39b1fd6e44a841818021aead1","datavalue":{"value":"Cartesian sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1362991$3D7863F0-4686-4C96-B2A5-F1D0946818B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00f34186dac3809ffcc7c97722164c8ce0e8b7b5","datavalue":{"value":"set function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1362991$3CA12053-310A-480F-86FC-8F57BF137B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5b6fc82eb16f5a2afc7b2ca7ad955370720f242","datavalue":{"value":"submodularity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1362991$5B770042-FE4D-45C0-90CD-51775923899A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cc44dd3f6b1631a47161ab73a871b037c5ff8fb","datavalue":{"value":"edge-isoperimetric problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1362991$E49A760B-7C3E-471A-AA57-117D5C3688A6","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":"Q1362991$98E3E20C-D1F1-4970-BDE1-9EF6F741F08B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8496bd6e1982cbf5712fce5ae90f7fac3840b8cf","datavalue":{"value":"https://doi.org/10.1006/eujc.1996.0106","type":"string"},"datatype":"url"},"type":"statement","id":"Q1362991$3C142681-B143-47B3-8359-67D51C5CC905","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3645dfcfddac3dcc940401b1b9065c921b79df4a","datavalue":{"value":"W2100449986","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1362991$9C20957C-0844-4657-A040-12FD23DFF527","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"47194618ec97119dfdeb0cf402ebdc13f2d0e0bf","datavalue":{"value":"10.1006/EUJC.1996.0106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1362991$4163E43B-579A-403C-B66F-CCC25DCC205D","rank":"normal"}],"P1643":[{"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":"04af2c96ce5d43b3b6547c7bc10a229e3f90fff2","datavalue":{"value":{"amount":"+0.8123889565467834","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":"Q1362991$C002460D-CEB4-48A1-BE25-157353D756B6","rank":"normal"},{"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":"031abf42ec38ecc662d55b94103c6d1466f6927c","datavalue":{"value":{"amount":"+0.8110340237617493","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":"Q1362991$E2DB69D6-A5D6-4306-ABC4-EB00C9F38B54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb1b74df0696c03123f11f6d43ac21b375f9551f","datavalue":{"value":{"entity-type":"item","numeric-id":1885043,"id":"Q1885043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2123a1239f3f490777baddc1c807c2f2333fe1ba","datavalue":{"value":{"amount":"+0.8103892207145691","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":"Q1362991$70890B68-581C-4BFB-9489-B76AFAF19E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1411a1a3484bea051ec50e9bc30ded02dd2f141c","datavalue":{"value":{"entity-type":"item","numeric-id":1613525,"id":"Q1613525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6efab932c6d4b3e8d55288fdacac0d46b994413d","datavalue":{"value":{"amount":"+0.7965899109840393","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":"Q1362991$026FE021-53AE-4F90-9890-2165619DEE51","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1362991","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1362991"}}}}}