Abstract
Our paper deals with the covering number of finite projective planes which is related to an unsolved question of P. Erdös. An integer linear programming (ILP) formulation of the covering number of finite projective planes is introduced for projective planes of given orders. The mathematical programming based approach for this problem is new in the area of finite projective planes. Since the ILP problem is NP-hard and may involve up to 360.000 boolean variables for the considered problems, we propose a heuristic based on Simulated Annealing. The computational study gives a new insight into the structure of projective planes and their (minimal) blocking sets. This computational study indicates that the current theoretical results may be improved.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abbott, H.L. and A. Liu. (1985). “Property B(s) and Projective Planes.” Ars Combinatoria 20, 217–220.
Béres, L. and T. Illés. (1993). “Kis rendü projektív sÞkok metszésszámának számítógépes vizsgálata.” Alkalmazott Matematikai Lapok 17, 397–411. (In Hungarian. English Title: Computational Investigation of the Covering Number of Finite Projective Planes with Small Order).
Boros, E. (1988). “PG (2, q), p > 2 has Property B (p + 2).” Ars Combinatoria 25, 111–114.
Bruen, A.A. (1970). “Baer Subplanes and Blocking Sets.” Bull. Amer. Math. Soc. 76, 342–344.
Bruen, A.A. and J.A. Thas. (1977). “Blocking Sets.” Geom. Dedicata 6, 193–203.
Bruen, A.A. and J.C. Fischer. (1974). “Blocking Sets and Complete k-Arcs.” Pacific Journal of Math. 53, 73–84.
Burgess, D. (1957). “The Distribution of Quadratic Residues and Non-Residues.” Mathematica 4, 106–112.
CPLEX Manual Version 2.1., CPLEX Optimization, Inc., 1993.
Dowsland, K.A. (1995). “Simulated Annealing.” In C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems. London, UK: Mc-Graw Hill, pp. 20–69.
Erdös, P., R. Silvermann, and A. Stein. (1983). “Intersection Properties of Families Containing Sets of Nearly the Same Size.” Ars Combinatoria 15, 247–259.
Hirschfeld, J.W.P. (1979). Projective Geometries over Finite Fields. Oxford: Oxford University Press.
Illés T., T. Szönyi, and F. Wettl. (1991). “Blocking Sets and Maximal Strong Representative Systems in Finite Projective Planes.” Mitt. Math. Sem. Giessen 201, 97–107.
Kárteszi, F. (1974). Introduction to Finite Geometries. Budapest: Akadémiai Kiadó.
Metropolis, N. A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller (1953). “Equation of State Calculation by Fast Computing Machines.” J. of Chem. Phys. 21, 1087–1091.
Moorhouse, E. Private communication, 1996.
Szönyi, T. (1992a). “Note on the Existence of Large Minimal Blocking Sets in Galois Planes.” Combinatorica 12, 227–235.
Szönyi, T. (1992b). “Blocking Sets in Finite Planes and Spaces.” Ratio Mathematica 5, 93–106.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Illés, T., Pisinger, D. Upper Bounds on the Covering Number of Galois-Planes with Small Order. Journal of Heuristics 7, 59–76 (2001). https://doi.org/10.1023/A:1026517829321
Issue Date:
DOI: https://doi.org/10.1023/A:1026517829321