{"entities":{"Q6614049":{"pageid":14225206,"ns":120,"title":"Item:Q6614049","lastrevid":56088477,"modified":"2026-03-12T14:51:08Z","type":"item","id":"Q6614049","labels":{"en":{"language":"en","value":"The base size of the symmetric group acting on subsets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7921882"}},"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":"Q6614049$B12F259B-50C7-49A2-B6BF-5E915488EFED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"faf07b26ef295ab5919141cfea54a0b336b75f89","datavalue":{"value":{"text":"The base size of the symmetric group acting on subsets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6614049$038683C2-F419-4BEE-B477-ED473CDE0EEF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"66452c0889800ad3f55810864f45e41b98909e8c","datavalue":{"value":{"entity-type":"item","numeric-id":4995325,"id":"Q4995325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$C89A8206-C251-479D-998F-41A8D694809F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09c9e677f467581a4964486a64603d264b546435","datavalue":{"value":{"entity-type":"item","numeric-id":375518,"id":"Q375518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$A01BBCDF-9768-40A0-8583-7D28FAF3B8A1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f2b397b605f6b917bc31809ef0354d057a518769","datavalue":{"value":{"entity-type":"item","numeric-id":776829,"id":"Q776829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$FA6268C0-02DD-44CE-85D2-BAE9EB088BE3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a97b222c279d09c7408b22b57194090b88c27b94","datavalue":{"value":{"time":"+2024-10-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6614049$ADA867A5-EE88-4524-ABF2-0524794471A0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a117f9701aec7e27d50778735bba9d3becfcd7f9","datavalue":{"value":"A base for a permutation group \\(G\\) acting on a set \\(\\Omega\\) is a subset of \\(\\Omega\\) such that the pointwise stabilizer in \\(G\\) of the subset is trivial. The minimal size of a base for \\(G\\) is denoted by \\(b(G)\\). In this paper, \\(G\\) is taken to be the symmetric group \\(S_n\\) or the alternating group \\(A_n\\) and \\(\\Omega\\) is the set of \\(r\\)-element subsets of \\(\\{ 1, \\ldots, n \\}\\) for any fixed (positive integer) \\(r\\) less than \\(n/2\\). In the former case, \\(b(G)\\) is denoted by \\(b(S_{n,r})\\) and in the latter case \\(b(G)\\) is \\(b(A_{n,r})\\).\\N\\NIn [Stud. Sci. Math. Hung. 49, No. 4, 492--500 (2012; Zbl 1296.20002)], \\textit{Z. Halasi} showed that \\(b(S_{n,r}) \\geq \\lceil \\frac{2n-2}{r+1} \\rceil\\) with equality when \\(n \\geq r^{2}\\) (later improved in [\\textit{J. C\u00e1ceres} et al., Discrete Math. Theor. Comput. Sci. 15, No. 1, 1--14 (2013; Zbl 1283.05122)] to \\(n \\geq (r^{2}+r)/2\\)) and that \\(b(S_{n,r}) \\geq \\lceil \\log_{2}n \\rceil\\) for all \\(n \\geq 2r\\) with equality if \\(n=2r\\).\\N\\NGiven \\(l\\), \\(k\\), \\(r \\in \\mathbb{N}\\), set \\(m_{r}(l,k) = \\frac{1}{k} ( lr - \\sum_{i=1}^{k-1} i \\binom{l}{i} )\\). Building on [Halasi, loc. cit.], the authors obtain the following result:\\N\\NTheorem 1. Let \\(n \\geq 2r\\) be fixed and let \\(l\\) be minimal such that there exists some \\(k \\leq l+1\\) satisfying \\(0 \\leq m_{r}(l,k) \\leq \\binom{l}{k}\\) and \\(\\sum_{i=0}^{k-1} \\binom{l}{i} + m_{r}(l,k) \\geq n\\). Then \\(b(S_{n,r}) = b(A_{n+1,r}) = l\\).\\N\\NIn the case of symmetric groups, a result similar to Theorem 1 was independently obtained by \\textit{G. Mecenero} and \\textit{P. Spiga} [Australas. J. Comb. 88, Part 2, 244--255 (2024; Zbl 1536.20008)]. The two proofs are different.\\N\\NWe note that the number \\(b(S_{n,r})\\) is the determining number for the Kneser graph \\(K_{n,r}\\). (The determining number of a graph \\(\\Gamma\\) with vertex set \\(V\\) is the minimum cardinality of a subset \\(S\\) of \\(V\\) such that the pointwise stabilizer of \\(S\\) in \\(\\mathrm{Aut}(\\Gamma)\\) is trivial. The vertex set of \\(K_{n,r}\\) is the set of all \\(r\\)-element subsets in \\(\\{ 1, \\ldots , n \\}\\) and two subsets are connected by an edge in \\(K_{n,r}\\) if and only if they are disjoint.)\\N\\NWe mention a corollary of Theorem 1.\\N\\NCorollary. For positive integers \\(n\\) and \\(r\\) satisfying \\(r^{3/2} + (r/2) + 1 \\leq n < (r^{2}+r)/2\\), one has\\N\\[\\Nb(S_{n,r}) = \\Big\\lceil {\\Big( 3(2n+r - \\frac{5}{4}) + r^{2} \\Big)}^{1/2} - r - \\frac{3}{2} \\Big\\rceil.\\N\\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q6614049$53A05A1A-BC5F-4332-8093-5DD7D5C96275","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"33e41358032c65f1c6e53862fbfa8c689b637f0f","datavalue":{"value":{"entity-type":"item","numeric-id":254329,"id":"Q254329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$DA7A75A6-4DDE-456E-BC72-FE916951D002","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3367018dbe2ad5da0826b32cb1ef14710133d281","datavalue":{"value":"20B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6614049$C9BA2F36-8023-4E9E-8A66-7552DC4C1E3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa3a0cd38ea582d702916ee49599e832f201d954","datavalue":{"value":"20B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6614049$D6BEA6E5-5B0C-4BC7-BA10-C91D67E24F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fad60f4f20aa9dea89d519269a20a5b36954889e","datavalue":{"value":"05E16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6614049$7104CE46-3283-4AC8-8409-4A704CCF3AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b0344475b093a005210c8cd3287a0b2589c6a0ee","datavalue":{"value":"05E18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6614049$19E53CBC-ACDA-4240-A916-479F6B8439F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eeb03bde62bd57310e192714f39a494690bfd058","datavalue":{"value":"7921882","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6614049$7216FD17-99D8-4951-8F9F-ED691CBF8EE3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38d830dae6f5ce906f6d20604a81e37d7574c069","datavalue":{"value":"symmetric group","type":"string"},"datatype":"string"},"type":"statement","id":"Q6614049$216FAAD0-AD70-498D-94DA-43216F28764B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76d2139cf0d2726e0b556197e7095ff9525ccf02","datavalue":{"value":"base size","type":"string"},"datatype":"string"},"type":"statement","id":"Q6614049$4908BCF1-1850-49AC-97D7-1A7B75807E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63a0b5bbdbffeb2f6d94dda6a7bccbc2173775aa","datavalue":{"value":"hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6614049$C8EAEAA9-28E6-44D9-AAA2-9EEEEF5FDC67","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":"Q6614049$03DF28ED-B064-4F93-ABA0-2B6E5500801F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"febd3cfd666d0e70bb82781a375fc0aa7e7e7826","datavalue":{"value":{"entity-type":"item","numeric-id":396927,"id":"Q396927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$7712B63E-E2DB-4C02-8793-19A515910A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4c1760dd9874c8616ff2ecec8a88827e917893d","datavalue":{"value":{"entity-type":"item","numeric-id":3990610,"id":"Q3990610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$218DAF18-B267-429A-BA95-5BD4181439F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2d76b6c8b7e12b93ebcdbb0f346b5649614f36b","datavalue":{"value":{"entity-type":"item","numeric-id":869991,"id":"Q869991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$C5F7B21E-D103-4B49-9AAD-BCA62CFE02C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"036f63b7d28561f9f34aba1e6dbac16467e76e2f","datavalue":{"value":{"entity-type":"item","numeric-id":3169279,"id":"Q3169279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$23D3DDEB-E598-4311-B7BF-5A4F34A144E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"109c16b67d0c75164a26bf776125b96f1277619a","datavalue":{"value":{"entity-type":"item","numeric-id":3597915,"id":"Q3597915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$44B9DAAA-60E6-438D-BF3A-387090DEB853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af7958a6413b2ead0b15377be1c3402707b23be2","datavalue":{"value":{"entity-type":"item","numeric-id":5747367,"id":"Q5747367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$665CECF1-B6C6-4E34-B508-AD6BE79E5A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a30855408a0aeeb826f54eccde04e276d0f15df3","datavalue":{"value":{"entity-type":"item","numeric-id":4289292,"id":"Q4289292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$1301BEFF-0C40-48FF-993B-0D804401A686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df0fa9865cd6dd0692e0adbe7a15998984f0b44d","datavalue":{"value":{"entity-type":"item","numeric-id":5169214,"id":"Q5169214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$4227BD96-4D04-4CE5-87DD-60215F2FE4DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3110802854fcb6986139ae23280dbaffbef56a3f","datavalue":{"value":{"entity-type":"item","numeric-id":4235502,"id":"Q4235502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$C7A1C53D-E108-44A4-968A-FF416209595E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2042ed659c177514afb9d6c8d861322c30769a5a","datavalue":{"value":{"entity-type":"item","numeric-id":6200554,"id":"Q6200554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$6BB4FE02-3EC9-45BE-B728-3A8A3DD07350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"822f3140ae47fe4e18cfca691197a0d5f7e9930c","datavalue":{"value":{"entity-type":"item","numeric-id":1984366,"id":"Q1984366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$C0E29993-8DC5-4E09-ADBA-5DFEA66D3A53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c62ada788f3ca01a4c6f8156af507942db5d91","datavalue":{"value":{"entity-type":"item","numeric-id":4787523,"id":"Q4787523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$E9B93F37-7258-46F1-9CD0-E3EB1E1C00E5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"41ad0053eee016162369e747b49039acdcd9210b","datavalue":{"value":"10.5802/ALCO.370","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6614049$FFE44188-6E9A-4C79-8BE1-E3FF67C36F09","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e1039caa23863a88a0ebe0406602f3842fdfb91","datavalue":{"value":{"entity-type":"item","numeric-id":6200554,"id":"Q6200554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99bd7a43e9070b848da846ff753c2ebd86158367","datavalue":{"value":{"amount":"+0.9173209071159364","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":"Q6614049$B9EF5A79-43DC-4F3D-ABEA-C2E0D7FC92D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bedb2690697e5c003c75ab0bbe6488e0085e9b3","datavalue":{"value":{"entity-type":"item","numeric-id":5169214,"id":"Q5169214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4573d2508a82ae5d30858323ed264b25a4e2ea0e","datavalue":{"value":{"amount":"+0.8539751768112183","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":"Q6614049$77EE640C-D38E-475F-AAE5-E84BDC910AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54e299013c30928e8bfc34a975d85df56559eb9f","datavalue":{"value":{"entity-type":"item","numeric-id":3169279,"id":"Q3169279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a354d0c744e1e6478b5eb294ea73e3659c4fbef4","datavalue":{"value":{"amount":"+0.8254786729812622","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":"Q6614049$373333E7-E4D2-45C1-AFE5-FCB300EB3116","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e364ed90ca56e66982f4a29b03e0086e120c6cd","datavalue":{"value":{"entity-type":"item","numeric-id":5747367,"id":"Q5747367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce11bb92b82b17b63ced0a29b0556edd6c4906bf","datavalue":{"value":{"amount":"+0.7940466403961182","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":"Q6614049$18D77B8F-85FD-4C3D-A894-90D43865F2BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"998dd2e882d177b77248b7c43434e483d41227c0","datavalue":{"value":{"entity-type":"item","numeric-id":1984366,"id":"Q1984366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"806e5cdc980e67bceb5d84a6f60391e97039694d","datavalue":{"value":{"amount":"+0.7883027195930481","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":"Q6614049$A2BFC3F3-F477-43C6-A505-D825B4060791","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6614049$2B314C61-C8A5-43B3-BCEC-6E76E18F339F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6614049","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6614049"}}}}}