New upper bounds on the smallest size t_{ 2}(2,q) of a complete arc in the projective plane PG(2,q) are obtained for 853 <= q <= 4561 and q\in T1\cup T2 where T1={ 173,181,193,229,243,257,271,277,293,343,373,409,443,449,457, 461,463,467,479,487,491,499,529,563,569,571,577,587,593,599,601,607,613,617,619,631, 641,661,673,677,683,691, 709}, T2={ 4597,4703,4723,4733,4789,4799,4813,4831,5003,5347,5641,5843,6011,8192}. From these new bounds it follows that for q <= 2593 and q=2693,2753, the relation t_{ 2}(2,q) < 4.5\sqrt{ q} holds. Also, for q <= 4561 we have t_{ 2}(2,q) < 4.75\sqrt{ q}. It is showed that for 23 <= q <= 4561 and q\in T2\cup { 2^{ 14},2^{ 15},2^{ 18}}, the inequality t_{ 2}(2,q) < \sqrt{ q}ln^{ 0.75}q is true. Moreover, the results obtained allow us to conjecture that this estimate holds for all q >= 23. The new upper bounds are obtained by finding new small complete arcs with the help of a computer search using randomized greedy algorithms. Also new constructions of complete arcs are proposed. These constructions form families of k-arcs in PG(2,q) containing arcs of all sizes k in a region k_{ min} <= k <= k_{ max} where k_{ min} is of order q/3 or q/4 while k_{ max} has order q/2. The completeness of the arcs obtained by the new constructions is proved for q <= 1367 and 2003 <= q <= 2063. There is reason to suppose that the arcs are complete for all q > 1367. New sizes of complete arcs in PG(2,q) are presented for 169 <= q <= 349 and q=1013,2003.
Categories: math.CO cs.IT math.IT