{"entities":{"Q547779":{"pageid":549546,"ns":120,"title":"Item:Q547779","lastrevid":62659557,"modified":"2026-04-11T07:35:26Z","type":"item","id":"Q547779","labels":{"en":{"language":"en","value":"Acyclic sets in \\(k\\)-majority tournaments"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5913180"}},"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":"Q547779$803CC8DD-37BC-48EE-B8CD-A58595738238","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ba15fa149ada7b197af1c57222a40241549303f0","datavalue":{"value":{"text":"Acyclic sets in \\(k\\)-majority tournaments","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q547779$257EA93A-1FA5-4B79-80A3-760F72EEB417","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f941763b1f311c78877e376b2ce35251ac60831c","datavalue":{"value":"1218.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547779$5E65911A-2ADF-4196-B2F3-B57ED69C7952","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bda6634bd9b704666aafb27971d31fe0a008c4ad","datavalue":{"value":{"entity-type":"item","numeric-id":405188,"id":"Q405188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q547779$0DC32B75-EB06-4FE8-97B0-DC01891BB382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"04b4167f048af4074a57221524cf8d46f47c8d0a","datavalue":{"value":{"entity-type":"item","numeric-id":547778,"id":"Q547778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q547779$87096DC4-7F2B-4D61-8D45-6C308F4FAEA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q547779$DCC8046A-02ED-447D-A5D2-8A7DEC2C04D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q547779$05EA7E60-1875-4516-8EAD-EAB931266351","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f112f61a1bf8951421a1669c4dcd263b162b3092","datavalue":{"value":{"time":"+2011-06-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q547779$9E2A32E0-8AE2-4057-B8FD-F71CA39A92C1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2696dad370344f779f13d7680f65fa711081f1ff","datavalue":{"value":"https://eudml.org/doc/230353","type":"string"},"datatype":"url"},"type":"statement","id":"Q547779$A1D5B23C-9526-43D8-B3E6-02F0CD74267D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d2759fb82ac094a5480171db743f116a5b873a9","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p122.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q547779$58A191D5-9C4D-4BAE-A8B6-981599A9D1F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd0e8563b78eb4fb12d16b99cdba352c80ed8331","datavalue":{"value":"Summary: When \\(\\Pi \\) is a set of \\(k\\) linear orders on a ground set \\(X\\), and \\(k\\) is odd, the \\(k\\)- majority tournament generated by \\(\\Pi \\) has vertex set \\(X\\) and has an edge from \\(u\\) to \\(v\\) if and only if a majority of the orders in \\(\\Pi \\) rank \\(u\\) before \\(v\\)  Let \\(f_{k}(n)\\) be the minimum, over all \\(k\\)-majority tournaments with \\(n\\) vertices, of the maximum order of an induced transitive subtournament. We prove that \\(f_{3}(n) \\geq n\\) always and that \\(f_{3}(n) \\leq 2 \\sqrt {n - 1}\\) when \\(n\\) is a perfect square. We also prove that \\(f_{5(n)} \\geq n^{1/4}\\).   For general \\(k\\), we prove that \\(n^{ck}\\leq f_{k(n)} \\leq n^{d_{k(n}})\\), where \\(c_k = 3^{-(k - 1)/2}\\) and \\(d_{k}(n) \\rightarrow {{1+lg lg k}\\over{-1+lg k}}\\) as \\(n \\rightarrow \\infty \\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q547779$46278B07-E6CF-4F5D-BADA-55B958FA2060","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547779$A16272AE-D285-4F22-8A73-FDD6783A5581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24363e421bb7b6dfa7fe7a9b1ee54d8da8a06bf1","datavalue":{"value":"06A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547779$5F81EC4A-406F-40B8-BBE6-DDFDE92902B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d941b7104ec478435a962a831d115d1e7419f8d8","datavalue":{"value":"5913180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547779$7782A74B-7046-400E-A0E1-E55D96C73729","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a95117eca4562916655982de035b721507a45dcd","datavalue":{"value":"linear orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q547779$015F0156-C363-4ADF-B9EE-8BE6C0ED19D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7439e657356fdbd11b6ea627f9f45abd148f7b13","datavalue":{"value":"k-majority tournament","type":"string"},"datatype":"string"},"type":"statement","id":"Q547779$03D990E5-408D-460C-8CB1-15E10D0A37C0","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":"Q547779$391DEA6B-C116-49C2-8B6C-65A6FC7279A8","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a3bc1d2cc96c81001e78ba0d122059f80608af55","datavalue":{"value":"bafkreia66tnrklink6hpkf3oxyw5rxetrhgn7ihfn737r7gjkqwktaba7q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547779$C2FE2148-8372-43E6-9488-72E8CDFAE9A6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c222af4295b84ad2084e64ae3709e5944c70cb27","datavalue":{"value":{"entity-type":"item","numeric-id":2490838,"id":"Q2490838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f31f8174ef08b3894340e0fb6e08a74dfff3dc5","datavalue":{"value":{"amount":"+0.90022695","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":"Q547779$A1DD4C7D-6941-4E77-86FE-2F7E344495E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e768883fa5b11ae62bb6dbfd3c028d90b750000","datavalue":{"value":{"entity-type":"item","numeric-id":4393303,"id":"Q4393303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58e21a2ea4d10ca31013ded81ac4f4109bf065ff","datavalue":{"value":{"amount":"+0.8939064","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":"Q547779$5672E966-75D1-4BBA-A968-5A3ABBA8A8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40893e765cf44b6fbf5fb20504a11ae75dd822f1","datavalue":{"value":{"entity-type":"item","numeric-id":640421,"id":"Q640421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8ee4a035fd337f38ad4b726d33010d4d826894c","datavalue":{"value":{"amount":"+0.8860932","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":"Q547779$CF62CAB9-2FBA-45FC-8F1F-07DFE6F21F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"277d889178059a76a9edbdc5e80d5f8a00bc85ee","datavalue":{"value":{"entity-type":"item","numeric-id":393743,"id":"Q393743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd91f198fc1b21b3c7e979e1acc0cc2ed5521619","datavalue":{"value":{"amount":"+0.87729037","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":"Q547779$CC17AE21-76CF-48BE-9F21-FD7215A942EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e034d4b6b0bba23eb001ee97411a9fc2bc0b5ae","datavalue":{"value":{"entity-type":"item","numeric-id":427897,"id":"Q427897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8eb6e79e28ee7d50b5820328205c0decfa5b9a34","datavalue":{"value":{"amount":"+0.87563306","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":"Q547779$F5EE6917-28DA-4759-A1E1-FA25F12AB63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddd890412d070dcfdec2baa59485d876face9ce6","datavalue":{"value":{"entity-type":"item","numeric-id":1773195,"id":"Q1773195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73117381aea121ff6fa6dc1d5a65d341c2764276","datavalue":{"value":{"amount":"+0.872549","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":"Q547779$707FDB56-C4DD-405F-B4AD-81D3628E713F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7dec549ca6c9931c610659e27c5226e82f012ac0","datavalue":{"value":{"entity-type":"item","numeric-id":5688104,"id":"Q5688104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84296d945aeca16ebefa248a647862ead0a022b8","datavalue":{"value":{"amount":"+0.87251663","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":"Q547779$628F4E46-8BFC-4B06-AC61-01A590053B19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e7c3c725b6ed89347143b5ebec7e5e39e996e67","datavalue":{"value":{"entity-type":"item","numeric-id":834910,"id":"Q834910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3afb17e1b281d03bf66835ae6411cb71d6420649","datavalue":{"value":{"amount":"+0.8723565","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":"Q547779$CEEF61D7-4FEF-435E-8B37-98DD8848CC4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"237d853b3c56006da224d0322557762f36630ca7","datavalue":{"value":{"entity-type":"item","numeric-id":4254308,"id":"Q4254308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7086cd90c8c01c1c06912d0cabe15c08f649ea96","datavalue":{"value":{"amount":"+0.8700665","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":"Q547779$DECD716E-E49A-4EAF-A9E4-A8CCA853C9FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ef4249086f1cae458d1e941a88c601602738338","datavalue":{"value":{"entity-type":"item","numeric-id":616998,"id":"Q616998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42b5db71fb057b16ae88522717d3de0b3014075f","datavalue":{"value":{"amount":"+0.86917615","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":"Q547779$AFD60DAD-CCF7-480A-BDAB-8651A895CF5F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Acyclic sets in \\(k\\)-majority tournaments","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Acyclic_sets_in_%5C(k%5C)-majority_tournaments"}}}}}