Top

Applicable Algebra in Engineering, Communication and Computing

Open Access 10-01-2023 | Original Paper

The automorphism group of projective norm graphs

Authors: Tomas Bayer, Tamás Mészáros, Lajos Rónyai, Tibor Szabó

Published in: Applicable Algebra in Engineering, Communication and Computing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Patentsearch

Off

Abstract

The projective norm graphs are central objects to extremal combinatorics. They appear in a variety of contexts, most importantly they provide tight constructions for the Turán number of complete bipartite graphs $K_{t,s}$ with $s>(t-1)!$. In this note we deepen their understanding further by determining their automorphism group.

The content of this note appears within a longer arXiv-manuscript [12], which will not be published in that form. The rest of the material of [12] and the material of [30] is restructured and combined into a longer manuscript, that will be published elsewhere. The main result here also appeared without proof in an extended abstract [13] of EUROCOMB 2019.

Supported by a DRS Fellowship of Freie Universität Berlin.

Supported by GIF Grant G-1347-304.6/2016.

Supported by NKFIH (Hungary) through the Program of Excellence TKP2021-NVA-02 at the Budapest University of Technology and Economics.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

Turán-type problems play a central role in extremal combinatorics. In the classic setting, given a graph H and integer $n\in \mathbb {\uppercase {N}}$, one is interested in determining the Turán number of H, denoted by ${{\,\mathrm{ex}\,}}(n,H)$, which is the maximum number of edges a simple graph on n vertices may have without containing a subgraph isomorphic to H. In a series of results by Mantel [29], Turán [46], Erdős and Stone [18], and Erdős and Simonovits [17] the asymptotics of the function ${{\,\mathrm{ex}\,}}(n,H)$ was obtained, whenever H is not bipartite. Unfortunately, when H is bipartite these results merely imply that ${{\,\mathrm{ex}\,}}(n,H)$ is of lower than quadratic order. A general classification of the order of magnitude of bipartite Turán numbers is widely open, even in the simplest-looking cases of even cycles and complete bipartite graphs. Kővári, T. Sós and Turán [24], using an elementary double counting argument, proved the general upper bound ${{\,\mathrm{ex}\,}}(n, K_{t,s})=O\left( n^{2-\frac{1}{t}}\right)$ and in general it is commonly conjectured that this is actually the right order of magnitude.

For a matching lower bound, one needs to exhibit a $K_{t,s}$-free graph that is dense enough. The first such constructions were found for $K_{2,2}$-free graphs (attributed to Esther Klein by Erdős [16]) and later for $K_{3,3}$-free graphs (Brown [14]). In [21] Kollár, Rónyai and Szabó constructed norm graphs, which are provably $K_{t,t!+1}$-free and their density matches the order of magnitude of the Kővári-Sós-Turán upper bound. Later, Alon, Rónyai and Szabó [4] modified this construction to obtain projective norm graphs, the principal object of this note, and verified the conjecture for $s>(t-1)!$.

For a prime power $q=p^k$ and integer $t\ge 2$ let $N:\mathbb {\uppercase {F}}_{q^{t-1}}\rightarrow \mathbb {\uppercase {F}}_q$ denote the $\mathbb {\uppercase {F}}_q$-norm on $\mathbb {\uppercase {F}}_{q^{t-1}}$, i.e. for $A\in \mathbb {\uppercase {F}}_{q^{t-1}}$ we have $N(A)=A\cdot A^q\cdot A^{q^2}\cdots A^{q^{t-2}}\in \mathbb {\uppercase {F}}_q$ . The projective norm graph ${\rm NG}(q,t)$ has vertex set $\mathbb {F}_{q^{t-1}}\times \mathbb {F}_q^{*}$ and two vertices (A, a) and (B, b) are adjacent if and only if $N(A+B)=ab$. For details on finite fields and the norm function the interested reader may consult e.g. [27].

In [6], using a general algebro-geometric lemma from [21], it was shown that $(q,t)$ is $K_{t,(t-1)!+1}$-free. A simple counting shows that ${\rm NG}(q,t)$ also has the desired density, and so it verifies the Kővári-Sós-Turán conjecture for $s>(t-1)!$.

2 The automorphism group

Since their first appearance, (projective) norm graphs were studied extensively [1, 9, 10, 20, 23, 34, 39]. Their various properties were utilized in many other areas, both within and outside combinatorics. These include, among others, (hypergraph) Ramsey theory [4, 22, 25, 31‐33, 49, 50], (hypergraph) Turán theory [1, 2, 36, 37, 39, 40], other problems in extremal combinatorics, [6, 11, 28, 41, 44, 45], number theory [35, 43, 47, 48], geometry [19, 38] and computer science [3, 7, 8, 15].

In this note we investigate the symmetries of projective norm graphs. We believe that a full understanding will prove to be helpful in further applications of these important combinatorial structures.

As usual, it is not difficult to stumble upon all the automorphisms, the main point is rather to show that there are no more. For odd q there are two, for even q there are three families of automorphisms which describe all symmetries. For one, Frobenius automorphisms of $\mathbb {\uppercase {F}}_{q^{t-1}}$, applied to both coordinates of the vertices, define $k(t-1)$ graph automorphisms. Then, multiplication of the first coordinate with any nonzero square $C^2 \in \mathbb {F}_{q^{t-1}}$ and of the second coordinate with (plus or minus) of the norm N(C) provides $q^{t-1}-1$ further graph autopmorphisms. Finally, for even q, the $q^{t-1}$ translations of the first coordinate by some $A\in \mathbb {\uppercase {F}}_{q^{t-1}}$ also define graph automorphisms. Any combination of these types of automorphisms give a different automorphism of ${\rm NG}(q,t)$.

Lemma 1

For any odd prime power $q=p^k$ and integer $t\ge 2$, the maps of the form

$$\begin{aligned} (X,x)\mapsto \left( C^2 \cdot X^{p^i}, \pm N(C) \cdot x^{p^i} \right) \end{aligned}$$

are automorphisms of NG$(q,t)$ for any choice of $C\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$ and $0\le i < k(t-1)$.

For any $q=2^k$ and integer $t\ge 2$, the maps of the form

$$\begin{aligned} (X,x)\mapsto \left( C^2 \cdot X^{p^i}+A, N(C) \cdot x^{p^i} \right) \end{aligned}$$

are automorphisms of NG$(q,t)$ for any choice of $C\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$, $A\in \mathbb {\uppercase {F}}_{q^{t-1}}$ and $0\le i < k(t-1)$.

Moreover, we will also show that all automorphisms can be represented this way. In the next statement $Z_n$ denotes the cyclic group of order n.

Theorem 1

For $q>2$ and $t\ge 2$ the maps described in Lemma 1 include all automorphisms and the automorphism group has the following structural description:

$$\begin{aligned} {{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))\simeq \left\{ \begin{array}{ll} Z_{q^{t-1}-1}\rtimes Z_{k(t-1)}&{} \text {if } q \text { and }t-1 \text { are both odd,}\\ \left( Z_2\times Z_{\frac{q^{t-1}-1}{2}}\right) \rtimes Z_{k(t-1)}&{} \text{ if } q\text { is odd and }t-1 \text { is even,}\\ \left( E_{q^{t-1}}\rtimes Z_{q^{t-1}-1}\right) \rtimes Z_{k(t-1)}&{} \text{ if }\, q \text { is even,} \end{array}\right. \end{aligned}$$

where $E_{q^{t-1}} = (Z_2)^{k(t-1)}$ is the additive group of $\mathbb {\uppercase {F}}_{q^{t-1}}$

Remark

Note that if $q=2$ then NG$(2,t)$ is a complete graph on $2^{t-1}$ vertices, and so ${{\,\mathrm{Aut}\,}}({\text{NG}}(2,t))$ is the whole symmetric group of order $2^{t-1}$.

Whenever $N(2X) = x^2$, the vertex (X, x) has a loop edge. In this paper we choose to deal with the version of projective norm graphs where these (few) loop edges are not deleted forcefully, just to obtain a simple graph. This avoids some inconveniencies and one can check that the deletion of the loop edges does not affect the symmetries.

3 Preliminaries

3.1 Common neighbourhood of pairs of vertices

For a set U of vertices in a graph G we denote their common neighbourhood by $\mathcal {N}(U)$.

Proposition 1

Given two different vertices $(X_1,x_1),(X_2,x_2)\in V({\text{NG}}(q,t))$, we have

$$\begin{aligned} |\mathcal {N}\left( \left\{ (X_1,x_1),(X_2,x_2)\right\} \right) |=\left\{ \begin{array}{ll} \frac{q^{t-1}-1}{q-1} &{} \text {if } X_1\ne X_2 \text { and } x_1\ne x_2,\\ \frac{q^{t-1}-1}{q-1}-1 &{} \text {if } X_1\ne X_2 \text { and } x_1=x_2,\\ 0 &{} \text {if } X_1=X_2. \end{array}\right. \end{aligned}$$

Proof

By definition, a vertex (A, a) is a common neighbour of $(X_1,x_1)$ and $(X_2,x_2)$ if both $N(X_1+A)=x_1a$ and $N(X_2+A)=x_2a$ hold. Dividing one equation by the other one we obtain

$$\begin{aligned} \frac{N(X_1+A)}{N(X_2+A)}=N\left( \frac{X_1+A}{X_2+A}\right) = \frac{x_1}{x_2}. \end{aligned}$$

(1)

If $X_1=X_2$, this necessarily implies $x_1=x_2$, which contradicts the assumption that the vertices $(X_1,x_1)$ and $(X_2,x_2)$ are different.

From now on assume $X_1\ne X_2$. Then, for any solution A of Equation 1 we have a unique common neighbour (A, a) with $a= \frac{N(X_1+A)}{x_1}=\frac{N(X_2+A)}{x_2}$. It is well known that the map $A \mapsto \frac{X_1+A}{X_2+A}$ maps $\mathbb {\uppercase {F}}_{q^{t-1}}\setminus \{-X_2\}$ bijectively to $\mathbb {\uppercase {F}}_{q^{t-1}}\setminus \{1\}$. This, together with the fact $\left| N^{-1}\left( \frac{x_1}{x_2}\right) \right| = \frac{q^{t-1}-1}{q-1}=m$ and $N(1)=1$ implies that we have m common neighbours when $x_1\not =x_2$, and $m-1$ common neighbours if $x_1=x_2$. $\square$

4 The proof

Proof of Lemma 1

First note that the map $X\mapsto X^{p^i}$ is an automorphism of $\mathbb {\uppercase {F}}_{q^{t-1}}$ for every $i\in \mathbb {\uppercase {N}}$, in particular it is bijective and commutes with the field operations and the norm function. Therefore, for any $C\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$ and $i\in \mathbb {\uppercase {N}}$ we have

$$\begin{aligned} (X,x) \sim (Y,y)\ \Leftrightarrow \ N(X+Y)= & \, xy\ \Leftrightarrow \ N(X+Y)^{p^i} = (xy)^{p^i}\\ \Leftrightarrow \ N\left( X^{p^i}+Y^{p^i}\right)= & \, x^{p^i} y^{p^i}\ \Leftrightarrow N\left( C^2\right) N\left( X^{p^i}+Y^{p^i}\right) = \big (N(C)\big ) ^2 x^{p^i} y^{p^i}\\ \Leftrightarrow \ N\left( C^2 X^{p^i}+C^2 Y^{p^i}\right)= & \, \left( \pm N(C) x^{p^i}\right) \left( \pm N(C) y^{p^i}\right) \\\Leftrightarrow \ \left( C^2 X^{p^i},\pm N(C) x^{p^i} \right) \sim & \left( C^2 Y^{p^i}, \pm N(C) y^{p^i}\right) . \end{aligned}$$

Hence all maps presented are indeed automorphisms of ${\rm NG}(q,t)$. Furthermore, when q is even then $2A=0$ for every $A\in \mathbb {\uppercase {F}}_{q^{t-1}}$, and hence, by continuing the previous series of equivalences, we have

$$\begin{aligned} ( X,x ) \sim ( Y,y)\ \Leftrightarrow \ \left( C^2 X^{p^i}+A, N(C) x^{p^i} \right) \sim \left( C^2 Y^{p^i}+A, N(C) y^{p^i}\right) \end{aligned}$$

completing the argument for even q as well. $\square$

Proof of Theorem 1

We start by observing that any $\varPhi \in {{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$ must act independently on the two coordinates.

Lemma 2

Let $q=p^{k}$ be a prime power, $t\ge 2$ an integer and $\varPhi \in {{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$. Then there are permutations $\varPsi :\mathbb {\uppercase {F}}_{q^{t-1}}\rightarrow \mathbb {\uppercase {F}}_{q^{t-1}}$ and $\psi :\mathbb {\uppercase {F}}_q^*\rightarrow \mathbb {\uppercase {F}}_q^*$ such that

$$\begin{aligned} \varPhi \big ( (X,x)\big ) = \big ( \varPsi (X), \psi (x) \big ) \end{aligned}$$

and $\varPsi (-X)=-\varPsi (X)$ for all $X\in \mathbb {\uppercase {F}}_{q^{t-1}}$.

Proof

We say that a set $S \subseteq V({\text{NG}}(q,t))$ of vertices is poor if for any two different vertices $u,v\in S$ we have $|\mathcal {N}(\{u,v\})|<\frac{q^{t-1}-1}{q-1}$. By Proposition 1$|\mathcal {N}(\{ (X,x), (Y,y)\}) |< \frac{q^{t-1}-1}{q-1}$ if and only if either $X=Y$ or $x=y$. Hence a set of vertices is poor if and only if either all the first or all the second coordinates are equal. In particular maximal poor sets are one of two types: either $S_x=\{(A,x)\ |\ A\in \mathbb {\uppercase {F}}_{q^{t-1}}\}$ for some $x\in \mathbb {\uppercase {F}}_q^*$, or $S_X=\{(X,a)\ |\ a\in \mathbb {\uppercase {F}}_q^*\}$ for some $X\in \mathbb {\uppercase {F}}_{q^{t-1}}$. The sizes of such sets are $q^{t-1}$ and $q-1$, respectively.

The automorphism $\varPhi$ must map a maximal poor set to a maximal poor set. Because of the size difference between the two types of maximal poor sets, and since $\varPhi$ is a bijection, $\varPhi$ must permute the maximal poor sets of each type within themselves. That is, there exist permutations $\psi :\mathbb {\uppercase {F}}_q^*\rightarrow \mathbb {\uppercase {F}}_q^*$ for which we have $\varPhi (S_x)=S_{\psi (x)}$ and $\varPsi :\mathbb {\uppercase {F}}_{q^{t-1}}\rightarrow \mathbb {\uppercase {F}}_{q^{t-1}}$ for which we have $\varPhi (S_X)=S_{\varPsi (X)}$.

Since $(X,x) \in S_X\cap S_x$, we have

$$\begin{aligned} \varPhi ((X,x)) \in \varPhi (S_X)\cap \varPhi (S_x) = S_{\varPsi (X)} \cap S_{\psi (x)} = \{ (\varPsi (X), \psi (x))\}. \end{aligned}$$

Consequently $\varPhi ((X,x)) = (\varPsi (X), \psi (x))$, as desired.

For the last statement note that the maximal poor sets $S_X$ and $S_Y$ have no edge between them if and only if $Y=-X$. (Otherwise $N(X+Y)/x=y \in \mathbb {\uppercase {F}}_q^*$ for every $x\in \mathbb {\uppercase {F}}_q^*$.) Consequently $\varPhi (S_X)=S_{\varPsi (X)}$ and $\varPhi (S_{-X})=S_{\varPsi (-X)}$ should also have no edge in between them, which implies $\varPsi (-X)=-\varPsi (X)$, as desired. $\square$

For what follows, fix $\varPhi \in {{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$ together with the permutations $\varPsi :\mathbb {\uppercase {F}}_{q^{t-1}}\rightarrow \mathbb {\uppercase {F}}_{q^{t-1}}$ and $\psi : \mathbb {\uppercase {F}}_q^*\rightarrow \mathbb {\uppercase {F}}_q^*$ guaranteed by Lemma 2.

First we suppose that $t>2$. To obtain further properties of $\varPsi$ and $\psi$ in this case we will need a result of Lenstra [26]. For a field extension $L\supseteq K$ a bijection $f:L\rightarrow L$ is called a K-semilinear L-automorphism, if $f(x + y) = f(x) + f(y)$ for every $x,y\in L$ (that is, f is an automorphism of the additive group of L), and there is an $h\in {{\,\mathrm{Aut}\,}}(K)$ such that $f(x\cdot y) = h(x) \cdot f(y)$ for every $x\in K, y\in L$. If $K=L$, the notion of semilinearity simplifies significantly.

Lemma 3

Let L be a field. Then f is an L-semilinear L-automorphism if and only if there is an $h\in {{\,\mathrm{Aut}\,}}(L)$ and element $C\in L^*$ such that $f(x) = C \cdot h(x)$ for every $x\in L$.

Proof

By definition, if f is an L-semilinear L-automorphism then there is some $h \in {{\,\mathrm{Aut}\,}}(L)$ such that $f( x \cdot 1) = h(x) \cdot f(1)$ for every $x\in L$, proving that f is of the desired form with $C=f(1)$. Conversely, if f is of the given form then, since h is an L-automorphism, it is also an automorphism of the additive group of L, and $f(x\cdot y) = C \cdot h(x\cdot y) = C\cdot h(x) \cdot h (y) = h(x) \cdot f(y) = f(x) \cdot h(y)$. $\square$

Theorem 2

(Lenstra ( [26, Theorem 2])) Let F be a finite field, E a non-trivial abelian group, $g: F^*\rightarrow E$ a surjective group homomorphism and $K = \langle ker(g) \rangle \subset F$ the subfield of F generated by the kernel of g. Then for a permutation $\rho :F\rightarrow F$ of F there exists a permutation $\kappa :E\rightarrow E$ of E such that

$$\begin{aligned} g\big (\rho (x) - \rho (y)\big ) = \kappa \big ( g(x-y) \big ) \quad \forall x\ne y\in F \end{aligned}$$

if and only if there exists a K-semilinear F-automorphism $f:F\rightarrow F$ and element $b\in F$, such that

$$\begin{aligned} \rho (x) = f(x) + b \quad \forall x\in F. \end{aligned}$$

We will apply this theorem with $F=\mathbb {\uppercase {F}}_{q^{t-1}}, E=\mathbb {\uppercase {F}}_q^*$, $g(x)=N(x)$ and hence K being the subfield of $\mathbb {\uppercase {F}}_{q^{t-1}}$ generated by $N^{-1}(1)$. We claim that $K=\mathbb {\uppercase {F}}_{q^{t-1}}$. Indeed, any proper subfield of $\mathbb {\uppercase {F}}_{q^{t-1}}=\mathbb {F}_{p^{k(t-1)}}$ has size at most $p^{\frac{k(t-1)}{2}}$. On the other hand, for $t>2$, we have

$$\begin{aligned} \left| N^{-1}(1)\right| = \frac{q^{t-1}-1}{q-1} = \sum \limits _{i=0}^{t-2} q^i > q^{t-2} = p^{k(t-2)} \ge p^{\frac{k(t-1)}{2}}, \end{aligned}$$

so $N^{-1}(1)$ would not fit into any proper subfield of $\mathbb {\uppercase {F}}_{q^{t-1}}$. Consequently we have $K=\mathbb {\uppercase {F}}_{q^{t-1}}$.

Recall the permutations $\varPsi :\mathbb {\uppercase {F}}_{q^{t-1}}\rightarrow \mathbb {\uppercase {F}}_{q^{t-1}}$ and $\psi : \mathbb {\uppercase {F}}_q^*\rightarrow \mathbb {\uppercase {F}}_q^*$ guaranteed by Lemma 2. We observe that choosing $\rho = \varPsi$ in Theorem 2, the function $\kappa : \mathbb {\uppercase {F}}_q^*\rightarrow \mathbb {\uppercase {F}}_q^*$, defined by $\kappa (x) = \psi (x) \psi (1)$, is a permutation of $\mathbb {\uppercase {F}}_q^*$, which satisfies the condition of the theorem. Indeed, given any $X\ne Y\in \mathbb {\uppercase {F}}_{q^{t-1}}$, the vertex $(X,N(X-Y))$ is adjacent to $(-Y,1)$, and hence the vertices

$$\begin{aligned} \varPhi \Big (\big (X,N(X-Y)\big )\Big )=\Big (\varPsi (X),\psi \big (N(X-Y)\big )\Big ) \end{aligned}$$

and

$$\begin{aligned} \varPhi \big ((-Y,1)\big )=\big (\varPsi (-Y),\psi (1)\big )=\big (-\varPsi (Y),\psi (1)\big ) \end{aligned}$$

must also be adjacent. Therefore we have

$$\begin{aligned} g(\rho (X)-\rho (Y)) = N\big (\varPsi (X)-\varPsi (Y)\big ) = \psi \big ((N(X-Y)\big ) \psi (1) = \kappa (g(X-Y)). \end{aligned}$$

(2)

By Theorem 2 there exist an $\mathbb {\uppercase {F}}_{q^{t-1}}$-semilinear $\mathbb {\uppercase {F}}_{q^{t-1}}$-automorphism $f:\mathbb {\uppercase {F}}_{q^{t-1}}\rightarrow \mathbb {\uppercase {F}}_{q^{t-1}}$ and element $A\in \mathbb {\uppercase {F}}_{q^{t-1}}$ such that $\forall X\in \mathbb {\uppercase {F}}_{q^{t-1}}$

$$\begin{aligned} \varPsi (X) = f(X) + A. \end{aligned}$$

By Lemma 3 we have $f(X)=C'\cdot h(X)$ for some $C'\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$ and $h\in {{\,\mathrm{Aut}\,}}(\mathbb {\uppercase {F}}_{q^{t-1}})$. Any automorphism of $\mathbb {\uppercase {F}}_{q^{t-1}}$ has the form $h(X)=X^{p^i}$ for some $0\le i < k(t-1)$, and hence we have $\varPsi (X) = C' X^{p^i} + A$. However, as $\varPsi (-1)=-\varPsi (1)$, we must have $-C'+A=-(C'+A)$, implying $2A=0$. For q odd this is possible only if $A=0$, while for even q this does not represent a restriction.

In order to show that $C'$ is a square, we evaluate Equation (2) for $Y=0$ to get

$$\begin{aligned} N\left( C' X^{p^i} - C' 0^{p^i}\right) = \psi \big (N(X-0)\big ) \psi (1)\ \Rightarrow \ \psi (N(X)) = N\left( C'\right) \psi (1)^{-1} N(X)^{p^i}. \end{aligned}$$

Substituting an $X \in N^{-1}(1)$ we also obtain $\psi (1)^2=N(C')$. $N(C')$ is a square if and only if $C'$ is a square, hence there exists $C\in \mathbb {\uppercase {F}}_{q^{t-1}}$ such that $C' = C^2$ and $\psi (1)=\pm N(C)$.

With these choices of parameters for every $(X,x)\in \mathbb {\uppercase {F}}_{q^{t-1}}\times \mathbb {\uppercase {F}}_q^*$ we have

$$\begin{aligned} \varPhi \big ((X,x)\big ) = \left( C^2 X^{p^i}, \pm N(C) x^{p^i} \right) \end{aligned}$$

if q is odd and

$$\begin{aligned} \varPhi \big ((X,x)\big ) = \left( C^2 X^{p^i}+A, N(C) x^{p^i} \right) \end{aligned}$$

if q is even, as desired.

Now let us move on to the case $t=2$. Then $t-1=1$ and we simply have $N(X)=X$ for every $X\in \mathbb {\uppercase {F}}_q$, meaning that two vertices $(X,x),(Y,y)\in \mathbb {\uppercase {F}}_q\times \mathbb {\uppercase {F}}_q^*$ are adjacent if and only if $X+Y=xy$.

Let us define the normalized maps $\widetilde{\varPsi }:\mathbb {\uppercase {F}}_q\rightarrow \mathbb {\uppercase {F}}_q$, $\widetilde{\psi } : \mathbb {\uppercase {F}}_q^*\rightarrow \mathbb {\uppercase {F}}_q^*$, and $\widetilde{\varPhi }:V\rightarrow V$ by

$$\begin{aligned} \widetilde{\varPhi }\left( (X,x)\right) := \left( \widetilde{\varPsi }(X), \widetilde{\psi } (x)\right) := \left( \frac{1}{\psi (1)^2}\left( \varPsi (X)-\varPsi (0)\right) , \frac{1}{\psi (1)}\psi (x) \right) , \end{aligned}$$

for $(X,x)\in \mathbb {\uppercase {F}}_q\times \mathbb {\uppercase {F}}_q^*$. The map $\widetilde{\varPhi }$ is an automorphism of ${\rm NG}(q,2)$, since $\varPhi$ is an automorphism and $2\varPsi (0)=0$. Furthermore $\widetilde{\varPhi }\big ((0,1)\big )=\big (\widetilde{\varPsi }(0),\widetilde{\psi }(1)\big )=(0,1)$.

As, for every $X\in \mathbb {\uppercase {F}}_q^*$, the vertices (X, X) and (0, 1) are adjacent, so must be their images under $\widetilde{\varPhi }$, implying $\widetilde{\varPsi }(X)=\widetilde{\varPsi }(X)+\widetilde{\varPsi }(0)=\widetilde{\psi }(X)\widetilde{\psi }(1)=\widetilde{\psi }(X)$ for every $X\in \mathbb {\uppercase {F}}_q^*$.

Next we show that $\widetilde{\varPsi }$, is a field automorphism of $\mathbb {\uppercase {F}}_q$, which implies that for some $0\le i < k$, we have $\widetilde{\varPsi }(X)=\widetilde{\psi }(X)=X^{p^i}$ for every $X\in \mathbb {\uppercase {F}}_q$, and consequently

$$\begin{aligned} \varPhi \big ((X,x)\big )=\big (\varPsi (X),\psi (x)\big )= \Big (\psi (1)^2 X^{p^i}+\varPsi (0),\psi (1)x^{p^i}\Big ). \end{aligned}$$

This is exactly the required form with $C=\psi (1)$ and $A=\varPsi (0)$, since $N(\psi (1))=\psi (1)$ and $A=\varPsi (0)=0$ when q is odd.

To check the additivity of $\widetilde{\varPsi }$, consider first $X, Y\in \mathbb {\uppercase {F}}_q$, $X\ne -Y$. The vertices $(X,X+Y)$ and (Y, 1) are adjacent, and hence so are their $\widetilde{\varPhi }$-images, implying $\widetilde{\varPsi }(X)+\widetilde{\varPsi }(Y)=\widetilde{\psi }(X+Y)\widetilde{\psi }(1)$. By the above this is equal to $\widetilde{\varPsi }(X+Y)$. For $X=- Y$ additivity also holds since $\varPsi (-X)=-\varPsi (X)$ for every $X\in \mathbb {\uppercase {F}}_q$.

To check the multiplicativity of $\widetilde{\varPsi }$, first let X and Y be arbitrary elements of $\mathbb {\uppercase {F}}_q^*$. Considering the $\widetilde{\varPhi }$-images of the adjacent vertices (XY, X) and (0, Y), by the above we obtain $\widetilde{\varPsi }(XY)=\widetilde{\varPsi }(XY)+\widetilde{\varPsi }(0)=\widetilde{\psi }(X)\widetilde{\psi }(Y)=\widetilde{\varPsi }(X)\widetilde{\varPsi }(Y)$. When $Y=0$ we have $\widetilde{\varPsi }(X\cdot 0)=\widetilde{\varPsi }(0)=0=\widetilde{\varPsi }(X)\cdot 0=\widetilde{\varPsi }(X)\widetilde{\varPsi }(0)$ for every $X\in \mathbb {\uppercase {F}}_q$.

Now we turn our attention to the group structure of ${{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$. This part of the argument is fairly standard, we include it for the convenience of readers less experienced in calculations with groups. We define the following subgroups of ${{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$, they correspond to the types of maps described before Lemma 1.

$$\begin{aligned} {{\,\mathrm{Aut}\,}}_F&= \left\{ \pi _i: (X,x) \mapsto (X^{p^i},x^{p^i}) \mid 0\le i < k(t-1) \right\} \simeq Z_{k(t-1)},\\ {{\,\mathrm{Aut}\,}}_M&= \left\{ \sigma _C: (X,x) \mapsto (C^2 X, N(C) x) \mid C\in \mathbb {\uppercase {F}}_{q^{t-1}}^* \right\} \\&\simeq \left\{ \begin{array}{cl} Z_{q^{t-1}-1}&{} \text { if } q \text { is even or both } q \text { and } t-1 \text { are odd}\\ Z_{\frac{q^{t-1}-1}{2}} &{} \text { if } q \text { is odd and } t-1 \text { is even.} \end{array}\right. \end{aligned}$$

In addition, for q odd we also consider the subgroup

$$\begin{aligned} {{\,\mathrm{Aut}\,}}_S = \left\{ \omega _\varepsilon : (X,x) \mapsto (X,\varepsilon x) \mid \varepsilon \in \left\{ -1,+1\right\} \right\} \simeq Z_{2}, \end{aligned}$$

and for q even the subgroup

$$\begin{aligned} {{\,\mathrm{Aut}\,}}_L = \left\{ \mu _A: (X,x) \mapsto (X+A, x) \mid A\in \mathbb {\uppercase {F}}_{q^{t-1}}\right\} \simeq \left( Z_2\right) ^{k(t-1)}. \end{aligned}$$

Now take some $\varPhi \in {{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$. When q is odd then, according to the first part of the theorem there exists $C\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$, $0\le i < k(t-1)$ and $\varepsilon \in \left\{ -1,+1\right\}$ such that $\varPhi \big ((X,x)\big )=\big (C^2X^{p^i},\varepsilon N(C)x^{p^i}\big )$ and hence $\varPhi =\omega _\varepsilon \circ \sigma _C \circ \pi _i$ (for the composition of some maps $\alpha$ and $\beta$ we fix the notation $\alpha \circ \beta$ and their order of action is understood as $(\alpha \circ \beta )(x)=\alpha (\beta (x))$). Similarly, when q is even, then there exists $C\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$, $0\le i < k(t-1)$ and $A\in \mathbb {\uppercase {F}}_{q^{t-1}}$ such that $\varPhi \big ((X,x)\big )=\big (C^2X^{p^i}+A,N(C)x^{p^i}\big )$ and hence $\varPhi =\mu _A\circ \sigma _C \circ \pi _i$. This shows that these subgroups generate ${{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$, i.e.

$$\begin{aligned} {{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))=\left\{ \begin{array}{ll} {{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M\circ {{\,\mathrm{Aut}\,}}_F &{} \text { if } q \text { is odd,}\\ {{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M\circ {{\,\mathrm{Aut}\,}}_F &{} \text { if } q \text { is even.} \end{array} \right. \end{aligned}$$

Before proving the particular group structure we prove a simple lemma that will be used several times in what follows.

Lemma 4

Let G be a group and N, H subgroups such that $N^h\subseteq N$ for every $h\in H$. Then $N\cdot H$ is a subgroup of G and $N\triangleleft N\cdot H$. If $N\cap H=\left\{ 1_G\right\}$, then $N\cdot H=N\rtimes H$.

Proof

The conditions $N^h\subseteq N$ imply that N is a normal subgroup in the group $\langle N,H\rangle$ generated by N and H, and hence $\langle N,H\rangle = N\cdot H$. Moreover, the intersection condition implies that $N\cdot H =N\rtimes H$ (see the definition on page 167 of [42]). $\square$

Now suppose first that q is odd, and consider the term ${{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M$. If $t-1$ is also odd, then $\omega _{-1}=\sigma _{-1}$, hence ${{\,\mathrm{Aut}\,}}_S\subseteq {{\,\mathrm{Aut}\,}}_M$ and so ${{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M={{\,\mathrm{Aut}\,}}_M$. If $t-1$ is even, then ${{\,\mathrm{Aut}\,}}_S\cap {{\,\mathrm{Aut}\,}}_M=\{id\}$, elements from the two parts clearly commute and ${{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M$ is also a subgroup of ${{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$, hence ${{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M={{\,\mathrm{Aut}\,}}_S\times {{\,\mathrm{Aut}\,}}_M$.

To add ${{\,\mathrm{Aut}\,}}_F$ we apply Lemma 4 with $G={{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$, $N={{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M$ and $H={{\,\mathrm{Aut}\,}}_F$. For this we first need to check that $\displaystyle (\omega _{\varepsilon }\circ \sigma _C)^{\pi _i}\in {{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M$ for every $\varepsilon \in \{-1,+1\}$, $C\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$ and $0\le i < k(t-1)$:

$$\begin{aligned} (\omega _\varepsilon \circ \sigma _C)^{\pi _i}=\pi _i^{-1}\circ (\omega _\varepsilon \circ \sigma _C)\circ \pi _i=\pi _{k(t-1)-i}\circ \omega _\varepsilon \circ \sigma _C\circ \pi _i=\omega _{\varepsilon '}\circ \sigma _{C'}\in {{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M, \end{aligned}$$

where $\varepsilon '=\varepsilon ^{p^{k(t-1)-i}}$ and $C'=C^{p^{k(t-1)-i}}$. We clearly also have $({{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M)\cap {{\,\mathrm{Aut}\,}}_F=\{id\}$, so Lemma 4 implies that ${{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M$ is a normal subgroup of ${{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M\circ {{\,\mathrm{Aut}\,}}_F={{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$ and

$$\begin{aligned} {{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))={{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M\circ {{\,\mathrm{Aut}\,}}_F=({{\,\mathrm{Aut}\,}}_S\circ {{\,\mathrm{Aut}\,}}_M)\rtimes {{\,\mathrm{Aut}\,}}_F\\ =\left\{ \begin{array}{ll} {{\,\mathrm{Aut}\,}}_M\rtimes {{\,\mathrm{Aut}\,}}_F= Z_{q^{t-1}-1}\rtimes Z_{k(t-1)} &{} \text {if } t-1 \text { is odd}\\ \left( {{\,\mathrm{Aut}\,}}_S\times {{\,\mathrm{Aut}\,}}_M\right) \rtimes {{\,\mathrm{Aut}\,}}_F=\left( Z_2\times Z_{\frac{q^{t-1}-1}{2}}\right) \rtimes Z_{k(t-1)} &{} \text {if } t-1 \text { is even.} \end{array} \right. \end{aligned}$$

Now suppose q is even and consider first ${{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M$. We again apply Lemma 4, now with $G={{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$, $N={{\,\mathrm{Aut}\,}}_L$ and $H={{\,\mathrm{Aut}\,}}_M$. First we check that $\mu _A^{\sigma _C}\in {{\,\mathrm{Aut}\,}}_L$ for every $A\in \mathbb {\uppercase {F}}_{q^{t-1}}$ and $C\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$:

$$\begin{aligned} \mu _A^{\sigma _C}=\sigma _C^{-1}\circ \mu _A \circ \sigma _C=\sigma _{C^{-1}}\circ \mu _A \circ \sigma _C=\mu _{(C^{-1})^2A}\in {{\,\mathrm{Aut}\,}}_L. \end{aligned}$$

We clearly also have ${{\,\mathrm{Aut}\,}}_L\cap {{\,\mathrm{Aut}\,}}_M=\{id\}$, so by Lemma 4${{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M$ is a subgroup of ${{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$, ${{\,\mathrm{Aut}\,}}_L$ is normal subgroup of it and we have

$$\begin{aligned} {{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M={{\,\mathrm{Aut}\,}}_L\rtimes {{\,\mathrm{Aut}\,}}_M. \end{aligned}$$

To describe the full group ${{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$, we apply Lemma 4 one last time, now with $G={{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$, $N={{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M={{\,\mathrm{Aut}\,}}_L\rtimes {{\,\mathrm{Aut}\,}}_M$ and $H={{\,\mathrm{Aut}\,}}_F$. We start by checking that $(\mu _A\circ \sigma _C)^{\pi _i}\in {{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M$ for every $A\in \mathbb {\uppercase {F}}_{q^{t-1}}$, $C\in \mathbb {\uppercase {F}}_{q^{t-1}}^*$ and $0\le i < k(t-1)$:

$$\begin{aligned} (\mu _A\circ \sigma _C)^{\pi _i}=\pi _i^{-1}\circ \mu _A\circ \sigma _C\circ \pi _i=\pi _{k(t-1)-i}\circ \mu _A\circ \sigma _C\circ \pi _i=\mu _{A'}\circ \omega _{C'}\in {{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M, \end{aligned}$$

where $A'=A^{p^{k(t-1)-i}}$ and $C'=C^{p^{k(t-1)-i}}$. We clearly also have $({{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M)\cap {{\,\mathrm{Aut}\,}}_F=\{id\}$, so using Lemma 4 we infer that ${{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M$ is a normal subgroup of ${{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M\circ {{\,\mathrm{Aut}\,}}_F={{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))$ and

$$\begin{aligned} {{\,\mathrm{Aut}\,}}({\text{NG}}(q,t))&={{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M\circ {{\,\mathrm{Aut}\,}}_F=({{\,\mathrm{Aut}\,}}_L\circ {{\,\mathrm{Aut}\,}}_M)\rtimes {{\,\mathrm{Aut}\,}}_F\\&=\left( {{\,\mathrm{Aut}\,}}_L\rtimes {{\,\mathrm{Aut}\,}}_M\right) \rtimes {{\,\mathrm{Aut}\,}}_F=\left( (Z_2)^{k(t-1)}\rtimes Z_{q^{t-1}-1}\right) \rtimes Z_{k(t-1)}. \end{aligned}$$

Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Alon, N., Krivelevich, M., Sudakov, B.: MaxCut in $H$-Free graphs. Comb. Probab. Comput. 14, 629–647 (2005)MathSciNetMATHCrossRef

Alon, N., Krivelevich, M., Sudakov, B.: Turán numbers of bipartite graphs and related Ramsey-type questions. Comb. Probab. Comput. 12, 477–494 (2003)MATHCrossRef

Alon, N., Moran, S., Yehudayoff, A.: Sign Rank, VC dimension and spectral gaps, In: Feldman, V., Rakhlin, A., Shamir, O. (eds.) Proceedings of COLT’16, Proceedings of Machine Learning Research, vol. 49, pp. 47–80. (2016). (Also: Mathematicheskii Sbornik, 208:4–41, 2017.)

Alon, N., Rödl, V.: Sharp bounds for some multicolor Ramsey numbers. Combinatorica 25(2), 125–141 (2005)MathSciNetMATHCrossRef

Alon, N., Shikhelman, C.: Many T-copies in H-free graphs. J. Comb. Theory Ser. B 121, 146–172 (2016)MathSciNetMATHCrossRef

Alon, N., Rónyai, L., Szabó, T.: Norm-graphs: variations and applications. J. Comb. Theory Ser. B 76, 280–290 (1999)MathSciNetMATHCrossRef

Babai, L., Gál, A., Kollár, J., Rónyai, L., Szabó, T., Widgerson, A.: Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs, In: Miller, G.L. (eds.), Proceedings of STOC’96, ACM, pp. 603–61 (1996)

Babai, L., Gál, A., Widgerson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica 19(3), 301–319 (1999)MathSciNetMATHCrossRef

Ball, S., Pepe, V.: Asymptotic Improvements to the Lower Bound of Certain Bipartite Turán Numbers. Comb. Probab. Comput. 21, 323–329 (2012)MATHCrossRef

10.

Ball, S., Pepe, V.: Forbidden subgraphs in the norm graph. Discret. Math. 339(4), 1206–1211 (2016)MathSciNetMATHCrossRef

11.

Balogh, J., Samotij, W.: The number of $K_{s, t}$-free graphs. J. Lond. Math. Soc. 83(2), 368–388 (2011)MathSciNetMATHCrossRef

12.

Bayer, T., Mészáros, T., Rónyai, L., Szabó, T.: Exploring projective norm graphs, (2019) arXiv:1908.05190

13.

Bayer, T., Mészáros, T., Rónyai, L., Szabó, T.: Exploring projective norm graphs (extended abstract). Acta Math. Univ. Comen. 88(3), 437–441 (2019)

14.

Brown, W.G.: On graphs that do not contain a Thomsen graph. Can. Math. Bull. 9, 281–285 (1966)MathSciNetMATHCrossRef

15.

Dvir, Z., Kollár, J., Lovett, S.: Variety evasive sets. Comput. Complex. 23(4), 509–529 (2014)MathSciNetMATHCrossRef

16.

Erdős, P.: On sequences of integers no one of which divides the product of two others and related problems, Mitt. Forsch. Institut. Mat. und Mech. Tomsk 2, 74–82 (1938)

17.

Erdős, P., Simonovits, M.: A limit theorem in graph theory. Stud. Sci. Math. Hung. 1, 215–235 (1966)MathSciNetMATH

18.

Erdős, P., Stone, A.H.: On the structure of linear graphs. Bull. Am. Math. Soc. 52, 1087–1091 (1946)MathSciNetMATHCrossRef

19.

Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. 19(6), 1785–1810 (2017)MathSciNetMATHCrossRef

20.

Grosu, C.: A note on projective norm graphs. Int. J. Number Theory 14(1), 55–62 (2018)MathSciNetMATHCrossRef

21.

Kollár, J., Rónyai, L., Szabó, T.: Norm-graphs and bipartite Turán numbers. Combinatorica 16, 399–406 (1996)MathSciNetMATHCrossRef

22.

Kostochka, A., Pudlák, P., Rödl, V.: Some constructive bounds on Ramsey numbers. J. Comb. Theory Ser. B 100, 439–445 (2010)MathSciNetMATHCrossRef

23.

Kostochka, A., Mubayi, D., Verstraëte, J.: Turán problems and shadows III: expansions of graphs. SIAM J. Discret. Math. 29(2), 868–876 (2015)MATHCrossRef

24.

Kővári, T., Sós, V.T., Turán, P.: On a problem of K. Zarankiewicz, Colloquium Mathematicae 3(1), 55–57 (1954)MathSciNetMATH

25.

Lazebnik, F., Mubayi, D.: New lower bounds for Ramsey numbers of graphs and hypergraphs. Adv. Appl. Math. 28(3), 544–559 (2002)MathSciNetMATHCrossRef

26.

Lenstra, H.W.: Automorphisms of finite fields. J. Number Theory 34(1), 33–40 (1990)MathSciNetMATHCrossRef

27.

Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications, Cambridge University Press (1986)

28.

Ma, J.: On edges not in monochromatic copies of a fixed bipartite graph. J. Comb. Theory Ser. B 123, 240–248 (2017)MathSciNetMATHCrossRef

29.

Mantel, W.: Problem 28. Winkundige Opgaven 10, 60–61 (1907)

30.

Mészáros, T., Rónyai, L., Szabó, T.: Singer difference sets and the projective norm graph, (2019) arXiv:1908.05591

31.

Monte Carmelo, E.L., Sanches, J.: Multicolored set multipartite Ramsey numbers. Discret. Math. 339, 2775–2784 (2016)MathSciNetMATHCrossRef

32.

Mubayi, D.: Some exact results and new asymptotics for hypergraph Turán numbers. Comb. Probab. Comput. 11(3), 299–309 (2002)MATHCrossRef

33.

Mubayi, D.: Coloring with three-colored subgraphs. J. Graph Theory 42(3), 193–198 (2003)MathSciNetMATHCrossRef

34.

Mubayi, D., Williford, J.: On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph. J. Graph Theory 56(2), 113–127 (2007)MathSciNetMATHCrossRef

35.

Nica, B.: Unimodular graphs and Eisenstein sums. J. Algebraic Comb. 45(2), 423–454 (2017)MathSciNetMATHCrossRef

36.

Nikiforov, V.: A contribution to the Zarankiewicz problem. Linear Algebra Appl. 432, 1405–1411 (2010)MathSciNetMATHCrossRef

37.

Nikiforov, V.: Some new results in extremal graph theory. In: Chapman, R. (eds.) Surveys in Combinatorics 2011, pp. 141–182. LMS Lecture Note Series 392, Cambridge University Press (2011)

38.

Pach, J., Spencer, J., Tóth, G.: New bounds on crossing numbers. Discret. Comput. Geom. 24(4), 623–644 (2000)MathSciNetMATHCrossRef

39.

Palmer, C., Tait, M., Timmons, C., Zs, A.: Wagner, Turán numbers for Berge-hypergraphs and related extremal problems. Discret. Math. 342(6), 1553–1563 (2019)MATHCrossRef

40.

Peng, X., Timmons, C.: Infinite Turán Problems for Bipartite Graphs. SIAM J. Discret. Math. 28(2), 702–710 (2014)MATHCrossRef

41.

Perarnau, G., Reed, B.: Existence of spanning $F$-free subgraphs with large minimum degree. Comb. Probab. Comput. 26(3), 448–467 (2017)MathSciNetMATHCrossRef

42.

Rotman, J. J.: An introduction to the theory of groups (4th ed.), Graduate Texts in Mathematics 148, Springer-Verlag (1995)

43.

Rué, J., Serra, O., Vena, L.: Counting configuration-free sets in groups. Eur. J. Comb. 66, 28–307 (2017)MathSciNetMATHCrossRef

44.

Sudakov, B., Verstraëte, J.: Cycle lengths in sparse graphs. Combinatorica 28(3), 357–372 (2008)MathSciNetMATHCrossRef

45.

Sudakov, B., Vondrák, J.: A randomized embedding algorithm for trees. Combinatorica 30(4), 445–470 (2010)MathSciNetMATHCrossRef

46.

Turán, P.: On an extremal problem in graph theory. Matematikai és Fizikai Lapok 48, 436–452 (1941)MathSciNet

47.

Verstraëte, J.: Product representations of polynomials. Eur. J. Comb. 27, 1350–1361 (2006)MathSciNetMATHCrossRef

48.

Vinh, L.A.: The sovability of norm, bilinear and quadratic equations over finite fields via spectra of graphs. Forum Math. 26(1), 141–175 (2014)MathSciNetMATHCrossRef

49.

Wang, Y., Li, Y.: Bounds for Bipartite Rainbow Ramsey Numbers. Graphs Comb. 33(4), 1065–1079 (2017)MathSciNetMATHCrossRef

50.

Wang, X., Lin, Q.: Multicolor bipartite Ramsey numbers of $K_{t, s}$ and large $K_{n, n}$. Discret. Appl. Math. 213, 238–242 (2016)MATHCrossRef

Title: The automorphism group of projective norm graphs
Authors: Tomas Bayer
Tamás Mészáros
Lajos Rónyai
Tibor Szabó
Publication date: 10-01-2023
Publisher: Springer Berlin Heidelberg
Published in: Applicable Algebra in Engineering, Communication and Computing
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-022-00590-3

Springer Professional

The automorphism group of projective norm graphs

Abstract

Publisher's Note

1 Introduction

2 The automorphism group

3 Preliminaries

3.1 Common neighbourhood of pairs of vertices

4 The proof

Publisher's Note

Premium Partner