{"entities":{"Q2531038":{"pageid":2541781,"ns":120,"title":"Item:Q2531038","lastrevid":48646765,"modified":"2026-01-05T11:58:52Z","type":"item","id":"Q2531038","labels":{"en":{"language":"en","value":"Submodular functions and independence structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3270648"}},"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":"Q2531038$654862CE-8384-4E9E-8087-12538880958B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f392b294cd08291d7d52dbc189b5d36ca92261d8","datavalue":{"value":{"text":"Submodular functions and independence structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2531038$FF032682-F557-4E43-9CE6-82A8DA745C4E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d130c539c3d5d15dfe3454970761cd7e1754a57b","datavalue":{"value":"0169.01902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2531038$C5208867-1100-4FD6-8A76-6422B94485D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"600c45ff3633b8477fb9f789ad379c1cb15ed97e","datavalue":{"value":"10.1016/0022-247X(70)90180-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2531038$B0D8F4FE-48AC-4D71-8947-30414EF68572","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf8bf66f92b228cb29592504899e7b4233a2afb9","datavalue":{"value":{"entity-type":"item","numeric-id":766916,"id":"Q766916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$3E2DB807-34A6-48B0-9988-2DB893E27BBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4b9978ba9af9bd8ccac9c990e084a657e995db4","datavalue":{"value":{"entity-type":"item","numeric-id":1778068,"id":"Q1778068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$5F46CDF6-F6BA-4350-9FC4-9673050F79E6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c5ad7b9baf8e531c6b1ad954eb5f2899cc8fe5e5","datavalue":{"value":{"entity-type":"item","numeric-id":85344,"id":"Q85344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$0F13D965-E0E9-4F4C-B7D8-021C5E65120E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e293d9e9c8dba13b0feb4b9b16887fc748f70c6f","datavalue":{"value":{"time":"+1970-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":"Q2531038$11C7A3C3-EB5D-42FD-A886-332B7E1C7625","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff49d944b2daee943fd8a012a776ae3ba1c380a4","datavalue":{"value":"A function \\(\\mu\\), defined on all subsets of a set \\(X\\) and taking its values in \\(\\{0,1,2, \\ldots,\\infty\\}\\), is called submodular if it is non-decreasing and \\(\\mu(A \\cup B) + \\mu(A \\cap B) \\le \\mu(A) +  \\mu(B)\\) \\((A,B\\subset X)\\). If \\(\\mathcal E\\) is an independence structure on \\(X\\) then its rank function \\(\\rho\\) \\((\\rho(A) = \\sup\\{ \\vert E\\vert : E\\subseteq A, E\\in \\mathcal E\\})\\) is submodular.   It is shown in \\S2 that the submodularity of \\(\\rho\\) is precisely what is required to prove a theorem of \\textit{R. Rado} [Q. J. Math., Oxf. Ser. 13, 83--89 (1942; Zbl 0063.06369)]: a family \\(\\mathfrak A = (A_i : i\\in I)\\) of subsets of \\(X\\) has a transversal which lies in the independence structure \\(\\mathcal E\\) if and only if for each finite subset \\(J\\) of \\(I\\), \\(\\rho(\\cup_{i\\in J} A_i)\\ge \\vert J\\vert\\).   In \\S3 it is shown that the set of integer-valued non-decreasing subadditive functions defined on the subsets of \\(X\\) form a lattice. A subadditive function is called continuous from below if \\(A_i\\uparrow A\\) implies \\(\\mu(A_i)\\uparrow \\mu(A)\\); this holds in particular for rank functions. If \\(\\mu_1\\) and \\(\\mu_2\\) are both submodular and continuous from below, then their lattice infimum  \\(\\mu_1\\wedge \\mu_2\\) is continuous from below (though it may not be submodular). Some of these results are now applied.   If \\(\\mu\\) is submodular on the subsets of \\(X\\), then \\(\\mathcal E(\\mu) = \\{E\\subseteq X : \\mu(A)\\ge \\vert A\\vert\\)  whenever \\(A\\) is a finite subset of \\(\\mathcal E\\}\\) (here, \\(\\vert A\\vert\\) is the cardinal number of \\(A\\), and generally, \\(\\vert\\cdot\\vert\\) denotes the cardinal function) is an independence structure, and if \\(A\\subseteq X\\) is finite, the rank of \\(A\\) is \\(\\mu\\wedge \\vert\\cdot\\vert (A)\\). An application to transversal theory is also given, generalizing the result that the partial transversals of a family of sets form an independence structure.   Next, a theorem of \\textit{C. St. J. A. Nash-Williams} is considered [Theory Graphs, Int. Symp. Rome 1966, 263--265 (1968; Zbl 0188.55903)]. Let \\((\\mathcal E_i : i\\in I)\\) be a family of independence structures on \\(X\\), and let \\(\\mathcal E_i\\) have rank function \\(\\rho_i\\). Write \\(\\mathcal E = \\{\\cup_{i\\in I}\\) for each \\(i\\}\\). Then  \\(\\mathcal E\\) is a pre-independence structure with rank function \\((\\sum_{i\\in I} \\rho_i) \\wedge \\vert\\cdot\\vert\\). Two other formula for the rank function of \\(\\mathcal E\\)are given.   The discussion now turns to graph theory. Let \\(\\Gamma\\) be a directed graph and \\(Y\\) a set of nodes of \\(\\Gamma\\). Given two sets \\(E, F\\) of nodes of \\(\\Gamma\\), write \\(E\\le F\\) if every path from ( a node of) \\(E\\) to (a node of) \\(Y\\) must contain a node of \\(F\\). Then \\(\\le\\) is a quasi-order on the sets of nodes of \\(\\Gamma\\). Write \\([E] = \\{x\\in E\\): there is a path from \\(x\\) to \\(Y\\) which contains no other node of \\(E\\}\\). Then \\(\\le\\) is a partial order of the collection \\(\\mathcal S\\) of sets of the form \\([E]\\), and moreover, \\(\\mathcal S\\) is a lattice. Take fixed sets \\(X\\), \\(S\\) of nodes of \\(\\Gamma\\) such that \\(X\\le S\\), and write, for \\(A\\subseteq X\\), \\(\\sigma_s(A) = \\min\\{\\vert E\\vert, A\\le E, E\\subseteq S\\}\\). Then \\(\\sigma_s\\) is submodular on the subsets of \\(X\\); it induces on \\(X\\) an independence structure with rank function \\(\\sigma_s \\wedge \\vert\\cdot\\vert\\) or simply \\(\\sigma_s\\) when \\(X\\subseteq S\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2531038$9213FE80-C25A-4DE8-B5F6-622766FE58C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2531038$6DB734C4-6A87-48E8-AD28-BB6B1688C3DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3d71e897988769ad2e271b00971ea2e28f364565","datavalue":{"value":"3270648","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2531038$C6A6FF0A-957F-46FA-8374-6EB6CF90FA6A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"459ffded74521c7177e183238b11e0b004784b7c","datavalue":{"value":"combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2531038$A2D9597F-D2EC-4294-AB8D-C5E4F7F40EAC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"64762724c1e02f9032bfe996e6c875fc215af1bd","datavalue":{"value":{"entity-type":"item","numeric-id":1778068,"id":"Q1778068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$CB9BE798-EB9F-4A58-9ED3-394FC364495D","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":"Q2531038$8285F8C8-731B-4CCB-8648-17C4AF457F3C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2234b0cffa2299db56ef38bc1a83d6d08f15012","datavalue":{"value":{"entity-type":"item","numeric-id":3254057,"id":"Q3254057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$F7697ADF-B608-425F-A7F3-DC1257C21A5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"145268d761c65c4413252c4f38f08de69481f3c9","datavalue":{"value":{"entity-type":"item","numeric-id":5516086,"id":"Q5516086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$03350943-02E0-463E-B240-6F24B525721B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"156e0039392d6ef79c6665c628ac60551f79308f","datavalue":{"value":{"entity-type":"item","numeric-id":5790243,"id":"Q5790243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$8C4D5840-619D-4C77-9D60-A1E93421BB08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4534d792f5262a1f297a74f9b43efedcc5cd94ec","datavalue":{"value":{"entity-type":"item","numeric-id":4760022,"id":"Q4760022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$2DA429F4-83EC-4842-9264-CFF9A3758612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66834db16fa66240c9b25788d376d904fc462b37","datavalue":{"value":{"entity-type":"item","numeric-id":3262258,"id":"Q3262258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$0942A41E-02B1-4FB2-BA34-B93A144DB0E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e82904222b9a512f3e983bc9662d9b5c40afe505","datavalue":{"value":{"entity-type":"item","numeric-id":5920823,"id":"Q5920823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$639CF0EA-4CBD-461F-BE82-59D2B54D4EBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0e4b7efadc93cfb2d719697915750696f0eb7ec","datavalue":{"value":{"entity-type":"item","numeric-id":5532565,"id":"Q5532565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$FDA71D3F-B43B-4CA8-8023-EB2A7B01D4BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcef05a03ebf2c920955a9550f678d5d0ff90329","datavalue":{"value":{"entity-type":"item","numeric-id":5582910,"id":"Q5582910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$B940C0FF-8C97-425B-ACFD-E84FA9FA8E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fdd0c89aa944e4c2338cc85d129375a6ff616a6","datavalue":{"value":{"entity-type":"item","numeric-id":5566538,"id":"Q5566538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$D8689587-E24E-4D7C-9BE0-60F5FEBE01C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed3a4436c7218f92ab880c2fff2e45e837768be8","datavalue":{"value":{"entity-type":"item","numeric-id":2527630,"id":"Q2527630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$981CFCC5-DE02-4275-857A-001F2DEC40DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"def8046dc06a73252841344bbd2a23b725fe0795","datavalue":{"value":{"entity-type":"item","numeric-id":5580257,"id":"Q5580257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$AE6D0DFC-A519-4310-842A-239E92151707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06249088c6e3f4e951e1e7883a106b54d43b0a88","datavalue":{"value":{"entity-type":"item","numeric-id":2533558,"id":"Q2533558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$20255AC2-4E36-424C-9D0B-4260568D99F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bef3ce047c7eb828a48fa89206a557b3aca45995","datavalue":{"value":{"entity-type":"item","numeric-id":5845425,"id":"Q5845425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$72FF76DC-711B-4D89-84A5-B53ED26E805D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a438e696f7fa90196f7c2ef9e9a8d6eb8fb9c3e","datavalue":{"value":{"entity-type":"item","numeric-id":5789532,"id":"Q5789532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$C2ADB71D-FE20-4B39-9DB3-B4095BCFED82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15845f85ecb2d928e4998106f456e4c54d2950fa","datavalue":{"value":{"entity-type":"item","numeric-id":5510786,"id":"Q5510786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$60F3373B-F9A6-4FE6-A4FF-45D1C6814A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7503180661c06c10a8af42d5d3480716d20a5cd6","datavalue":{"value":{"entity-type":"item","numeric-id":5542117,"id":"Q5542117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$82EC401E-96AD-4041-B17B-69ACB32E8A7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ef595c19ff7cfdef187a18349266eb05bda6338","datavalue":{"value":{"entity-type":"item","numeric-id":5530480,"id":"Q5530480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$B0596C1B-F764-48DD-AF4A-D29BBA088170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54ee48280c3b631d656d9997c1ccfd90f7e6b44f","datavalue":{"value":{"entity-type":"item","numeric-id":2550391,"id":"Q2550391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$1E7ECA33-0184-41E4-B3DF-87C4081E25A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef595d3b2b2756d193a4196daf05782b06adb112","datavalue":{"value":{"entity-type":"item","numeric-id":5555708,"id":"Q5555708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2531038$076CCA48-BCED-44F0-8117-91E12560A4F9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e76eb7dd4c8732e7ea5ac916a2248b667847859b","datavalue":{"value":{"entity-type":"item","numeric-id":3824318,"id":"Q3824318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"133041c910d76fabb3b2f98c4b63284c8bcbae1f","datavalue":{"value":{"amount":"+0.8057839870452881","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":"Q2531038$87D128B1-353F-4BAA-BC69-0E2B7BCB0D14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8590a439efd47f5c01d2198f7bc817352f430a83","datavalue":{"value":{"entity-type":"item","numeric-id":1174311,"id":"Q1174311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca7c4b09b5110532f0f62d73509c73995d84f6c8","datavalue":{"value":{"amount":"+0.7901437878608704","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":"Q2531038$B34C00A8-4132-47B5-B731-0F7425FD5F3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e2dc442f8110e9da1c86938ce70f0536c26eb15","datavalue":{"value":{"entity-type":"item","numeric-id":790044,"id":"Q790044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e88c577eca1f9c151766db4b8671338c8cf724cd","datavalue":{"value":{"amount":"+0.7860864996910095","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":"Q2531038$61D30503-6BC4-4395-943E-25550D1F6DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b617acd195bf7c8598879b7eff8a53a1a86e8a4f","datavalue":{"value":{"entity-type":"item","numeric-id":4414632,"id":"Q4414632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01b7932b806c246dce7eed561dd506c74151cf5a","datavalue":{"value":{"amount":"+0.7851474285125732","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":"Q2531038$8DD54048-1A1E-4FF6-A856-40CC0AC5FA05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f12d3666457417e52e3ad871cd89a88aa9095ca8","datavalue":{"value":{"entity-type":"item","numeric-id":3313913,"id":"Q3313913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01b7932b806c246dce7eed561dd506c74151cf5a","datavalue":{"value":{"amount":"+0.7851474285125732","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":"Q2531038$B683319B-DBF8-45AB-A5D3-2A4AB92A4ABA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2531038","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2531038"}}}}}