ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 67-79
https://doi.org/10.26493/1855-3974.1546.c5e
(Also available at http://amc-journal.eu)
On chromatic indices of finite affine spaces*
Gabriela Araujo-Pardo
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad Universitaria, 04510, Mexico City, Mexico
Gyorgy Kiss
Department of Geometry and MTA-ELTE Geometric and Algebraic Combinatorics Research Group, Eotvos Lomnd University, H-1117 Budapest, Pázmany s. 1/c, Hungary and FAMNIT, University of Primorska, 6000 Koper, Glagoljaska 8, Slovenia
Christian Rubio-Montiel
Department of Algebra, Comenius University, Mlynska dolina, 84248, Bratislava, Slovakia and Division de Matematicas e Ingeniería, FES AcatMn, Universidad Nacional Autónoma de Mexico, 53150 Naucalpan, Mexico
Adrian Vazquez-Avila
Subdireccion de Ingeniería y Posgrado, Universidad Aeronautica en Queretaro, Parque Aeroespacial Queretaro, 76270, Queretaro, Mexico
Received 6 December 2017, accepted 14 April 2018, published online 17 September 2018
A line-coloring of the finite affine space AG(n, q) is proper if any two lines from the same color class have no point in common, and it is complete if for any two different colors i and j there exist two intersecting lines, one is colored by i and the other is colored by j. The pseudoachromatic index of AG(n, q), denoted by ^'(AG(n, q)), is the maximum number of colors in any complete line-coloring of AG(n, q). When the coloring is also proper, the maximum number of colors is called the achromatic index of AG(n, q). We prove that ^'(AG(n,q)) - qi.Sn-1 for even n, and that qL5("-1) < ^'(AG(n,q)) < q1.5"-1 for odd n. Moreover, we prove that the achromatic index of AG(n, q) is q15"-1 for even n, and we provide the exact values of both indices in the planar case.
*The authors gratefully acknowledge funding from the following sources: Gabriela Araujo-Pardo was partially supported by CONACyT-Mexico under Projects 178395, 166306, and by PAPIIT-Mexico under Projects IN104915 and IN107218. Gyorgy Kiss was partially supported by the bilateral Slovenian-Hungarian Joint Research Project, grant no. NN 114614 (in Hungary) and N1-0032 (in Slovenia), and by the Hungarian National Foundation for Scientific Research, grant no. K 124950. Christian Rubio-Montiel was partially supported by a CONACyT-Mexico Postdoctoral fellowship, and by the National scholarship programme of the Slovak Republic. Adrian Vazquez-A'vila was partially supported by SNI of CONACyT-Mexico.
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
Abstract
68
Ars Math. Contemp. 16 (2019) 245-255
Keywords: Achromatic index, complete coloring, finite affine space, pseudoachromatic index. Math. Subj. Class.: 05B25, 51E15, 05C15
1 Introduction
This paper is motivated by the well-known combinatorial conjecture about colorings of finite linear spaces stated by Erdos, Faber and Lovasz in 1972. As a starting point, we briefly recall some definitions and state the conjecture. Let S be a finite linear space. A line-coloring of S with k colors is a surjective function ? from the lines of S to the set of colors [k] = {1,..., k}. For short, a line-coloring with k colors is called k-coloring. If ?: S ^ [k] is a k-coloring and i e [k] then the subset of lines ?-1(i) is called the i-th color class of A k-coloring of S is proper if any two lines from the same color class have no point in common. The chromatic index x'(S) of S is the smallest k for which there exists a proper k-coloring of S. The Erdos-Faber-Lovasz conjecture (1972) states that if a finite linear space S contains v points then x'(S) < v, see [12, 13].
Several papers have investigated the conjecture for particular classes of linear spaces. For instance, if each line of S has the same number k of points then S is called a block design or a (v, n)-design. The conjecture is still open for designs even for k = 3, however, it was proved for finite projective spaces by Beutelspacher, Jungnickel and Vanstone [8]. It is not hard to see that the conjecture is also true for the n-dimensional affine space AG(n, q) of order q defined over the Galois field GF(q). Indeed,
qn - 1
x'(AG(n,q)) =	.
q -1
For some related results, see for instance [6, 7].
A natural question is to determine similar, but slightly different color parameters in finite linear spaces. A k-coloring of S is complete if for each pair of different colors i and j there exist two intersecting lines of S, such that one of them belongs to the i-th and the other one to the j-th color class. Observe that any proper coloring of S with x'(S) colors is a complete coloring. The pseudoachromatic index ^'(S) of S is the largest k such that there exists a complete k-coloring (not necessarily proper) of S. When the k-coloring is required to be complete and proper, the parameter is called the achromatic index and it is denoted by a'(S). Therefore, we have that
x'(S) < a'(S) < V'(S).
Several authors studied the pseudoachromatic index, see [2, 3, 4, 5, 9, 14, 15, 17]. Moreover, in [1, 10, 18] the achromatic indices of some block designs were also estimated.
In this paper we study the pseudoachromatic and achromatic indices of finite affine spaces. In the proofs we will often use the notion of the projective closure of AG(n, q). This is the finite projective space PG(n, q) = AG(n, q) U where the points of correspond to the parallel classes of lines in AG(n, q). The space is isomorphic to PG(n - 1, q), and it is called the hyperplane at infinity. We assume that the reader is
E-mail addresses: garaujo@matem.unam.mx (Gabriela Araujo-Pardo), kissgy@cs.elte.hu (Gyorgy Kiss), christian.rubio@apolo.acatlan.unam.mx (Christian Rubio-Montiel), adrian.vazquez@unaq.edu.mx (Adrian Vazquez-Avila)
G. Araujo-Pardo et al.: On chromatic indices of finite affine spaces
69
familiar with the most important properties of affine and projective geometries. For the detailed description of these spaces we refer to [16].
The main results in the paper are proved in Sections 2 and 3. They are stated in Theorems 1.1, 1.2 and 1.3. In these theorems v = qn always denotes the number of points of the finite affine space AG(n, q).
Theorem 1.1. For all n:
V>'(AG(n,q)) < v/Vy(V . 1) - Q(qVV/2). q — 1
Theorem 1.2. If n is even:
1	VV(v — 1)
2	^ q — 1
i VV(v — 1)
If n is odd:
sjq q — 1 Theorem 1.3. If n is even:
1 yv(v — 1)
3 ^ q — 1
—	Q(Vv/2) < V'(AG(n,q)).
—	©(^y/v/q5) < ^'(AG(n, q)).
+ Q(v/q) < a'(AG(n, q)).
Note that when n is even Theorems 1.1 and 1.2 show that ^'(AG(n, q)) grows asymptotically as ©(v1-5/q), while Theorems 1.2 and 1.3 show that a'(AG(n, q)) grows asymptotically as ©(w15/q). Let us remark that no similar estimates regarding the asymptotic behavior of these indices have appeared so far in the literature.
Finally, in Section 4 we determine the exact values of pseudoachromatic and achromatic indices of arbitrary (not necessarily Desarguesian) finite affine planes and we improve the previous lower bounds in dimension 3.
2 Upper bounds
In this section, upper bounds for the pseudoachromatic index of AG(n, q) are presented when n > 2. The following lemma is pivotal in the proof.
Lemma 2.1. Let L be a set of s lines in AG(n, q), n > 2. Then the number of lines of AG(n, q) intersecting at least one element of L is at most
2 ( q"-1 - 1 ( 1)
q s-;--(s -1)
V q -1
Proof. In AG(n, q) there are q ^- l) = q2 (q g--1) lines intersecting any fixed
line. The number of lines intersecting two lines, say and l2, is at least q2, because if £1 n l2 = 0 then the q2 lines joining a point of and a point of l2 intersect both and ¿2, while, if l\_ n i2 = {P} then the other qn—r - 2 > q2 lines through P intersect both ^
and . Consequently, the number of lines intersecting at least one element of L is at most
"2 (^) - <• -1"2'
70
Ars Math. Contemp. 16 (2019) 245-255
Notice that the previous inequality is tight, since if L consists of s parallel lines in a plane then there are exactly q2 ^s q q_-1 - (s - 1) j lines intersecting at least one element of L.	□
Lemma 2.2. Let n > 2 bean integer. Then the colorings of the finite affine space AG(n, q) satisfy the inequality
*'(AG(n, q)) < ^4q"(q"- 1)(q" -^q211)2(q-1)2+. (2.1)
Proof. Consider a complete coloring which contains ^'(AG(n, q)) color classes. Then the number of lines in the smallest color class is at most
qn-1(qn - 1)
s —
(q - 1)V"(AG(n, q))"
Each of the other ^'(AG(n, q)) - 1 color classes must contain at least one line which intersects a line from the smallest color class. Hence, by Lemma 2.1, we obtain
V>'(AG(n, q)) - 1 < q2 f sq" 1 - 1 - (s - .
q-1
Multiplying it by ^'(AG(n, q)), we get a quadratic inequality on ^'(AG(n, q)), whence the assertion follows.	□
We are in a position to prove our first main theorem.
Proof of Theorem 1.1. For n > 2 a straightforward computation shows
4qn(qn - 1)(qn - q2) + (q2 + 1)2(q - 1)2
= (2q2 (qn - 1) - q2 (q2 - 1))2 - qn(q2 - 1)2 + (q2 + 1)2(q - 1)2
< (2q2 (qn - 1) - q2 (q2 - 1))
2
because n > 2 implies that qn(q2 - 1)2 > (q2 + 1)2(q - 1)2. This together with Inequality (2.1) give
*'<**,,)) < ,2 (^ 1 - q2 (i+i) + 11
q -1 J V 2 ) 2 '
which proves the theorem for n > 2. For n = 2 the statement is clear.	□
3 Lower bounds
In this section complete colorings of AG(n, q) are presented. These constructions give different bounds on ^'(AG(n, q)) depending on the parity of n. First, we prove some geometric properties of affine and projective spaces.
G. Araujo-Pardo et al.: On chromatic indices of finite affine spaces
71
Proposition 3.1. Let n > 1 be an integer, ni and n2 be subspaces in PG(n, q) = AG(n, q) U Hœ. Let d denote the dimension of n for i = 1,2. Suppose that n1 n n2 n %œ is an m-dimensional subspace and d1 + d2 = n + 1 + m. Then n1 n n2 n AG(n, q) is an (m + 1)-dimensional subspace in AG(n, q).
In particular, n1 n n2 is a single point in AG(n, q) when n1 n n2 n %œ = 0 and di + ¿2 = n.
Proof. Since n1 n n2 n %œ is an m-dimensional subspace, dim(n1 n n2) < m +1. On the other hand, the dimension formula yields
dim(n1 n n2) = dimn1 + dimnv - dim(n1, n2) > d1 + d2 - n = m + 1.
Thus n1 n n2 is an (m + 1)-dimensional subspace in PG(n, q), therefore n1 n n2 n AG(n, q) is an (m + 1)-dimensional subspace in AG(n, q) if m > 0.
If m = -1, then n1 n n2 n %œ = 0 and dim(n1 n n2) = 0. Hence n1 n n2 is a single point in AG(n, q).	□
In the following proposition we present a partition of the points of PG(2k, q) that we will call a good partition in the rest of the paper.
Proposition 3.2. Let k > 1 be an integer and Q G PG(2k, q) be an arbitrary point. The points of PG(2k, q) \ {Q} can be divided into two subsets, say A and B, and one can assign a subspace S (P) to each point P G A U B, such that the following holds true:
• P G S (P) for all points;
2k
|A| = q2 ( qo2_11 ) and, if A G A then S(A) is a k-dimensional subspace;
( 2k_-| \
•	|B| = q ( qq2_1 j and, if B G B then S(B) is a (k — l)-dimensional subspace;
•	S(A) n S(B) = 0 for all A G A and B gB.
Proof. We prove the assertion by induction on k. If k = 1 then let ¿4,..., } be the set of lines through Q. Let A and B consist of points PG(2, q) \ {4i} and \ {Q}, respectively. If A g A then let S(A) be the line AQ, if B g B then let S(B) be the point B. These sets clearly fulfill the prescribed conditions, so PG(2, q) admits a good partition.
Now, let us suppose that PG(2k, q) admits a good partition. In PG(2k + 2, q) take a 2k-dimensional subspace n which contains the point Q. Then n is isomorphic to PG(2k, q), hence it has a good partition {Q} uA' UB' with assigned subspaces S'(P). Let H0,..., Hq be the pencil of hyperplanes in PG(2k + 2, q) with carrier n. Let B = B' U (H0 \ n) and A = PG(2k + 2, q) \ (B U {Q}). Notice that A' and B' have the required cardinalities, because
q2fc+3 _ 1	q2k+3 _ 1	/q2k+2 _ 1 \
|A'| = \ — 1 — (|B| + 1) = (q + 1)q q2 1 1 — q ( q ,2 t M — 1
q — 1	q2 — 1	V q2 — 1
/q2k+2 _ i ^
2 q 1
q
lB'l = ibi + IH\ni =	q	q2 — 1
q2 - 1
q2k _ 1 \ /q2k+2 _ 1
q_M + q2k+1 = q q_1
72
Ars Math. Contemp. 16 (2019) 245-255
We assign the subspaces in the following way. If A 6 A' then let S(A) be the (k + 1)-dimensional subspace (S'(A),P} where P 6 uq=1H( is an arbitrary point, whereas, if A 6 (uq=1Hi) \ n then let S(A) be the (k + 1)-(dimensional subspace (A, S'(P)} where P 6 A' is an arbitrary point. In both cases S(A) C U?=1H( for all A 6 A. Similarly, if B 6 B' then let s(b) be the k-dimensional subspace (S'(B),P} where P 6 H0 is an arbitrary point, whereas, if B 6 H0 \ n then let S(B) be the k-dimensional subspace (B, S'(P)} where P 6 B' is an arbitrary point. Also here, in both cases, S(B) C H0 for all B 6 B. Moreover, the assigned subspaces satisfy the intersection condition because if A 6 A and B 6 B are arbitrary points then
S(A) n S(B) = (S(A) n (u?=1H()) n (S(B) n H0) = S'(A) n S'(B) n n = 0.
Hence PG(2k + 2, q) also admits a good partition, and the statement is proved. □
The next theorem proves Theorem 1.2 for even dimensional finite affine spaces. Notice that the lower bound depends on the parity of q, but its magnitude is	in both cases,
where v = qn.
Theorem 3.3. If k > 1 then the colorings of the even dimensional affine space, AG(2k, q), satisfy the inequalities
{^kfr———, if q is odd,
qkM) +1 f q is even 2(q—1) + 1 11 even.
Proof. The hyperplane at infinity in the projective closure of AG(2k, q), is isomorphic to PG(2k - 1, q), hence it has a (k - 1)-spread S = {S1, S2,..., Sqk+1}. The elements of S are pairwise disjoint (k - 1)-dimensional subspaces (see [16, Theorem 4.1]). Let {Pj, P2(,..., P(qfc — 1)/(q—1)} be the set of points of S( for i = 1, 2,...,
qk + 1. For a point P 6 let S(P) denote the unique element of S that contains P, and A(P) = {nPj1, nP,2,..., nP,qk} denote the set of the qk parallel k-dimensional subspaces of AG(2k, q) whose projective closures intersect in S(P).
We define a pairing on the set of points of which depends on the parity of q. On the one hand, if q is odd then let (Pj Pj+1) be the pairs for i = 1, 3, 5,..., qk and
_ On flip nthpr honH i
q—1 he p
i = 4,6,..., qk and j = 1,2,..., q—, and let (P/, P2), (P2+1, Pf+1), (Pj1+1, Pj3) and
(P2, Pf) be the pairs for i = 1, 2, 3 and j = 2,4,6,..., ¿"1 - 1.
Let (U, V) be any pair of points. Then, by defintion, S(U) = S(V). Let the color class Cu,v,( contain the lines joining either U and a point from nU (, or V and a point from nV,(, for i = 1,2,..., qk. Clearly, (U, V) defines qk color classes, each one consists of the parallel lines of one subspace in A(U) and the parallel lines of one subspace in A(V). Finally, if q is even, then let the color class C1 consist of all lines of AG(2k, q) whose point at infinity is P11 .
2k_1 2k_
We divided the points of into i) pairs if q is odd, and into |(q—1) pairs if q is
2k_1 ,
even. Consequently, the number of color classes is equal to 2(q—^ qk when q is odd, and it is equal to 2q(q—qk + 1 when q is even.
j = 1,2,..., q—j-. On the other hand, if q is even then %œ has an odd number of points, thus we give the pairing on the set of points \ {P-}: let (Pj, PJ+-) be the pairs for
G. Araujo-Pardo et al.: On chromatic indices of finite affine spaces
73
Now, we show that the coloring is complete. The class C obviously intersects any other class. Let CUtv,i and Cw,z,j be two color classes. Then S(U) and S(V) are distinct elements of the spread S and S(W) is also an element of S. Hence we may assume, without loss of generality, that S(U) n S(W) = 0. As
dim(S(U) U nU,i) = dim(S(W) U nWj) = k
in PG(2k, q), by Proposition 3.1, we have that nU,i n nW,j consists of a single point in AG(2k, q). Notice that the coloring is not proper, because the same argument shows that nU,i n nVi is also a single point in AG(2k, q).	□
For odd dimensional spaces we have a slightly weaker estimate. In this case, the magnitude of the lower bound is ^q ■	, where v = qn.
Theorem 3.4. If k > 1 then the colorings of the odd dimensional affine space, AG(2k + 1, q), satisfy the inequality
qfc+2 ( +1 - +1 q)).
Proof. The hyperplane at infinity in the projective closure of AG(2k+1, q), is isomorphic to PG(2k, q). Hence, by Proposition 3.2, admits a good partition = AUBU {Q} with assigned subspaces S(U). Let A = {Pi, P2,..., Pt} and B = {Ri, R2,..., R }
where t = q2 (i^) and s = q ($-r) .
For a point Pi e A let A(Pi) = {nPiji, nPi,2,..., nP.qk} denote the set of the qk parallel (k+1)-dimensional subspaces of AG(2k+1, q) whose projective closures intersect in S(Pi). Similarly, for a point Rj e B let B(Rj) = {nR. ,i, nR.,2,..., nRj ,qfc+i} denote the set of the qk+1 parallel k-dimensional subspaces of AG(2k + 1, q) whose projective closures intersect in S(Rj).
Now, we define the color classes. Let Ci be the color class that contains all lines of AG(2k + 1, q) whose point at infinity is Q. Let the color class Ci,j,m contain the lines joining either P(j-i)q+i and a point from np(._1)f+.,m, or Rj and a point from nR. ,(i-i)qk +m for j = 1,2,..., s, i = 1,2,..., q and m = 1, 2,..., qk. Counting the number of color classes of type Ci,j,m, we obtain s ■ q ■ qk = qk+2 ^^J-1) . Each color class consists of the parallel lines of one subspace in A(P(j-i)q+i) and the parallel lines of one subspace in B(Rj). Clearly, the total number of color classes is 1 + qk+2 ^ qq2 j-1 ) . The color class Ci
contains q2k lines and each of the classes of type Ci,j,m consists of qk + qk-i lines.
To prove that the coloring is complete, notice that the class Ci obviously intersects any other class. Let Ci,j,m and Ci/,j/,m' be two color classes other than Ci. Consider the projective closures of those elements of A(P(j-i)q+i) and B(Rj) whose lines are contained in Ci,j,m and in Ci',j',m', respectively. One of these subspaces is a (k + 1)-dimensional, whereas the other one is a k-dimensional subspace in PG(2k + 1, q), and they have no point in common in Thus, by Proposition 3.1, their intersection is a single point in AG(2k + 1, q).
The coloring is not proper, because the same argument shows that nP(j_1)q+.,m n nRj ,(i-i)qfc+m is also a point in AG(2k + 1, q), thus Ci,j,m contains a pair of intersecting lines.	□
74
Ars Math. Contemp. 16 (2019) 245-255
Now, we are ready to prove our second main theorem.
Proof of Theorem 1.2. If n is even then Theorem 3.3 gives the result at once. If n is odd
then v = q2fc+1, hence \Jv/q = qk. From the estimate of Theorem 3.4 we get
/ q2k _ i \	q3k+2 _ qk+2
qk+2( ^—r ) +1 = q _2 ! +1
;) q3k+1 + qk+2 _ qk + 1 _ qk
+ 1
q2 -1	q2 -1
(q + 1)(q3k+1 - qk) q3fc+1 + qk+2 - qfc+1 - qk

q2 - 1	q2 - 1
1 Vv(v - 1) q3k+1 + qk+2 - qk+1 - qk

+ 1,
v^ q - 1	q2 - 1
which proves the statement.	□
Next, recall that a lower bound for the achromatic index require a proper and complete line-coloring of AG(n, q). We consider only the even dimensional case.
Theorem 3.5. Let k > 1 and e = 0,1 or 2, such that qk + 1 = e (mod 3). Then the achromatic index of the even dimensional finite affine space AG(2k, q) satisfies the inequality
q + 1 - ' (qk + 2) + e) q--1 < a'(AG(2k, q)).
3 ^ ' / q - 1
Proof. The hyperplane at infinity in the projective closure of AG(2k, q), is isomorphic to PG(2k - 1, q), hence it admits a (k - 1)-spread L =	... , ^qfc+1}. Let A(£j) = jn£i, 1, n£i, 2,..., , qk} denote the set of the qk parallel k-dimensional subspaces in AG(2k, q) whose projective closures intersect in £j. Then, by Proposition 3.1, the intersection n£.jS nn^.,t is a single affine point for all i = j and 1 < s,t < qk.
First, to any triple of (k - 1)-dimensional subspaces, e, f, g G L, we assign qk + 2 color classes as follows. Take a fourth (k - 1)-dimensional subspace d g L, and, for u = (qk - 1)/(q-1), denote the points of the (k-1)-dimensional subspaces d, e, f and g by D1, D2,..., Du, E1, E2,..., Eu, F1, F2,..., Fu and G1, G2,..., Gu, respectively. For any triple (Dj, e, g) there is a unique line through Dj which intersects the skew subspaces e and g. We can choose the numbering of the points Ej and Gj such that the line Ej Gj intersects d in Dj for i = 1, 2,..., u; the numbering of the points Fj, such that the line DjEj+1 intersects d and g for i = 1,2,..., u - 1, and, finally, choose the line D„E1 that intersects d and g. Notice that this construction implies that the line DjEj does not intersect g for i = 1,2,..., u. Let the points of nd1 denote by M1, M2,..., Mqk. We can choose the numbering of the elements of A(e), A(f) and A(g) such that nejj nn ^ nnSjj = {Mj} for i = 1, 2,..., qk.
We define three types of color classes for i = 1, 2,..., u and j = 1,2,..., qk. Let f g and Bj' f g be the color classes that contain the lines through Mj whose point at infinity is Ej and Fj, respectively. Let Cj ' f g be the color class that contains the lines in ne, j whose point at infinity is Ej, except the line Ej Mj, the lines in n , j whose point at infinity is Fj, except the line Fj Mj, and the lines in ng , j whose point at infinity is Gj. Hence each of Bj,' f g and Bj,' f g contains qk lines and Cj'f g contains 3qk-1 - 2 lines. Notice that for each i G {1,2,..., u}, the union of the color classes
v-j = pi'0 , , Bj '1 , ,qfc Cj'j Ke , f, g = Be, f ,g U Be , f ,g Uj=1 Ce , f, g
G. Araujo-Pardo et al.: On chromatic indices of finite affine spaces
75
contains all lines whose point at infinity is E^ Fj or Gj. Each of the two sets of lines belonging to Bj f g or Bj,' f g, naturally defines a (k +1)-dimensional subspace of PG(2k, q), we denote these subspaces by nE. and nFi, respectively.
For t = 0,1,..., |_(qk - 2 - 'e)/3j let'e = 4t+1, f = ¿st+2, g = 4t+s, d = 4t+4, define ^qfc+2-e as and make the qk + 2 color classes Bj,' f g, Bj,' f g and Cjf g. Finally, for each point P in the subspace £qk+1 if e =1, or in £qk if e = 2, define a new color class which contains all lines whose point at infinity is P.
Clearly, the coloring is proper and it contains, by definition, the required number of color classes. Now, we prove that it is complete. Notice that each color class of type obviously intersects any other color class. In relation to the other cases we have that:
•	The color classes Bj ' 3 e e and Bj' 3 ,, e intersect, because both of them contain all points of the k-dimensional subspace n^3m+4 , 1.
•	If t = m then the color classes Bj '3 „ e and Bj '3 „ e intersect,
'	¿3t + 1 /3t + 2, ¿3t+3	(3m+1, ¿3m+2, (3m+3
because the (k - 1)-dimensional subspaces ^st+4 and ^Sm+4 are skew in hence the 2-dimensional intersection of the (k + 1)-dimensional subspaces nEi or nFi, according as j = 1 or 2, and nE, or nF,, according as j' = 1 or 2, is not a subspace of Thus Proposition 3.1 implies that their intersection contains some affine points.
•	The color classes Bj'3 „ „ and Gj '3 „ e intersect in both cases
(3m+1 ' (3m+2 /3m + 3	¿3t + 1 , ¿3t+2 , ¿3t+3
m = t and m = t, because the (k - 1)-dimensional subspaces ^Sm+4 and ^st+s are skew in . Again, Proposition 3.1 implies that the intersection of the k-dimensional subspaces n£3m+4,1 (which is a subspace of either the (k + 1)-dimensional subspace nEi or nFi, according as j = 1 or 2) and n^3 is an affine point.
•	If t = m then each pair of color classes Cj '3 e e and Cj '3 e e ,
'	1	^3t + 1 '^3t + 2 '^3t + 3	t3m + 1 '^3m + 2 '^3m + 3 7
intersects since, as previously, the (k - 1)-dimensional subspaces ^st+s and ^3m+s are skew in thus Proposition 3.1 implies that the projective closures of the k-dimensional subspaces n^3t+3, j and n^3m+3, j/ intersect each other in AG(2k, q).
•	Finally, we prove that each pair of classes Cj '3 e „ and Cj '3 e „ intersects. It is obvious when i = i'. Suppose that i = i', let Mj = n^3t+1, j n
n^3t+2' j n n^3t+3' j and Mj/ = n^3t+1' j, n n^3t+2' j, n n^3t+3' j,. Since the points Mj and Mj, are in n^3t+4 , 1, the line MjMj, intersects in ^st+4. Take the point T = MjMj, n ^st+4 and the lines E3T and E3 T. Clearly, at least one of these lines does not intersect ¿st+s, we may assume without loss of generality, that E3T n ¿st+s = 0.
By Proposition 3.1, there exist affine points Nj = n^3t+1 j n n^3t+3, j, and Nj, =
n^3t+1 'j, n n£3t+3,j. Suppose that Nj G EjMj, and Nj, G E3MM». Then ¿st+1 n MjMj, = 0, hence (^st+1, MjMj,} is a (k + 1)-dimensional subspace Ek+1, which intersects in a k-dimensional subspace . Obviously, also contains the points Ej and Ej. Then Efc = (^st+1, T}, and n ^st+s is a single point, say U. As the lines Nj, Mj and NjMj, are in the k-dimensional subspaces n^3t+3, j and n^3t+3, j,, respectively, there exist the points Nj,Mj n ^st+s and NjMj, n ^st+s. Moreover, we have that Nj,Mj n ^st+s = NjMj, n ^st+s = U. Hence the points Nj, Mj, Nj, and Mj, are contained in a 2-dimensional subspace S2, and S2 n contains the points U, E3, Ej, and T. Consequently, S2 n is the line E3 T and it contains the point U, thus E3 T intersects the subspace ^st+s, contradiction.
76
ArsMath. Contemp. 16(2019)203-213
Thus Nj G Ejr Mj/ or N^ G Ej Mj. This implies that Nj or N^ is a common point of the color classes
In consequence, the coloring is complete.
and C' j , , .
□
To conclude this section we prove our third main theorem. Proof of Theorem 1.3. As v = q2k, from Theorem 3.5 we get
+ 1 - e, k , , ^ qk - 1 _ q3k + (2 - e)q2k + (2e - 1)qk - 2 - e
3
+ 2) + e
q - 1	3(q - 1)
1 Vv(v - 1) (2 - e)v + 2eVV - 2 - e = 3 q - 1 +	3(q - 1)	'
which proves the statement. 4 Small dimensions
□
In this section, we improve on our bounds in two and three dimensions. First, we prove the exact values of achromatic and pseudoachromatic indices of finite affine planes. Due to the fact that there exist non-desarguesian affine planes, we use the notation Aq for an arbitrary affine plane of order q. For the axiomatic definition of Aq we refer to [11]. The basic combinatorial properties of Aq are the same as of AG(2, q).
Theorem 4.1. Let Aq be any affine plane of order q. Then
xX (Aq ) = a'(Aq ) = q +1.
Proof. Let Si, S2,..., Sq+1 denote the q +1 parallell classes of lines in Aq. Two lines have a point in common if and only if they belong to distinct parallel classes. Hence, if we define a coloring ^ with q +1 colors such that a line I gets color i if and only if I G Sj then ^ is proper, so q +1 < x'(Aq).
Since x'(Aq) < a'(Aq), it is enough to prove that a'(Aq) < q +1. Suppose to the contrary that ^ is a complete and proper coloring with m > q +1 color classes. As ^ is proper, each color class must be a subset of a parallel class. By the pigeonhole principle, m > q+1 implies that there exist at least two color classes that are subsets of the same parallel class. Hence they do not contain intersecting lines, contradicting to the completeness of Thus a'(Aq) < q +1, the theorem is proved.	□
Theorem 4.2. Let Aq be any affine plane of order q. Then

Proof. First, we prove that ^'(Aq) <
(q+1)2
(q+1)2
. Suppose to the contrary that f is a com-
plete coloring of Aq with
(q+1)2
+ 1 color classes. As Aq has q2 + q lines, this implies
that f has at most q2 + q - (q+1) J + 1) color classes of cardinality greater than one. Thus, there are at least
(q+1)2
+ 1 - q2 + q -
(q+1)2
+ 1 =
q + 2, if q is even, q + 3, if q is odd,
2
2
2
2
2
G. Araujo-Pardo et al.: On chromatic indices of finite affine spaces
77
color classes of size one. Hence, again by the pigeonhole principle, there are at least two color classes of size one belonging to the same parallel class. They have empty intersection, so ( is not complete. This contradiction shows that ^'(Aq ) <
We go on to give a complete coloring of Aq with
a point and e1, e2,
Sq+1
be the lines through P.
(q+1)2 2
For i
(q+1)2 2
color classes. Let P be
1, 2,,..., q +1 let S,
be the parallel class containing ei and denote the q — 1 lines in the set Si \ {ei} by
ti.i
(q+1)+i,
X
(q-2)(q+1)+i
Then:
U (Si \{ei}) = {h,l2,...,£q2-1},
and ij and ij+1 are non-parallel lines for all 1 < j < q2 -1. For better clarity, we construct
q2 — 1
color classes with odd indices. Let the
q +1 color classes with even indices and color class C2k consist of one line, ek, for k = 1,2,..., q + 1. Let the color class C2k—1
a2 — 1
contain the lines i2k-1 and i2k for k = 1,2,...,	, finally, if q is even, let the color
class Ca2—3 contain the line ia2_1, too.
The coloring is complete, because color classes having even indices intersect at P, and each color class with odd index contains two non-parallel lines whose union intersects all lines of the plane.	□
Our last construction gives a lower bound for the achromatic index of AG(3, q). As a'(AG(3, q)) < ^'(AG(3, q)), this can be considered as well as a lower estimate on the pseudoachromatic index of AG(3, q) and this bound is better than the general one proved in Theorem 3.4. We use the cyclic model of PG(2, q) to make the coloring. The detailed description of this model can be found in [16, Theorem 4.8 and Corollary 4.9]. We collect the most important properties of the cyclic model in the following proposition.
Proposition 4.3. Let q be a prime power. Then the group Zq2+a+1 admits a perfect difference set D = {d0,d1,d2,... ,da}, that is the q2 + q integers di — dj (i = j) are all distinct modulo q2 + q +1. We may assume without loss of generality that d0 =0 and d1 = 1. The plane PG(2, q) can be represented in the following way. The points are the elements of Za2+a+1, the lines are the subsets
D + j = {di + j : di e D} for j =0,1,..., q2 + q, and the incidence is the set theoretical inclusion. Theorem 4.4. The achromatic index of AG(3, q) satisfies the inequality:
q(q +1)2
2
+ 1 < a'(AG(3,q)).
Proof. The plane at infinity in the projective closure of AG(3, q), is isomorphic to PG(2, q), hence it has a cyclic representation (described in Proposition 4.3). Let v = q2 + q +1, let the points and the lines of be P1, P2,..., Pv, and i1, i2,..., iv, respectively. We can choose the numbering such that for i = 1,2,3,..., v the line ii contains the points Pi, Pi+1 and Pi—d (where 0 = d =1 is a fixed element of the difference set D, and the subscripts are taken modulo v).
78
Ars Math. Contemp. 16 (2019) 245-255
Let A(Pj) = {nPiii,nPi,2,...,nPi,q} denote the set of the q parallel planes in AG(3, q) whose projective closures intersect in £j, and nPi,j denote the projective closure of nPij- for i = 1,3,..., v, and j = 1,2,..., q. Let Wj be a plane whose projective closure intersects in £j_d. Then the projective closure of each element of A(Pj) U A(Pj+1) intersects Wj in a line whose point at infinity is Pg, so we can choose the numbering of the elements of A(Pg) and A(Pj+1), such that nPi,j n nPi+1ij- c Wj for i = 1, 3,..., v - 2, and j = 1,2,..., q. Let ej denote the line nPij- n nPi+1ij-.
We assign q +1 color classes to the pair (Pj, Pj+1) for i = 1, 3,..., v - 2. Let the color class Cg contain the lines el, e2 ..., eq. For j = 1, 2,..., q, let the color class Cj contain those lines of nP. j whose point at infinity is Pg, except the line ej, and the q parallel lines of nPi+1,j whose point at infinity is Pj+1. Finally, let the color class Cv contain all lines whose point at infinity is Pv. In this way we constructed
,v - 1	q(q + 1)2
(q + 1) —+ 1 = q(q + ) +1
color classes and each line belongs to exactly one of them, because C0i contains q lines, Cj contains 2q - 1 lines for each j = 1,2,..., q. and Cv contains q2 lines.
The coloring is proper by construction. The color class Cv obviously intersects any other class. For other pairs of color classes, two major cases are distinguished when we prove the completeness. On the one hand, if i = k then we have:
•	Cg n C0fc = 0, because the planes Wj and W0 intersect each other;
•	if j > 0 then Cg n Ck = 0, because the planes Wg and nPk+1 ,j intersect each other;
•	if m > 0 and j > 0 then C^ n CO = 0, because the planes nPi+1jm and nPfc+1ij intersect each other.
On the other hand, color classes having the same superscript also have non-empty intersection:
•	Cg n Cj = 0, because the planes Wg and nPi+1ij- intersect each other;
•	if j = k then the planes nPi j and nPi+1 0 intersect in a line f and f = ej, hence its points are not removed from nPi,j, so Cj n CO = 0.
Hence the coloring is also complete, this proves the theorem.	□
References
[1]	G. Araujo-Pardo, Gy. Kiss, C. Rubio-Montiel and A. Vazquez-Avila, On line colorings of finite projective spaces, 2018, arXiv:1702.06769 [math.CO] .
[2]	G. Araujo-Pardo, J. J. Montellano-Ballesteros, C. Rubio-Montiel and R. Strausz, On the pseu-doachromatic index of the complete graph II, Bol. Soc. Mat. Mex. 20 (2014), 17-28, doi: 10.1007/s40590-014-0007-9.
[3]	G. Araujo-Pardo, J. J. Montellano-Ballesteros, C. Rubio-Montiel and R. Strausz, On the pseu-doachromatic index of the complete graph III, Graphs Combin. 34 (2018), 277-287, doi: 10.1007/s00373-017-1872-6.
[4]	G. Araujo-Pardo, J. J. Montellano-Ballesteros and R. Strausz, On the pseudoachromatic index of the complete graph, J. Graph Theory 66 (2011), 89-97, doi:10.1002/jgt.20491.
G. Araujo-Pardo et al.: On chromatic indices of finite affine spaces
79
[5]	G. Araujo-Pardo and C. Rubio-Montiel, Pseudoachromatic and connected-pseudoachromatic indices of the complete graph, Discrete Appl. Math. 231 (2017), 60-66, doi:10.1016/j.dam. 2017.03.019.
[6]	G. Araujo-Pardo, C. Rubio-Montiel and A. Vazquez-Avila, Note on the Erdos-Faber-Lovasz conjecture: quasigroups and complete digraphs, Ars Combin., in press.
[7]	G. Araujo-Pardo and A. Vazquez-Avila, A note on Erdos-Faber-Lovasz conjecture and edge coloring of complete graphs, Ars Combin. 129 (2016), 287-298.
[8]	A. Beutelspacher, D. Jungnickel and S. A. Vanstone, On the chromatic index of a finite projective space, Geom. Dedicata 32 (1989), 313-318, doi:10.1007/bf00147923.
[9]	A. Bouchet, Indice achromatique des graphes multiparti complets et reguliers, Cahiers Centre Etudes Rech. Oper. 20 (1978), 331-340.
[10]	C. J. Colbourn and M. J. Colbourn, Greedy colourings of Steiner triple systems, in: A. Bar-lotti, P. V. Ceccherini and G. Tallini (eds.), Combinatorics '81, North-Holland, Amsterdam, volume 18 of Annals of Discrete Mathematics, pp. 201-207, 1983, proceedings of the International Conference on Combinatorial Geometries and their Applications held in Rome, June 7 -12, 1981.
[11]	P. Dembowski, Finite Geometries, Classics in Mathematics, Springer-Verlag, Berlin, 1997, doi:10.1007/978-3-642-62012-6, reprint of the 1968 original.
[12]	P. Erdos, Problems and results in combinatorial analysis and combinatorial analysis, in: C. St. J. A. Nash-Williams and J. Sheehan (eds.), Proceedings of the Fifth British Combinatorial Conference, Utilitas Mathematica Publishing, Winnipeg, Manitoba, volume 15 of Congressus Numerantium, pp. 169-192, 1976, held at the University of Aberdeen, Aberdeen, July 14-18, 1975.
[13]	P. Erdos, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25-42, doi:10.1007/bf02579174.
[14]	R. P. Gupta, Bounds on the chromatic and achromatic numbers of complementary graphs, in: W. T. Tutte (ed.), Recent Progress in Combinatorics, Academic Press, New York, pp. 229-235, 1969, proceedings of the Third Waterloo Conference on Combinatorics, May 1968.
[15]	F. Harary, S. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Portugal. Math. 26 (1967), 453-462, http://eudml.org/doc/1150 4 7.
[16]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Mathematical Monographs, The Clarendon Press, New York, 2nd edition, 1998.
[17]	R. E. Jamison, On the edge achromatic numbers of complete graphs, Discrete Math. 74 (1989), 99-115, doi:10.1016/0012-365x(89)90202-1.
[18]	A. Rosa and C. J. Colbourn, Colorings of block designs, in: J. H. Dinitz and D. R. Stinson (eds.), Contemporary Design Theory, John Wiley & Sons, New York, Wiley-Interscience Series in Discrete Mathematics and Optimization, pp. 401-430, 1992.