Some applications of pq-groups in graph theory

We describe some new applications of nonabelian pq-groups to construction problems in Graph Theory. The constructions include the smallest known trivalent graph of girth 17, the smallest known regular graphs of girth five for several degrees, along with four edge colorings of complete graphs that improve lower bounds on classical Ramsey numbers. For primes p and q such that p < q and q ≡ 1 (mod p), there exists a nonabelian group of order pq, which is a semidirect product of Zq by Zp [3]. In this note, we use these groups to construct several graphs and graph colorings. Let G be a nonabelian pq-group and let a and b be elements of orders p and q, respectively. The subgroup generated by b is normal in G and a−1ba = b where r ≡ 1 (mod q). So the elements of G can be represented in the form ab , for 0 ≤ i < p and 0 ≤ j < q. Group multiplication can be defined by ab ∗ ab = ab s+t. In what follows, it will be convenient to refer to elements of a pq-group using the notation (i, j) instead of ab . 1 Ramsey Graphs Recall that an (s, t)-coloring of the complete graph Kn is a 2-coloring of its edges such that there is neither a complete subgraph of order s, all of whose edges are color 1, nor a complete subgraph of order t, all of whose edges are color 2. The Ramsey number R(s, t) is the minimum n such that no (s, t) coloring on Kn exists. Our first application of pq-groups gives us a new lower bound for R(4, 8). For this we use a Cayley coloring on the nonabelian group G of order 55, where we take p = 5, q = 11, and r = 3. Note that in a Cayley coloring, we assign