Given a finite group , the hypergraphical regular representation problem asks about the existence of a hypergraph whose full automorphism group is equal to acting regularly on the set of its vertices. In our paper, we work with -hypergraphs which are hypergraphs in which each hyperedge is of the same size . Since the existence or non-existence of hypergraphical regular representations for groups of the order exceeding the value 32 has been proved theoretically, our focus is on a computational verification of hypergraphical regular representation via -hypergraphs for groups of order smaller than or equal to 32. For all groups of order less than or equal to 32, except for the group Z25, we computationally proved a conjecture stating that if a group admits a hypergraphical regular representation via some -hypergraph, it admits the hypergraphical regular representation for every -hypergraph in the range ≤ ≤ | | − . To obtain our results, we created and implemented algorithms in the computational system GAP.
group and the order of the group is relatively prime
to 6. Their method was generalised by Imrich [10]
Throughout this paper, we consider all groups to be fi- who discovered that non-abelian groups whose order
nite. The automorphism of a graph Γ is a permutation is odd and not less than 37 · 54 admit a GRR. Later,
of the vertex set (Γ) , such that the pair of vertices Watkins [11] summarised the previous findings that
(, ) form an edge if and only if the pair ((), ()) were subsequently supplemented by Godsil [12].
Gradalso form an edge. The set of all automorphisms of Γ ually, a list of groups that do not admit a GRR has been
together with the operation of composition form the au- formed and today we have a complete classification in
tomorphism group (Γ) of the given graph Γ . The the form of the following list: abelian groups with
exgraphical regular representation (GRR) of a group is ponent greater than 2, generalised dicyclic groups and
a graph Γ with the set of vertices (Γ) and the set of groups isomorphic to one of 13 groups whose order is
edges (Γ) having the property that the automorphism not greater than 32 Z22, Z23, Z24, D3, D4, D5, A4, Q ×
group of the graph (Γ) is the group in its regular Z3, Q × Z4, ⟨, , | 2 = 2 = 2 = 1, =
action. Frucht in [
The GRR problem has been intensely studied over A variation of the GRR problem is a digraphical regular
the years. First, Sabidussi [
The search for the GRR’s for non-abelian groups on the set of vertices of . The problem was studied by
started with Nowitz [
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License automorphism group isomorphic to .
CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) In the present work, we focused on the problem of
hypergraphical regular representation motivated by the property ∀ ∈ () : () ∈ (). Based on
previoriginal GRR problem of which it is a generalization. The ous definitions, the 2-hypergraph is also the non-oriented
hypergraphical regular representation problem is inter- graph Γ from Section 1. A -hypergraph is a regular
repesting mainly due to the more complex structure of the resentation (HRR) of a group for 0 ≤ ≤ | | if and
hypergraphs. Section 2 covers the definition of the hy- only if for every two vertices , ∈ () there exists
pergraphical regular representation problem with a brief exactly one automorphism () = from the
automorreview of all necessary concepts and an overview of the phism group of the -hypergraph (), i.e. ()
previous results. At the end of the section, we present acts regularly on the set of vertices (). An important
the hypergraphical regular representations problem that concept that will be used is a group action of a group
we computationally verified and a conjecture about the on a set which is a map · : × ↦→ (written as
spectrum of possible parameters. In Section 3, we de- · , ∀ ∈ , ∈ ) such that ∀1, 2 ∈ , ∈ :
scribe our computational approach in details. We specify 1 · (2 · ) = (12) · and ∀ ∈ : 1 · = .
the used computational system GAP that is important The orbit of a hyperedge ∈ () is the set of
hyfor reaching our proposed goals. Further, we present peredges in () to which can be moved by the
elean implementation of algorithms in the computational ments of group , where is acting on the set (),
system with a description of the theoretical background i.e. () = { · ∈ () : ∈ }, where · is the
for each operation. In Section 4, we present diferent induced action of on ().
types of applied optimizations used to decrease the com- Foldes and Singhi [
As stated before, a group has a HRR if and only if 3. Methods there is a -hypergraph whose automorphism group acts regularly on the set of its vertices. We implemented methFor the computational verification of group regular rep- ods described and proved in [18]. The authors defined resentations via -hypergraphs, we decided to program () as a set of all -element subsets of a group and our algorithms in the system for computational discrete as the left multiplication of a group . By [18], a algebra - GAP [20]. The system is free, open-source and group has a HRR via a -hypergraph whenever there widely used in similar computational problems concern- exists a -hypergraph with the set of -hyperedges ing work with groups, graphs and other combinatorial structures. It provides its own programming language ar(eel)e m⊆ents(of)w.hose () = , where () and implements functions for multiple algebraic algo- We needed to search groups of small orders to use the rithms in importable packages. Throughout the imple- theory from [18] in computational implementation. The mentation of our algorithms, we were using diferent above-mentioned theoretical result confirms the existypes of packages: GRAPE, loops and DESIGN. In the rest tence of -hypergraphs, which are the HRR’s, for groups of this section, I will give some technical information exceeding the order of 32, thus our proposed algorithm about the used packages and commands. The algorithms needed to go through all groups of order up to and weTreheimnpalmeme eonfttehdeipnatchkeaGgeAGPRwAiPthE v[e2r1s]i oisna4n.1a1b.1b.revia- itnocgluodtinhgro3u2g.hWaelluosredderthselefsosr-tlhoaonpsofroerquoarldtoer32≤ an3d2 itosifodngersfaoigprnhGesRdwafpoithrhcAorlemgloaprtuiitothanmtsiostnuoss,igncrgoonuPspEtrsrmu.cuTttihoaentisopnaancgdkroaaugnpeaslcyaosnnids- rgferotoruurpniss ≤ tohfeNgrniSuvmmeanblelorGrdoreforu,gproswu(hpoesrrdeweirNth)rSttomhagelegtliaGvlrleonpuoospsrsidb(el)er. nects the graph structure with the group structure. Each Subsequently, we created a group object with the gOrnaephofisthsetocroemd paosnaesnttrsuicstuargerwouitphosfeavegrraalpchomwhpiocnheinstsa. rceotmurmnasntdhe G-th:=groSumpalolfGtrhoeugpiv(eonrdoerdre,r. iT)h,e rweshuilcths specifically chosen subgroup of the graph automorphism above imply that the automorphism group of the group. The loops package [22] allows computing with -hypergraph must be equal to the left multiplication of algebraic structures: quasigroups and loops. We chose the group from which the -hypergraph was constructed. to use this package because of the implementation of According to Cayley’s theorem, we assigned to each group-theoretical algorithms, which were important in element of the group the permutation of the left our experiments. More precisely, we used an algorithm for the left multiplication action. We firstly transformed amrueltailpsloicealteiomne,nstuschofththate gr·oup.= Wℎe wusheedrecomamnadndℎs a group object into a quasigroup object and then per- from the loops package to get the left multiplication. formed the action of the left multiplication. Lastly, the DESIGN package [23] is made for constructing, classi- Wweitthratnhsefocormmemdatnhde qdueafasuilt :g=rouIpntoobQjeucatsiingtoroauqpu(aGs)i-, fying, partitioning and studying block designs. In their group object from the loops package. We performed dpeofininittisoann, da tbhloecsketdoefsibglnocikssa,nwohredreereadppoainirt oisf athneelseemtoefnt opbetramin :t=heLpeefrtmMuutlattiiopnliocfatthieolnefGtrmouuplt(iqpluiacastiio)n fotor and a block is a set of elements. The condition for using each element of . Based on the computed permuthe package is an imported GRAPE package. tations, we created orbits of -hyperedges with the lteemcTt,ot whfineedefirtsxhtielsytiemfnopccleuesomerdennootnant-pieorxonipssotoeslniunctgieoaonnftHoalRtghRoer’siHthfRomrR gtporroodubep--s cd(ou[mp1l.mic.aaontredd-fereroe]r,lbiskt:)o=,f oOOrrnbbSiitesttsws()hp,eerremwe,hacicChhoomrbbrieitntuairstniasosnesat vitisac2o-rhreycptenregsrsaopnhst.hWekentoeswtendthoeuorraeltgicoarlitrhemsulatns.dWveerhifieadve corfeat-ehsypaellrepdgoesssi.bleThe-hcyopmermedagneds Ctohmabtianraetidoivnisd(e)d the list of all groups with orders not exceeding 32 ad- into orbits depending on the permutations of the left mitting the GRR from the [12], which is the HRR via a multiplication. Since the orbit for each -hyperedge 2-hypergraph in our case. After verifying the proposed contains a set of equivalent -hyperedges, the orbits are algorithm for groups on 2-hypergraphs, we modified the disjoint. By creating the combinations of orbits with algorithm to compute a HRR of groups via 3-hypergraphs for the same set of groups of orders less than or equal wCohmicbhieniathteiroandsm(iotsrbo)r,dowese noobttaadinmeidt aaHR-Rhyfopreraggriavpehn, to 32. We observed the changes in the list of groups ad- group. The GAP system does not have a specific object for a -hypergraph. Thus, we decided to represent a actions are equivalent. Therefore, the orbits cor-hypergraph as an incidence structure which preserves responding to the left and to the right multiplicasymmetries and its automorphism group is isomorphic tion actions are isomorphic. The diference between to the automorphism group of the -hypergraph. We the actions is in the order in which acts on . depicted the incidence structure (Fig. 1) as a bipartite The orbits of the -hyperedges and the efectivegraph where the left (black) set of vertices () are the ness of the final algorithm are more important. Inelements of a given group and the right (white) set of stead of using two commands IntoQuasigroup() and vertices () are -hyperedges of the -hypergraph, i.e. LeftMultiplication() from the loops package in the each ∈ () is a -subset of (). An edge between original algorithms, we used one command Action(G two vertices ∈ (), ∈ () is constructed if and , AsList(G), OnRight) which is by default in GAP, only if ∩ ̸= ∅. In the GAP, we constructed the graph i.e. we did not need to import additional package. The command performs the group action of the right multi1 plication on the elements of the group. The results of these two approaches are distinct in the arrangement 2 of vertices in the built graphs which is not relevant as all the constructed graphs from the first approach are 3 isomorphic to all the graphs constructed by the second approach. 4 5
6 obtain a list of all orbits for all -hyperedges without duplications. With the increasing size of and the increasing order of the group, the list of orbits takes a lot Figure 1: Incidence structure of the 3-hypergraph generated of computational time. Instead of the Orbits() comfrom group of order 6 mand, we used the command OrbitsDomain(perm, Combinations([1..order], k), OnSets). The object, i.e. the incidence structure of a -hypegraph, diference between these two commands is in the apwith the command I := Graph(Group(()), proach to the set of -hyperedges built by command [1..Size(vertices)], OnPoints, function Combinations([1..order], k). The Orbits() (x,y)return ((Length(vertices[x])= 1 works with the set of -hyperedges as seeds compare and Length(vertices[y])<> 1)or (Length( to the OrbitsDomain() that works with the set of vertices[x])<> 1 and Length(vertices[y])= hyperedges as a domain. The domain is a structured set 1))and Length(IntersectionSet(vertices[ in GAP, which is closed under the action of the group . x], vertices[y]))>= 1; end, true) from the GRAPE package, where vertices = () ∪ (). 4.3. Creating and accessing orbit Consequently, we got the automorphism group of the incidence structure with AutomorphismGroup(I). If combinations the automorphism group has the same order as the given group, it means the group admits a HRR otherwise the group does not admit a HRR.
nations of orbits with Combinations(orb). Then, we iterated through all of the combinations in a for-loop until we found a regular representation via a -hypergraph 4. Optimizations for a given group. The orbits are represented as sets of hyperedges thus the combinations of orbits are stored as We introduce the optimization methods used to improve a set of sets of sets of -hyperedges. The resulting object the computational time and the memory usage of the of the Combinations() command is demanding on the original algorithms proposed in Section 3. computational memory and becomes more complex with the increasing which makes the approach not efective in the way of the memory usage. 4.1. Left vs. right action The first optimization changed the combinations of In the original algorithms, we used the outcome orbits to the combinations of indexes of orbits. We used of the left multiplication of the group given by command Combinations([1..Size(orb)]) that creLeftMultiplicationGroup() to get the orbits con- ates combinations on elements {1, .., ||} representing sisting of -hyperedges. The left and the right group the indexes of orbits in the orb object. The optimization led to lower memory load since combinations of orbits of HRR’s via -hypergraphs are obtained at the |2| are saved as a set of sets. A disadvantage of the algorithm combinations of orbits. Following these observations, we is that it generates the combinations of orbits that are conjectured that if a given group did not admit a HRR at not needed if we find the HRR for a group in the earlier the |2| -combinations of orbits, it could not be found at combinations. any -combinations of orbits, i.e. the given group does
We optimized the generated combinations of orbits by not have a HRR. Based on the conjecture, we reduced decreasing the amount of computed and not-used com- the number of constructed graphs from 2|| to (︀ || )︀ binations. We gradually created all combinations of size |2| , shortly called -combinations, of indexes one by one, which improved the computational time, in particular for where is in the range 1 ≤ ≤ | |. In the beginning, groups not admitting HRR’s. We computed the specific we generated all -combinations of orbits for = 1. We -combinations of orbits with the iterator object menlooked if a group admits a HRR via a -hypergraph con- tioned in Section 4.3 by specifying the extra parameter : structed from one of the -combinations. If we did not IteratorOfCombinations(orb, c). ifnd a HRR, we moved to ( + 1)-combinations of orbits.
We went one by one through the combinations of orbits 4.5. Correcting the graph object until we either found a HRR for a given group or we To create the graph object expressing the incidence structrabhesitae’wcscheioenmdddiepdxu+netsaot1taiobh>noavav|leemtthoe|em.cWoo-mcriyotphmautnbthedinettahohtpeieotcicnmoosmm,izwbpahtiunieotaarntet,iioowwnneesaflsooatfuivmonerdde- tscueorrmevemidnaanthdseigfronorimficigaintnhtaeflalwGalRgwAoirtPihEthupmsaisnc,kgwatgeheeu.csHeodmowtmheaevneGdrr,aawspeihto(b)ttaahhllceeoH-m-cRcoboRmimnobabfitininaoaangttiriorooennussspu,,.lwttLhihneeigtcruheinssitspaoonfHiontRthtRenoecuocotfemtsahsbaagirtnryoaw.utieIpofgnweesaneraelfriroeeaurntneionddt ittgnhortmeoeurionpcrhtpweahrnicitgshhmeasanstgbhoeiegf,gtstheherteesoocorrrfdiegveairetn,reaatdilscageitlsrgasohprohit(u,hlimd).eab.snefa.douutnodm(mo)rop.rWheisaitmuhused. We decided to use a command BlockDesign(order,
To avoid the computation of not-used combinations hyperedges) from the DESIGN package where order of orbits, we decided on another optimization with the itshothuegshetwen(ee)daenddtohyimpeproertdagnesexistrtahepascektage(,th).eEnveewn tcuormnmsaannditIetraetroartoobrjeOcftCthormobuignhaatliloconms(boinrabt)iownshiocfhthree- command prevented: interchanging the sets of vertices sooeuvtetorthftehorenbeciteosdm.tTbohinsetaoittrieoernaastlolwrthipterhocoovumidtbethsinetahrteieoppneostsiostiifbooinlribtayintsdt.owWloiitothhp- itniotn(hien)ctaohnmedgpruatpa(hti)oc,rnemaalitsitntiamgkefeu.snicntiwonriatinndgwthaes cmoorrreecetficcieonntdithe use of the iterator, we did not need to precompute the combinations of orbits which makes a significant im- 4.6. Optimized algorithm provement in the usage of the computational memory and the computational time of the algorithm.
As the graphs are being constructed based on the combinations of orbits, we easily computed the number of all possible graphs given by -combinations of orbits with ︀( ||)︀ , where || is the total number of orbits. After observing the original algorithms printouts for groups that admit HRR’s, we noticed a given group starts to admit a HRR from some -combinations of orbits and stops to admit a HRR from (|| − )-combinations of orbits. The smallest number of -hypergraphs that are the regular representations of a group is at the starting -combinations of orbits, i. e. the -combination from which the group starts to admit a HRR. The number of -hypergraphs which are a HRR’s increases from the starting up to || and decreases from || to ||− , 2 2 where it is also on its minimum. The maximum number
able to implement a more efective algorithm shown in Algorithm 1. The input to the algorithm is a parameter for the -hypergraph. The optimization from Section 4.1 concerning the change in the group action is used in Operation 5. Next optimization in the way of computing the orbits from Section 4.2 was applied in Operation 6. Optimizations considering the combinations of orbits from Sections 4.3 and 4.4 is showed in Operation 7. The last optimization of constructing the graph object is presented in Operation 8.
Algorithm 1 Pseudocode: Optimized algorithm 1: function (k) 2: for ≤ 32 do 3: for ≤ NrSmallGroup(order) do 4: G = SmallGroup(order, i) 5: perm = Action(G, AsList(G), OnRight) 6: orb = OrbitsDomain(perm, Combinations([1..order], k), OnSets) 7: for comb in IteratorOfCombinations(orb,
Int(Size(orb)/2)) do 8: graph = BlockDesign(order, comb) 9: if Size(AutomorphismGroup(graph)) = order then 10: return ’group has HRR’ 11: break 12: end if 13: end for 14: return ’group does not have HRR’ 15: end for 16: end for 17: end function
The first goal of our computational verification was to ifnd which groups of orders less than or equal to 32 admit or do not admit HRR’s via -hypergraphs, where is in the range 0 ≤ ≤ | |. We obtained results for all groups of orders less than or equal to 32 with their respective values of except for the group Z52. We were able to compute the existence or nonexistence of HRR via -hypergraph for group Z25 only for = 3, 4, 5, 28, 29, 30, 31, 32. All mentioned groups with an associated value of admit a HRR except groups that are shown in Table 1. With the increasing and the increasing order of the group, the computations became more complex considering the computational time and the computational memory. The most challenging was to compute a HRR of a group for the around the middle of the range, i.e., for around |2| , due to a large number 5 of orbits. Especially, the computations for the group Z2 got exhaustive, because of an enormous number of orbits. We are still working on computing the results for the group Z25 and values of in the range 6 ≤ ≤ 27.
starts to admit a HRR via some -hypergraph, it admits One of the main goals was to prove a conjecture by Ja- HRR’s via -hypergraphs until the ≥ | | − . For exjcayova [19]. Based on the results from the previous ample, the group Z7 admits a HRR via a -hypergraph for subsection and Table 1, we proved the conjecture for all = 3, 4 and does not admit a HRR via a -hypergraph groups of orders less than or equal to 32 except the group for = 0, 1, 2, 5, 6, 7. The range from the conjecture Z52 as we do not have results for all values of in the applied to the group Z7 gives the range 3 ≤ ≤ 4 range 0 ≤ ≤ | |. Thus if a group of order not ex- which satisfies the conjecture. We continue with our ceeding 32, except Z25, admits a HRR via a -hypergraph, ex5periments for the remaining open case of the group it also admits HRR’s via -hypergraphs, where the is Z2. in the range ≤ ≤ | | − . In other words, if a group
versity for his advice about managing orbits in Section 4.3 and for the possibility to work with Magma in Section 5.4. I would also like to thank Grahame Erskine from the Open University for his very useful suggestion to use the command BlockDesign() to describe the graph object in Section 4.5. I would like to thank my supervisor Tatiana Jajcayová for her guidance, suggestions and corrections throughout the writing process. The work was partially supported by G-22-173-00 and VEGA 1/0423/20. We performed several runs of the implemented algorithm and analysed the printouts about the minimal needed combinations, where we can find the first -hypergraph satisfying the HRR conditions for a given group. From Section 5.2, we know that if a group starts to have a HRR via a -hypergraph, it admits a HRR via -hypergraph as far as ≤ | | − . The for the minimal needed -combinations to construct a HRR is at its maximum for the -hypergraph, i.e. the starting -hypergraph, and also for the (|| − )-hypergraph. The development of the decreases from to || and consequently in2 creases from |2| to || − . The greatest starting for -combinations we obtain so far is = 6 for the group Z42.Z2. In most of the cases, groups admit HRR ’s with -combinations where = 1, 2. Based on the small , we speeded up our computation for some groups and instead of having (︀ || )︀ possible combinations of orbits, ||
2 we have only (︀ ||)︀ or (︀ ||)︀ combinations of orbits.
1 2
An interesting observation was made with regard to the cyclic groups, where we noticed that cyclic groups of = 6, 7, 8 start to admit HRR’s with a 2-combinations of orbits and cyclic groups of orders greater than or equal to 9 start to admit HRR’s with a 1-combinations of orbits. To obtain HRR’s for the dihedral groups via a 3-hypergraph, we always needed a 2-combinations of orbits. Abelian groups by 3-uniform hypergraphs, Ars Comb. 3 (1977) 15–20. [15] S. Foldes, Symmetries, 1977. [16] S. Foldes, N. M. Singhi, Regular Representation of Finite Groups by Hypergraphs, Canadian Journal of Mathematics 30 (1978) 946–960. doi:10.4153/ CJM-1978-082-9. [17] R. Jajcay, Representing Finite Groups As Regular Automorphism Groups Of Combinatorial Structures, Ars Comb. 62 (2002). [18] R. Jajcay, T. Jajcayová, k-hypergraphs with regular automorphism groups, Acta Mathematica Universitatis Comenianae 88 (2019) 835– 840. URL: http://www.iam.fmph.uniba.sk/amuc/ojs/ index.php/amuc/article/view/1257. [19] T. Jajcayová, Regular actions of groups and inverse semigroups on combinatorial structures, url: https://ciencias.ulisboa.pt/sites/default/files/ fcul/public/CSA2016-Jajcayova.pdf , 2016. [20] GAP system for computational discrete algebra, 1986. URL: https://www.gap-system.org/index. html. [21] L. H. Soicher, GRAPE, 1993. URL: https://www.
gap-system.org/Packages/grape.html. [22] G. P. Nagy, P. Vojtěchovský, loops, 2015. URL: https: //www.gap-system.org/Packages/loops.html. [23] L. H. Soicher, DESIGN, 2006. URL: https://www. gap-system.org/Packages/design.html.