Constructions of Hypergraphical Regular Representations via -uniform Hypergraphs of Certain Groups of Order Greater than 32

Abstract

The article explores the problem of hypergraphical regular representation of finite group via -uniform hypergraph. A hypergraphical regular representation preserves the group's structure within the hypergraph. The paper builds upon previous research and investigates hypergraphical regular representations of certain groups of orders greater than 32. The paper presents an algorithm based on methods by Mihálová and Erskine and Tuite. The algorithm is implemented in the computational system GAP to find hypergraphical regular representations for certain groups. The results include a table with groups for which hypergraphical regular representations via -uniform hypergraphs were obtained.

Keywords

• eol>Hypergraphical Regular Representation
• Groups
• -uniform hypergraph
• Dual hypergraphs
• GAP

1. Introduction

an exponent greater than 2, generalised dicyclic groups, a group isomorphic to one of 13 groups whose order is A hypergraph is a generalisation of a graph where a hy- not greater than 32 (Z22, Z23, Z24, D3, D4, D5, A4, Q × Z3, peredge can connect more than two vertices. We are Q × Z4, ⟨, , | 2 = 2 = 2 = 1, = = ⟩, focusing on the problem of hypergraphical regular rep- ⟨, | 8 = 2 = 1, − 1 = 5⟩, ⟨, , | 3 = 3 = resentation of groups. We seek to find hypergraphs that 2 = 1, = , ()2 = ()2 = 1⟩, ⟨, , | 3 = faithfully represent the structure of a group by preserving 3 = 3 = 1, = , = , − 1 = ⟩). Later, its symmetries. Babai[ 3 ] raised and solved the question concerning the

The problem of hypergraphical regular representation regular representation of a group via directed graphs. He was formulated as an extension of the graphical regular published a complete list of groups not admitting the direpresentation problem. Given a graph Γ , an automor- graphical regular representation: Z22, Z23, Z24, Z32 and Q8. phism of Γ is a permutation of the vertex set, such that An overview of diferent types of regular representations the vertices and form an edge if and only if the ver- was presented by Spiga [ 4 ]. tices () and () also form an edge. The set of all auto- We build upon the previous research and investigate morphisms of Γ together with the operation of composi- the problem of hypergraphical regular representation for tion forms the automorphism group (Γ) . The graphi- certain groups of orders greater than 32. Section 2 covers cal regular representation (GRR) of a group is a graph Γ the necessary concepts, including definitions of hyperwhose automorphism group is the group in its regular graphs, hypergraphical regular representation and dual action. The search for representations of groups started structures. In Section 3, we present an overview of the with Kőnig in 1936 [ 1 ]. He posed a question: Does there ex- previous research and results in hypergraphical regular ist a graph Γ for a given group such that (Γ) ∼= ? representation. In Section 4, we describe the methods by Two years later, Frucht showed that for every finite group Mihálová [ 5 ] and Erskine and Tuite [ 6 ] that we used to , there exist infinitely many non-isomorphic connected obtain the hypergraphical regular representation of cergraphs Γ such that (Γ) is isomorphic to . How- tain groups of order greater than 32. Section 5 contains ever, the automorphism groups of these graphs are not our algorithm, which was implemented in computational necessarily regular. Multiple researchers worked on the system GAP. We describe particular commands in more problem of graphical regular representation over the detail. In Section 6, we present our results with a table years. Godsil [ 2 ] summed up the previous findings and containing groups for which we found a hypergraphical published the complete list of groups not admitting a regular representation via -uniform hypergraph. graphical regular representation: abelian groups with

2. Preliminaries

ordered pair of the vertex set (Γ) and the hyperedge by the elements of group acting on E (Γ) . It can be set E (Γ) . In certain contexts, hyperedges may be referred defined formally as · = { · | ∈ , ∈ E (Γ) }, to as blocks. Each hyperedge ∈ E (Γ) is a nonempty where is the group acting on E (Γ) and · is the induced subset of the vertex set (Γ) , i.e. 1 ≤ | | ≤ | (Γ) |. action of on E (Γ) . The intersection of diferent orbits Generally, hyperedges are blocks of various sizes. Our fo- is empty. cus is on -uniform hypergraphs, which are hypergraphs An incidence structure of a hypergraph Γ is an ordered with hyperedges of the same size , i.e. ∀ ∈ E (Γ) : pair I = ( (I ), (I )). The vertex set (I ) is a || = . Note that a 2-uniform hypergraph is also an partition into two disjoint sets: 1 = (Γ) and 2 = undirected graph. Our method requires working with E (Γ) . The edge set satisfies (I ) ⊆ 1 × 2. Vertices hypergraphs whose vertices are in the same number of ∈ 1 and ∈ 2 are incident if ∈ , i.e. (I ) = hyperedges. The degree () of a vertex in a hypergraph {(, )| ∈ , ∈ E (Γ) }. The incidence structure of Γ is the number of hyperedges which contain the vertex a hypergraph Γ preserves the symmetries of Γ . Based on . A hypergraph is -regular if all vertices have the same [ 8 ], the automorphism group of the incidence structure degree , i. e. ∀ ∈ (Γ) : () = . An automorphism of a hypergraph Γ is isomorphic to the automorphism of a hypergraph Γ is a bijection : (Γ) ↦→ (Γ) such group of Γ (Fig. 1). that vertices 1, 2, ..., ∈ (Γ) form a hyperedge if In our method, we are using the concept of dual inand only if vertices (1), (2), ..., () ∈ E (Γ) also cidence structure. A dual incidence structure I * = form a hyperedge. The automorphism group (Γ) of a ( (I * ), (I * )) of the incidence structure I is an orhypergraph Γ is formed by the set of all automorphisms dered pair of the vertex set (I * ) and the edge set of the hypergraph with the operation of composition. (I * ). The partitions in the vertex set are swapped Since we are dealing with groups and hypergraphs, defin- compared to the partitions in the incidence structure. ing a Cayley hypergraph is in place. Over the years, sev- Given a hypergraph Γ , the partitions of the dual incieral definitions of Cayley hypergraphs have been formu- dence structure are 1 = E (Γ) and 2 = (Γ) (Fig. 2). lated. The definitions difer in their approach to creating We use the knowledge of complementary hypergraphs. hyperedges and in the minimal possible size of hyper- Let Γ be a -uniform hypergraph. By Γ , we denote edges. We choose the definition by Jajcay and Jajcayova a -uniform hypergraph defined as an ordered pair in [ 7 ] because it best suits our problem. Let P() be ( (Γ) , P( (Γ)) ∖E (Γ)) , i.e. the hyperedges of Γ are the powerset of the elements of , be the left regular complements of the hyperedges of Γ . By , we denote action of and be ⋃︀=1 , where ∈ P() for a ( (Γ) − )-uniform hypergraph, where E ( ) are 1 ≤ ≤ | P()|. A Cayley hypergraph (, ) complements of E (Γ) of size (Γ) − . is a hypergraph Γ with the elements of as the vertex set and the elements of as the hyperedge set. For a -uniform (, ) it holds that ∈ P(). 3. Previous research and similar

We can define the regular representation of hy- questions pergraphs based on previous definitions. The hypergraphical regular representation (HRR) of a group Foldes and Singhi [ 9 ] were the first to investigate the is a Cayley hypergraph (, ) where for ev- problem of hypergraphical regular representation. They ery two vertices , ∈ ((, )), there ex- proved the existence of a hypergraphical regular repreists exactly one automorphism such that () = sentation via a 3-uniform hypergraph for every finite from the automorphism group of the hypergraph group of odd order greater than or equal to 57. In the ((, )). This means that the automorphism same year, Foldes [ 10 ] proved that cyclic groups Z (exgroup ((, )) acts regularly on the set of cept = 3, 4, 5) admit regular representation using a 3vertices of ((, )). Several researchers have uniform hypergraph. Collaboratively, Foldes and Singhi studied the existence of hypergraphical regular represen- [ 11 ] established a polynomial lower bound () for the tations for various groups and types of hypergraphs. order of the group that admits a hypergraphical regular

Since we use groups in our research, concepts from representation via -uniform hypergraph for ≥ 3. For group theory and their connection to hypergraphs are every finite group such that () ≤ | |, there exists needed. Given a group and a set , the group action a -uniform hypergraph which is a hypergraphical regof on is a map · : × ↦→ (denoted as · , ular representation of . The lower bound for = 3 ∀ ∈ , ∈ ) with the following properties: ∀1, 2 ∈ is (3) > 26 and for ≥ 4 is () > 4 + 2. They , ∀ ∈ : 1 · (2 · ) = (1 · 2) · and ∀ ∈ : suggested that for = 3, the lower bound should be 1 · = . An orbit of an element ∈ under the action improved to a linear polynomial of the form + , where of a group on a set is denoted as · . In particular is a constant. Jajcay [12] studied the problem of hyperfor hyperedges, an orbit of a hyperedge ∈ E (Γ) is the graphical regular representation for hypergraphs whose set of all hyperedges in E (Γ) that are equivalent to hyperedges are not necessarily regular. He improved the 1 3

Hypergraph Incidence structure 2 4 a group that does not admit a hypergraphical regular representation via a non-uniform hypergraph does not admit a hypergraphical regular representation via a uniform hypergraph. Furthermore, Jajcay and Jajcayova [13] listed the groups without a hypergraphical regular representation by 3-uniform hypergraphs. The list includes the groups mentioned in [12], as well as some other groups: Z3, Q8, Z23, Z34, Z53, D5 × Z5. Their colleague Martin Mačaj verified computationally that there exists a hypergraphical regular representation through 3-uniform hypergraph for groups of order 6 ≤ | | ≤ 32.

Recently, we computationally verified [ 5 ] a generalised conjecture by Jajcayová [14]. We stated which groups admit or do not admit a hypergraphical regular representation via -uniform hypergraph for groups of orders less than or equal to 32 and the whole spectrum of 3 ≤ ≤ | |.

4. Overview of methods

{1, 2}

We aim to find hypergraphical regular representations 1 for groups of order greater than 32. We already found hy{1, 3} pergraphical representations of groups of order less than

33 in [ 5 ]. However, exhaustive search, the main method 2 {1, 4} in [ 5 ], is challenging for groups of greater order. We decided to merge the method from [ 5 ] with the method by {2, 3} Erskine and Tuite in [ 6 ] to obtain hypergraphical regular 3 representation for groups of greater order. We briefly describe these methods.

{2, 4} The computational method in [ 5 ] was based on theoret4 ical proofs in [13]. We went through all groups of orders {3, 4} less than 33. For each group, we computed the permutation of the right multiplication for each element within the group. Based on the permutations, we obtained orFigure 1: For illustration, the hypergraph Γ (which is a bits of -uniform hyperedges. As a next step, we went tshime pselet ogfrahpyhp)erheadsgetsheE (sΓet) o=f v{e{r1t,ic2e}s, {1(,Γ3)}, ={1,{41},,2{,23,,34}},, through all combinations of orbits. We constructed the {2, 4}, {3, 4}} and (Γ) = S4. hypergraph and asked for its automorphism group. If The incidence structure I of the hypergraph Γ is an the order of the automorphism group was equal to the undirected graph with the vertex set 1 = (Γ) and order of the group, we confirmed the existence of the 2 = E (Γ) and the edge set (I ) = {(1, {1, 2}), hypergraphical regular representation for that group. (1, {1, 3}), (1, {1, 4}), (2, {1, 2}), (2, {2, 3}), (2, {2, 4}), Erskine and Tuite [ 6 ] used their method to obtain new (3, {1, 3}), (3, {2, 3}), (3, {3, 4}), (4, {1, 4}), (4, {2, 4}), record graphs. A record graph is a graph with the smallest (4, {3, 4}) and (S ) = S4. known number of vertices for a given girth (size of the The automorphism groups of I and Γ are isomorphic. smallest cycle in the graph) and degree of vertices. We will adopt their method to create a -regular -uniform hypergraph Γ and construct an incidence structure I lower bound () ≥ 6 for hypergraphs with varying from Γ (Fig. 1). Subsequently, we obtain dual incidence sizes of hyperedges. Also, he showed the non-existence structure I * from which we can obtain a -regular of a hypergraphical regular representation for four fi- uniform hypergraph known as the dual hypergraph Γ * nite groups Z3, Z4, Z4, Z22. It supports the findings in (Fig. 2). The dual hypergraph Γ * has the same automor[ 10 ]. Nonetheless, his solution heavily depends on hy- phism group as the original hypergraph Γ . However, the pergraphs with hyperedges of diferent sizes. In this case, order of the dual hypergraph is | (Γ) |. The order of criteria for admitting a regular representation are less re- Γ * can be smaller, equal or greater than the order of Γ strictive than for -uniform hypergraphs. Consequently, depending on values of and .

Dual incidence structure

5. Algorithm

Second, if |(Γ) | = ( − | E (Γ) |), we are able to construct a complement hypergraph Γ to hypergraph Γ . The hypergraph Γ is a hypergraphical regular representation via -regular ( − )uniform hypergraph for group , where ∼= (Γ) . Third, if |(Γ) | = |E ( )|, we can obtain a complement hypergraph to hypergraph Γ . The hypergraph is a hypergraphical regular representation via regular ′-uniform hypergraph, where ∼= (Γ) and ′ is the regularity of .

Algorithm 1 Pseudocode (one group): identifying HRR

of groups of greater order function(order, i, k) group = SmallGroup(order, i) permutations = Action(group,AsList(group),OnRight) orbits = OrbitsDomain(permutations, Combinations([1..order], k), OnSets) numAllEdges = Binomial(order, k) maxDegree = numAllEdges * k / order bound = Int(Size(orbits)/2) for 1 ≤ numOfOrbits ≤ bound do for all combinations of orbits of size do edges = Concatenation(combination of orbits) gamma = BlockDesign(order, edges) if gamma is regular then autGroup = AutomorphismGroup(gamma) if || > 32 then if || = || then

print found -regular -uniform HRR end if if || = ( − ||) then print found -regular ( − )-uniform HRR (complement 1) end if if || = NrBlockDesign- plored for greater values of since the computational Blocks(ComplementBlockDesign(gamma)) complexity and time increased with increasing . Also, then the density of printed results decreased with increasing print found ( − )-regular ′- . We attribute the smaller amount of printouts to the uniform HRR (complement 2) fact that with increasing , there is a higher probability end if of finding hypergraphical regular representation via end if uniform hypergraph for the starting group . However, end if we are more interested in -uniform hypergraphs Γ that end for are not regular representations of the starting group end for as (Γ) ≉ and |(Γ) | is greater (or smaller) than end function ||. Thus, these -uniform hypergraphs can be regular representations for groups of greater (or smaller) order than .

We first launched our algorithm without the restriction |(Γ) | > 32 to verify our algorithm by obtaining hypergraphical regular representations for groups of orders smaller than 33. We obtained numerous hy

6. Results of experiments

We ran our algorithm for groups of orders smaller than

15. Groups of order greater than 10 were not fully exI want to thank my supervisor Tatiana Jajcayová for her guidance, suggestions and corrections throughout the writing process. pergraphical regular representations for those groups [12] R. Jajcay, Representing Finite Groups As Reguthat confirmed the correctness of our algorithm. Then, lar Automorphism Groups Of Combinatorial Strucwe looked for hypergraphical regular representations of tures, Ars Combinatoria 62 (2002) 51–64. groups of orders greater than 32. Groups and values of , [13] R. Jajcay, T. Jajcayová, k-hypergraphs with for which we found hypergraphical regular representa- regular automorphism groups, Acta Mathetions via -uniform hypergraphs, are presented in Table matica Universitatis Comenianae 88 (2019) 835– 1. The names of the groups are in GAP notation. Most 840. URL: http://www.iam.fmph.uniba.sk/amuc/ojs/ of the hypergraphical regular representations are from index.php/amuc/article/view/1257. complementary hypergraphs . [14] T. Jajcayová, Regular actions of groups and inverse semigroups on combinatorial structures, url: https://ciencias.ulisboa.pt/sites/default/files/ Acknowledgments fcul/public/CSA2016-Jajcayova.pdf , 2016. [15] T. G. Group, GAP - Groups, Algorithms, and

Programming, Version 4.12.2, url: https://www. gap-system.org, 2022.

References

[1] D. Kőnig , Theorie Der Endlichen und Unendlichen Graphen: Kombinatorische Topologie Der Streckenkomplexe, Mathematik und ihre anwendungen in monographien und lehrbüchern , Chelsea , 1936 .

[2] C. D. Godsil , GRR's for non-solvable groups, Algebraic methods in graph theory , Vol. I, Conf. Szeged 1978 , Colloq. Math. Soc. Janos Bolyai 25 , 221 - 239 ( 1981 )., 1981 .

[3] L. Babai , Finite digraphs with given regular automorphism groups , Periodica Mathematica Hungarica 11 ( 1980 ) 257 - 270 .

[4] P. Spiga , The beauty of counting cayley graphs , url: https://drive.google.com/file/d/ 1-QjDoKw6j0rblcli2VeR5TWOX8yAC8mJ/view, 2022 .

[5] D. Mihálová , Computer verifications of regular representations of groups of orders smaller than 32 via k-hypergraphs, CEUR-WS Proceedings ( 2022 ) 196 - 203 .

[6] G. Erskine , J. Tuite , Small graphs and hypergraphs of given degree and girth, 2022 . URL: https://arxiv. org/abs/2201.07117. doi: 10 .48550/ARXIV.2201. 07117.

[7] T. Jajcayová , R. Jajcay , Generalizations of cayley graphs to uniform hypergraphs, 2023 .

[8] E. M. Luks , Hypergraph isomorphism and structural equivalence of boolean functions , in: Symposium on the Theory of Computing , 1999 .

[9] S. Foldes , N. M. Singhi , Regular representation of Abelian groups by 3-uniform hypergraphs , Ars Comb . 3 ( 1977 ) 15 - 20 .

[10] S. Foldes , Symmetries, 1977 .

[11] 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.