Computational investigation of the covering number of finite projective planes with small order

Our paper deals with Erdős’ problem related to the covering number of blocking sets of finite projective planes. An integer linear programming (ILP) formulation of Erdős’ problem is introduced for projective planes of given orders. The mathematical programming based approach is a new one for such finite projective planes. In view of the complexity of exact solution methods for integer programming problems and the available computational capacity a greedy algorithm for the ILP is presented and implemented. We produced a suboptimal solution for ILP (denoted by αG(q)) for 7 ≤ q ≤ 89, q prime and for q = 8,9,16. Our greedy algorithm is the only known method which for all integer α from a given interval (in our case α ∈ [αG(q), q]) produces a blocking set with property B(α + 1). According to our computational results the approximate value of αG(q) is c log q, where 1 ≤ c ≤ 2 holds. If q = 89 then the ILP contains 8012 integer variables and 8011 range constraints. All the variables, expect one, are binary. Finally, computational results and a comparison with the known theoretical results are presented.