Infinite family of large complete arcs in PG(2, q n ), with q odd and n > 1 odd

For q odd and n > 1 odd, a new infinite family of large complete arcs K′ in PG(2, q ⁿ ) is constructed from complete arcs K in PG(2, q) which have the following property with respect to an irreducible conic ${\mathcal{C}}$ in PG(2, q): all the points of K not in ${\mathcal{C}}$ are all internal or all external points to ${\mathcal{C}}$ according as q ≡ 1 (mod 4) or q ≡ 3 (mod 4).     

Transitive A 6-invariant k-arcs in PG(2, q)

For q = p ^r with a prime p ≥ 7 such that ${q \equiv 1}$ or 19 (mod 30), the desarguesian projective plane PG(2, q) of order q has a unique conjugacy class of projectivity groups isomorphic to the alternating group A ₆ of degree 6. For a projectivity group ${\Gamma \cong A_6}$ of PG(2, q), we investigate the geometric properties of the (unique) Γ-orbit ${\mathcal{O}}$ of size 90 such that the 1-point stabilizer of Γ in its action on ${\mathcal O}$ is a cyclic group of order 4. Here ${\mathcal O}$ lies either in PG(2, q) or in PG(2, q ²) according as 3 is a square or a non-square element in GF(q). We show that if q ≥ 349 and q ≠ 421, then ${\mathcal O}$ is a 90-arc, which turns out to be complete for q = 349, 409, 529, 601,661. Interestingly, ${\mathcal O}$ is the smallest known complete arc in PG(2,601) and in PG(2,661). Computations are carried out by MAGMA.     

Trivectors yielding spreads in PG(5, 2)

Given an alternating trilinear form ${T\in {\rm Alt}(\times^{3}V_{6})}$ on V ₆ = V(6, 2) let ${\mathcal{L}_{T}}$ denote the set of those lines ${\langle a, b \rangle}$ in ${{\rm PG}(5,2)=\mathbb{P}V_{6}}$ which are T-singular, satisfying, that is, T(a, b, x) = 0 for all ${x\in {\rm PG}(5, 2).}$ If ${\mathcal{L}_{21}}$ is a Desarguesian line-spread in PG(5, 2) it is shown that ${\mathcal{L}_{T}=\mathcal{L}_{21}}$ for precisely three choices T ₁,T ₂,T ₃ of T, which moreover satisfy T ₁ + T ₂ + T ₃ = 0. For ${T\in\mathcal{T}:=\{T_{1},T_{2},T_{3}\}}$ the ${\mathcal{G}_{T}}$ -orbits of flats in PG(5, 2) are determined, where ${\mathcal{G}_{T}\cong {\rm SL}(3,4).2}$ denotes the stabilizer of T under the action of GL(6, 2). Further, for a representative U of each ${\mathcal{G}_{T}}$ -orbit, the T-associate U ^# is also determined, where by definition $$U^{\#}=\{v\in {\rm PG}(5,2)\, |\, T(u_{1},u_{2},v) = 0\, \,{\rm for\,all }\, \, u_{1},u_{2}\in U\}$$ .     

Blocking Sets in PG(r, q n )

Let $\mathcal S$ be a Desarguesian (n – 1)-spread of a hyperplane Σ of PG(rn, q). Let Ω and ${\bar B}$ be, respectively, an (n – 2)-dimensional subspace of an element of $\mathcal S $ and a minimal blocking set of an ((r – 1)n + 1)-dimensional subspace of PG(rn, q) skew to Ω. Denote by K the cone with vertex Ω and base ${\bar B}$ , and consider the point set B defined by $$B=\left(K\setminus\Sigma\right)\cup \{X\in \mathcal S\, : \, X\cap K\neq \emptyset\}$$ in the Barlotti–Cofman representation of PG(r, q ⁿ ) in PG(rn, q) associated to the (n – 1)-spread $\mathcal S$ . Generalizing the constructions of Mazzocca and Polverino (J Algebraic Combin, 24(1):61–81, 2006), under suitable assumptions on ${\bar B}$ , we prove that B is a minimal blocking set in PG(r, q ⁿ ). In this way, we achieve new classes of minimal blocking sets and we find new sizes of minimal blocking sets in finite projective spaces of non-prime order. In particular, for q a power of 3, we exhibit examples of r-dimensional minimal blocking sets of size q ⁿ⁺² + 1 in PG(r, q ⁿ ), 3 ≤ r ≤ 6 and n ≥ 3, and of size q ⁴ + 1 in PG(r, q ²), 4 ≤ r ≤ 6; actually, in the second case, these blocking sets turn out to be the union of q ³ Baer sublines through a point. Moreover, for q an even power of 3, we construct examples of minimal blocking sets of PG(4, q) of size at least q ² + 2. From these constructions, we also get maximal partial ovoids of the hermitian variety H(4, q ²) of size q ⁴ + 1, for any q a power of 3.     

New upper bounds on the smallest size of a complete arc in a finite Desarguesian projective plane

In the projective planes PG(2, q), more than 1230 new small complete arcs are obtained for ${q \leq 13627}$ and ${q \in G}$ where G is a set of 38 values in the range 13687,..., 45893; also, ${2^{18} \in G}$ . This implies new upper bounds on the smallest size t ₂(2, q) of a complete arc in PG(2, q). From the new bounds it follows that $$t_{2}(2, q) < 4.5\sqrt{q} \, {\rm for} \, q \leq 2647$$ and q = 2659,2663,2683,2693,2753,2801. Also, $$t_{2}(2, q) < 4.8\sqrt{q} \, {\rm for} \, q \leq 5419$$ and q = 5441,5443,5449,5471,5477,5479,5483,5501,5521. Moreover, $$t_{2}(2, q) < 5\sqrt{q} \, {\rm for} \, q \leq 9497$$ and q = 9539,9587,9613,9623,9649,9689,9923,9973. Finally, $$t_{2}(2, q) <5 .15\sqrt{q} \, {\rm for} \, q \leq 13627$$ and q = 13687,13697,13711,14009. Using the new arcs it is shown that $$t_{2}(2, q) < \sqrt{q}\ln^{0.73}q {\rm for} 109 \leq q \leq 13627\, {\rm and}\, q \in G.$$ Also, as q grows, the positive difference ${\sqrt{q}\ln^{0.73} q-\overline{t}_{2}(2, q)}$ has a tendency to increase whereas the ratio ${\overline{t}_{2}(2, q)/(\sqrt{q}\ln^{0.73} q)}$ tends to decrease. Here ${\overline{t}_{2}(2, q)}$ is the smallest known size of a complete arc in PG(2,q). These properties allow us to conjecture that the estimate ${t_{2}(2,q) < \sqrt{q}\ln ^{0.73}q}$ holds for all ${q \geq 109.}$ The new upper bounds are obtained by finding new small complete arcs in PG(2,q) with the help of a computer search using randomized greedy algorithms. Finally, new forms of the upper bound on t ₂(2,q) are proposed.     

On unitals in PG(2,q^2) stabilized by a homology group

The linear collineation group of a classical unital of $\mathrm{PG}(2,q^2)$ contains a group of homologies of order $q+1$ . In this paper we prove that if $\mathcal{U }$ is a unital of PG $(2,q^2)$ stabilized by a homology group of order $q+1$ and $q$ is a prime number, then $\mathcal{U }$ is classical.     

Cycle Lemma, Parking Functions and Related Multigraphs

For positive integers a and b, an ${(a, \overline{b})}$ -parking function of length n is a sequence (p ₁, . . . , p _n ) of nonnegative integers whose weakly increasing order q ₁ ≤ . . . ≤ q _n satisfies the condition q _i  < a + (i ? 1)b. In this paper, we give a new proof of the enumeration formula for ${(a, \overline{b})}$ -parking functions by using of the cycle lemma for words, which leads to some enumerative results for the ${(a, \overline{b})}$ -parking functions with some restrictions such as symmetric property and periodic property. Based on a bijection between ${(a, \overline{b})}$ -parking functions and rooted forests, we enumerate combinatorially the ${(a, \overline{b})}$ -parking functions with identical initial terms and symmetric ${(a, \overline{b})}$ -parking functions with respect to the middle term. Moreover, we derive the critical group of a multigraph that is closely related to ${(a, \overline{b})}$ -parking functions.     

Set-coloring of Edges and Multigraph Ramsey Numbers

Edge-colorings of multigraphs are studied where a generalization of Ramsey numbers is given. Let ${M_n^{(r)}}$ be the multigraph of order n, in which there are r edges between any two different vertices. Suppose q ₁, q ₂, . . . , q _k and r are positive integers, and q _i ≥ 2(1 ≤ i ≤ k), k > r. Let the multigraph Ramsey number ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ be the minimum positive integer n such that in any k-edge coloring of ${M_n^{(r)}}$ (every edge is colored with one among k given colors, and edges between the same pair of vertices are colored with different colors), there must be ${i \in \{1,2,\ldots,k\}}$ such that ${M_n^{(r)}}$ has such a complete subgraph of order q _i , of which all the edges are in color i. By Ramsey’s theorem it is easy to show ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ exists for given q ₁ ,q ₂, . . . , q _k and r. Lower and upper bounds for some multigraph Ramsey numbers are given.     

Colourful and Fractional (p,q)-theorems

Let p≥q≥d+1 be positive integers and let ${\mathcal{F}}$ be a finite family of convex sets in ${\mathbb{R}}^{d}$ . Assume that the elements of ${\mathcal{F}}$ are coloured with p colours. A p-element subset of ${\mathcal{F}}$ is heterochromatic if it contains exactly one element of each colour. The family ${\mathcal{F}}$ has the heterochromatic (p,q)-property if in every heterochromatic p-element subset there are at least q elements that have a point in common. We show that, under the heterochromatic (p,q)-condition, some colour class can be pierced by a finite set whose size we estimate from above in terms of d,p, and q. This is a colourful version of the famous (p,q)-theorem. (We prove a colourful variant of the fractional Helly theorem along the way.) A fractional version of the same problem is when the (p,q)-condition holds for all but an α fraction of the p-tuples in ${\mathcal{F}}$ . We show that, in the case that d=1, all but a β fraction of the elements of ${\mathcal{F}}$ can be pierced by p?q+1 points. Here β depends on α and p,q, and β→0 as α goes to zero.     

The non-existence of some NMDS codes and the extremal sizes of complete (n,3)-arcs in PG(2,16)

The non-existence of $[29+h,3+h,26]_{16}$ and $[29+h,4+h,25]_{16}$ -codes, $h\ge 0$ , is proven. These results are obtained using geometrical methods, exploiting the equivalence between NMDS codes of dimension $3$ and $(n,3)$ -arcs in $PG(2,q)$ . Along the way the packing problem for complete $(n,3)$ -arcs in $PG(2,16)$ is solved, proving that $m_{3}(2,16)=28$ and $t_{3}(2,16)=15$ and that the complete $(28,3)$ -arc and the complete $(15,3)$ -arc are unique up to collineations.     

Classification and nonexistence results for linear codes with prescribed minimum distances

Starting from a linear [n, k, d] _q code with dual distance ${d^{\bot}}$ , we may construct an ${[n - d^\bot, k - d^\bot +1,\geq d]_q}$ code with dual distance at least ${\left\lceil\frac{d^\bot}{q}\right\rceil}$ using construction Y ₁. The inverse construction gives a rule for the classification of all [n, k, d] _q codes with dual distance ${d^{\bot}}$ by adding ${d^\bot}$ further columns to the parity check matrices of the smaller codes. Isomorph rejection is applied to guarantee a small search space for this iterative approach. Performing a complete search based on this observation, we are able to prove the nonexistence of linear codes for 16 open parameter sets [n, k, d] _q , q =  2, 3, 4, 5, 7, 8. These results imply 217 new upper bounds in the known tables for the minimum distance of linear codes and establish the exact value in 109 cases.     

A note on maximal regular subsemigroups of the finite transformation semigroups \mathcal{T}(n,r)

Let $\mathcal{T}_{n}$ be the semigroup of all full transformations on the finite set X _n ={1,2,…,n}. For 1≤r≤n, set $\mathcal {T}(n, r)=\{ \alpha\in\mathcal{T}_{n} | \operatorname{rank}(\alpha)\leq r\}$ . In this note we show that, for 2≤r≤n?2, any maximal regular subsemigroup of the semigroup $\mathcal{T} (n,r)$ is idempotent generated, but this may not happen in the semigroup $\mathcal{T}(n, n-1)$ .     

Subsets of PG(n,2) and Maximal Partial Spreads in PG(4,2)

Put θ _n = # {points in PG(n,2)} and φ _n = #{lines in PG(n,2)}. Let ψ be anypoint-subset of PG(n,2). It is shown thatthe sum of L = #{internal lines of ψ} and L′= #{external lines of ψ} is the same for all ψ having the same cardinality:[6pt] Theorem A If k is defined by k = |ψ| ? θ _{n ? 1}, then $$L + L' = \phi _{n - 1} + k(k - 1)/2.$$ (The generalization of this to subsets of PG(n,3) is also obtained.) Let $\mathcal{S}$ be a partial spreadof lines in PG(4,2) and let N denote the number of reguli contained in $\mathcal{S}$ .Use of Theorem A gives rise to a simple proof of:[6pt] Theorem B If $\mathcal{S}$ is maximal then one of the followingholds: (i) $\left| \mathcal{S} \right| = 5,{\text{ }}N = 10;{\text{ }}$ (ii) $\left| \mathcal{S} \right| = 7,{\text{ }}N = 4;{\text{ }}$ (iii) $\left| \mathcal{S} \right| = 9,{\text{ }}N = 4.$ If (i) holds then $\mathcal{S}$ is spread in a hyperplane.It is shown that possibility (ii) is realized by precisely threeprojectively distinct types of partial spread. Explicit examplesare also given of four projectively distinct types of partialspreads which realize possibility (iii). For one of these types,type X, the four reguli have a common line. It isshown that those partial spreads in PG(4,2) of size 9 which arise, by a simple construction, from a spreadin PG(5,2), are all of type X.     

A construction for infinite families of semisymmetric graphs revealing their full automorphism group

We give a general construction leading to different non-isomorphic families $\varGamma_{n,q}(\mathcal{K})$ of connected q-regular semisymmetric graphs of order 2q ⁿ⁺¹ embedded in $\operatorname{PG}(n+1,q)$ , for a prime power q=p ^h , using the linear representation of a particular point set $\mathcal{K}$ of size q contained in a hyperplane of $\operatorname{PG}(n+1,q)$ . We show that, when $\mathcal{K}$ is a normal rational curve with one point removed, the graphs $\varGamma_{n,q}(\mathcal{K})$ are isomorphic to the graphs constructed for q=p ^h in Lazebnik and Viglione (J. Graph Theory 41, 249–258, 2002) and to the graphs constructed for q prime in Du et al. (Eur. J. Comb. 24, 897–902, 2003). These graphs were known to be semisymmetric but their full automorphism group was up to now unknown. For q≥n+3 or q=p=n+2, n≥2, we obtain their full automorphism group from our construction by showing that, for an arc $\mathcal{K}$ , every automorphism of $\varGamma_{n,q}(\mathcal{K})$ is induced by a collineation of the ambient space $\operatorname{PG}(n+1,q)$ . We also give some other examples of semisymmetric graphs $\varGamma _{n,q}(\mathcal{K})$ for which not every automorphism is induced by a collineation of their ambient space.     

Composed products and factors of cyclotomic polynomials over finite fields

Let q = p ^s be a power of a prime number p and let ${\mathbb {F}_{\rm q}}$ be a finite field with q elements. This paper aims to demonstrate the utility and relation of composed products to other areas such as the factorization of cyclotomic polynomials, construction of irreducible polynomials, and linear recurrence sequences over ${\mathbb {F}_{\rm q}}$ . In particular we obtain the explicit factorization of the cyclotomic polynomial ${\Phi_{2^nr}}$ over ${\mathbb {F}_{\rm q}}$ where both r ≥ 3 and q are odd, gcd(q, r) = 1, and ${n\in \mathbb{N}}$ . Previously, only the special cases when r = 1, 3, 5, had been achieved. For this we make the assumption that the explicit factorization of ${\Phi_r}$ over ${\mathbb {F}_{\rm q}}$ is given to us as a known. Let ${n = p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}}$ be the factorization of ${n \in \mathbb{N}}$ into powers of distinct primes p _i , 1 ≤ i ≤ s. In the case that the multiplicative orders of q modulo all these prime powers ${p_i^{e_i}}$ are pairwise coprime, we show how to obtain the explicit factors of ${\Phi_{n}}$ from the factors of each ${\Phi_{p_i^{e_i}}}$ . We also demonstrate how to obtain the factorization of ${\Phi_{mn}}$ from the factorization of ${\Phi_n}$ when q is a primitive root modulo m and ${{\rm gcd}(m, n) = {\rm gcd}(\phi(m),{\rm ord}_n(q)) = 1.}$ Here ${\phi}$ is the Euler’s totient function, and ord _n (q) denotes the multiplicative order of q modulo n. Moreover, we present the construction of a new class of irreducible polynomials over ${\mathbb {F}_{\rm q}}$ and generalize a result due to Varshamov (Soviet Math Dokl 29:334–336, 1984).     

Dihedral Biembeddings and Triangulations by Complete and Complete Tripartite Graphs

We construct biembeddings of some Latin squares which are Cayley tables of dihedral groups. These facilitate the construction of ${n^{an^2}}$ nonisomorphic face 2-colourable triangular embeddings of the complete tripartite graph K _n,n,n and the complete graph K _n for linear classes of values of n and suitable constants a. Previously the best known lower bounds for the number of such embeddings that are applicable to linear classes of values of n were of the form ${2^{an^2}.}$ We remark that trivial upper bounds are ${n^{n^2/3}}$ in the case of complete graphs K _n and ${n^{2n^2}}$ in the case of complete tripartite graphs K _n,n,n .     

On certain forms and quadrics related to symplectic dual polar spaces in characteristic 2

Let V be a 2n-dimensional vector space over a field ${\mathbb {F}}$ and ξ a non-degenerate alternating form defined on V. Let Δ be the building of type C _n formed by the totally ξ-isotropic subspaces of V and, for 1 ≤ k ≤ n, let ${\mathcal {G}_k}$ and Δ _k be the k-grassmannians of PG(V) and Δ, embedded in ${W_k=\wedge^kV}$ and in a subspace ${V_k\subseteq W_k}$ respectively, where ${{\rm dim}(V_k)={2n \choose k} - {2n \choose {k-2}}}$ . This paper is a continuation of Cardinali and Pasini (Des. Codes. Cryptogr., to appear). In Cardinali and Pasini (to appear), focusing on the case of k = n, we considered two forms α and β related to the notion of ‘being at non maximal distance’ in ${\mathcal {G}_n}$ and Δ _n and, under the hypothesis that ${{\rm char}(\mathbb {F}) \neq 2}$ , we studied the subspaces of W _n where α and β coincide or are opposite. In this paper we assume that ${{\rm char}(\mathbb {F}) = 2}$ . We determine which of the quadrics associated to α or β are preserved by the group ${G= {\rm Sp}(2n, \mathbb {F})}$ in its action on W _n and we study the subspace ${\mathcal {D}}$ of W _n formed by vectors v such that α(v, x) = β(v, x) for every ${x \in W_n}$ . Finally, we show how properties of ${\mathcal {D}}$ can be exploited to investigate the poset of G-invariant subspaces of V _k for k = n ? 2i and ${1\leq i \leq \lfloor n/2\rfloor}$ .     

On additive representation functions of finite sets, I (Variation)

If m ∈ ?, ? _m is the additive group of the modulo m residue classes, $\mathcal{A} \subset \mathbb{Z}_m$ and n ∈ ?, ? _m , then let $R\left( {\mathcal{A},n} \right)$ denote the number of solutions of a+a′ = n with $a,a' \in \mathcal{A}$ . The variation $V(\mathcal{A}) = \mathop {\max }\limits_{n \in \mathbb{Z}_m } |R(\mathcal{A},n + 1) - R(\mathcal{A},n)|$ is estimated in terms of the number of a’s with $a - 1 \notin \mathcal{A}$ , $a \in \mathcal{A}$ .