{"entities":{"Q1364141":{"pageid":1374880,"ns":120,"title":"Item:Q1364141","lastrevid":68731236,"modified":"2026-04-13T01:42:36Z","type":"item","id":"Q1364141","labels":{"en":{"language":"en","value":"Transversals of \\(d\\)-intervals"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1051248"}},"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":"Q1364141$D936D3B9-034C-43D1-9070-FBD1AB86D71B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bfed8eca8d7e5f2e235edddb161b7d0d7e93fbc4","datavalue":{"value":{"text":"Transversals of \\(d\\)-intervals","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1364141$1D7A0299-CD60-443A-91AE-F4AABBEBC48E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e5e11940c33a66c0d86d9d992c9a16b99b810940","datavalue":{"value":"0883.05124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364141$6C63DF63-A116-4815-8254-32F1C155B556","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f29f4f4da9afbb171c28d9ccca9826c1852c5789","datavalue":{"value":"10.1007/PL00009315","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364141$B96B20EC-CC53-4EE6-9293-ED6DAC6C13F1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364141$B6404F2E-01B1-4A37-A50E-3935504D6AC3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1c562e995241e7dc0acff61121b38a857bce140d","datavalue":{"value":{"time":"+1998-02-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1364141$6F5EED5B-06EE-4238-A9E7-2FE07330BBC3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f101abac6102e5f7356b61c8ddb6d082bd5a7373","datavalue":{"value":"A homogeneous \\(d\\)-interval is a nonempty union of at most \\(d\\) closed intervals on a fixed line. A nonhomogeneous \\(d\\)-interval \\(J\\) is a nonvoid subset of the union of \\(d\\) distinct lines \\(l_1,\\ldots ,l_d\\) in the plane, such that each \\(J\\cap l_i\\) is either a closed segment or the empty set. This paper treats generalizations to (homogeneous or nonhomogeneous) \\(d\\)-intervals of the following theorem of Gallai: if \\(H\\) is a family of closed intervals on a line such that no \\(k+1\\) of its members are pairwise disjoint, then there is a set \\(T\\) of \\(k\\) points of the line that intersects all intervals from \\(H\\). The set \\(T\\) is then called a transversal of \\(H\\). Obviously, the number \\(k\\) may be replaced by the packing number (or matching number) \\(\\nu (H)\\), which is defined to be the maximum number of pairwise disjoint elements of \\(H\\). Here are the two main results of the paper: (1) Every system \\(H\\) of homogeneous \\(d\\)-intervals has a transversal of size \\((d^2-d+1) \\nu (H)\\). This bound improves to \\((d^2-d) \\nu (H)\\) if \\(d\\geq 3\\) and there is no projective plane of order \\(d-1\\). (2) Every system \\(H\\) of nonhomogeneous \\(d\\)-intervals has a transversal of size \\((d^2-d) \\nu (H)\\). These theorems improve a previous result by \\textit{G. Tardos} on \\(2\\)-intervals [see Combinatorica 15, No. 1, 123-134 (1995; Zbl 0823.05022)]. A main tool of the proof is the Borsuk-Ulam theorem, which says that every continuous antipodal map \\(S^n\\rightarrow \\mathbb{R}^n\\) has a zero. Furthermore, two results of Lov\u00e1sz and F\u00fcredi are used, which give upper bounds of the fractional matching number \\(\\nu ^{*}(H)\\) in terms of \\(\\nu (H)\\). However, the author remarks that the latter results are not necessary if one wants to prove only the slightly weaker bound \\(d^2\\nu (H)\\) on the minimum size of a transversal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364141$919ED454-F917-459E-9977-8A3493F18C53","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364141$95570548-E9E1-4455-B277-5EC85E5CE25A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364141$EDF566D4-CF7C-4F65-AFA2-6AA3599458F9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae1879bf5e22e08c903f5fadcf32df7709edda33","datavalue":{"value":"1051248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364141$31314699-0A0A-47C3-8979-EFD35CF3E84B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed8a010bdd9169cc07d3976a995e98935bae1e64","datavalue":{"value":"transversal number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364141$0CABE9AA-CA9F-4149-8AE8-925DC75A27C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8410b3c94e92c6ef80171853b72204799eb8548","datavalue":{"value":"packing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364141$2491AF31-284D-4576-A443-FE9C620B4419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a6f9a53e5491c0a3783f5f18f068fcc0d291ba1","datavalue":{"value":"matching number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364141$D3EEC94D-F6A5-4FF2-8F4F-699A3CC8E328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2551957dc6ed0110294ad32e0bf2fb7bd3beb725","datavalue":{"value":"multiple intervals","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364141$5C13A31C-D5A7-4180-BBA6-321B2B42A171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6604eaa54105525adebb34a256ebb35aa0cd260","datavalue":{"value":"theorem of Gallai","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364141$8F2B8274-90EB-4A63-8A85-989CC6EA2775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b523d0120e9fd1439cbe34ae44730372d628480","datavalue":{"value":"intervals","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364141$B7C2FDB4-0676-4895-86A2-09A31B5D2C90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"916cdd3d2a6f5f57db6bd562990e6d44b7fb3b1d","datavalue":{"value":"transversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364141$E720D4EE-34EF-4CFD-8BDE-19BCAE82C92C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8df0ebc0c42f35d05a59dce509c57e3cf22f3034","datavalue":{"value":{"entity-type":"item","numeric-id":322208,"id":"Q322208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364141$FC3B4B7F-BA90-4469-A7EF-D77FFA19A73A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e0e4819c4197c41254056c7cc3ff1f7d43cbb4c","datavalue":{"value":{"entity-type":"item","numeric-id":587733,"id":"Q587733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364141$F0709C6A-9E02-4F86-BC9D-C50F72996314","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":"Q1364141$A8AA7AFD-5262-4E1F-95E9-83F51615C38C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a6af8531abdb56f18f62a4b56943783c40576e01","datavalue":{"value":"https://doi.org/10.1007/pl00009315","type":"string"},"datatype":"url"},"type":"statement","id":"Q1364141$A70BD471-820F-4283-9CC6-05A3F13490C3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b0152e7801ba11e38235d77ab8cf59c270202506","datavalue":{"value":"W1971007914","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364141$1EDF655C-D795-4F1B-B6B9-8D33B9ECE253","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"143c771ad5576b9d34810361756012450478bee8","datavalue":{"value":{"entity-type":"item","numeric-id":4208249,"id":"Q4208249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5957bf55530d79a3a275cc519d1ae0cf9ed240b","datavalue":{"value":{"amount":"+0.9284063","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$857C73F0-0F94-4706-BDEE-5E5BCF1DFE11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7b31327d8bbfface1a7237ec067f5bc84715f01","datavalue":{"value":{"entity-type":"item","numeric-id":5953072,"id":"Q5953072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14ba3d3f6567f42fa0444261c6359f6e2bfc1415","datavalue":{"value":{"amount":"+0.90352213","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$FB91D4D8-FC4D-4882-A7D8-6AB2C0B3F67E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cbb42f19ce76f2f9bf2885a44b8b415e2f9ac6b","datavalue":{"value":{"entity-type":"item","numeric-id":1842574,"id":"Q1842574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36b9c33c83d6bc1a1625b3c10a386cd6cb0cd03b","datavalue":{"value":{"amount":"+0.90296936","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$8FFDE5C3-E10C-48DC-8911-31B9E6771A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63b532cb3544174ab33d2cb5f8d502d231a47c26","datavalue":{"value":{"entity-type":"item","numeric-id":3192321,"id":"Q3192321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d120e8926c342e9be14adf10616bbfb9ea4e435","datavalue":{"value":{"amount":"+0.874147","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$CC16CF1E-0F21-4734-828F-8505537FCC4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ae8ad4008707674fcfbcc3c60ed260430309055","datavalue":{"value":{"entity-type":"item","numeric-id":5203262,"id":"Q5203262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7f261cbb6f2e1198197ed7041008cc0d2f528e0","datavalue":{"value":{"amount":"+0.8667724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$44819FFE-BE40-4937-905B-8817651F669A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"280e79e4f2fff863d02fa663e63dd4ad6daea442","datavalue":{"value":{"entity-type":"item","numeric-id":3972900,"id":"Q3972900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e07abdca953565d9bc9868ad3c712edebadfc1c","datavalue":{"value":{"amount":"+0.85938597","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$45E83B52-7270-456B-AB26-A6A8E47C307A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d5853236954133666c24dfe4c46cfef46261ed3","datavalue":{"value":{"entity-type":"item","numeric-id":3333277,"id":"Q3333277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e60c27e9962ead1f31a862b8dfa77d5c9bc678bf","datavalue":{"value":{"amount":"+0.8586518","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$7C1F5CCF-6485-4EEF-ADD8-8348DC992DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ff0b5f824770c6ce0a184470d518b1d9d9de7fe","datavalue":{"value":{"entity-type":"item","numeric-id":4907225,"id":"Q4907225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7beeb61b5ea13655235ee287482d8605a73c467","datavalue":{"value":{"amount":"+0.85861385","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$F1873A71-D875-470C-ACFD-351FDB30B7D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad25e5a16e4224aa5064f74626cc9d4a49f8c179","datavalue":{"value":{"entity-type":"item","numeric-id":4311449,"id":"Q4311449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"532e417996cbd894d541a72d724fc3ba0518a8c4","datavalue":{"value":{"amount":"+0.85739315","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$9AAC01C8-838D-418F-A939-100344AB2AD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ffc8c2935f5fd3780f4cb9c3f480fdb2017a9fe","datavalue":{"value":{"entity-type":"item","numeric-id":3184854,"id":"Q3184854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8badc97ff5172f04ece9e2273ad5307cdb01a15c","datavalue":{"value":{"amount":"+0.8558645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364141$3C80159B-E9F4-4D97-A839-89EE352767C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Transversals of \\(d\\)-intervals","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Transversals_of_%5C(d%5C)-intervals"}}}}}