Minimal multiple blocking sets

zbMATH Open1410.51009arXiv1703.07843MaRDI QIDQ668041FDOQ668041

Authors: Anurag Bishnoi, Sam Mattheus, Jeroen Schillewaert 

Publication date: 5 March 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We prove that a minimal $t$-fold blocking set in a finite projective plane of order $n$ has cardinality at most [frac{1}{2} nsqrt{4tn - (3t + 1)(t - 1)} + frac{1}{2} (t - 1)n + t.] This is the first general upper bound on the size of minimal $t$-fold blocking sets in finite projective planes and it generalizes the classical result of Bruen and Thas on minimal blocking sets. From the proof it directly follows that if equality occurs in this bound then every line intersects the blocking set $S$ in either $t$ points or $frac12(sqrt4tn-(3t+1)(t-1)+t-1)+1$ points. We use this to show that for $n$ a prime power, equality can occur in our bound in exactly one of the following three cases: (a) $t=1$, $n$ is a square and $S$ is a unital; (b) $t=n-sqrtn$, $n$ is a square and $S$ is the complement of a Baer subplane; (c) $t=n$ and $S$ is equal to the set of all points except one. For a square prime power $q$ and $tleqsqrtq+1$, we give a construction of a minimal $t$-fold blocking set $S$ in $mathrmPG(2,q)$ with $|S|=qsqrtq+1+(t-1)(q-sqrtq+1)$. Furthermore, we obtain an upper bound on the size of minimal blocking sets in symmetric $2$-designs and use it to give new proofs of other known results regarding tangency sets in higher dimensional finite projective spaces. We also discuss further generalizations of our bound. In our proofs we use an incidence bound on combinatorial designs which follows from applying the expander mixing lemma to the incidence graph of these designs.

Full work available at URL: https://arxiv.org/abs/1703.07843

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On multiple blocking sets in Galois planes
• A \(t\pmod p\) result on weighted multiple \((n-k)\)-blocking sets in \(\mathrm{PG}(n,q)\)
• Multiple Blocking Sets and Arcs in Finite Planes
• Blocking sets in Desarguesian affine and projective planes
• On large minimal blocking sets in PG(2,q)

zbMATH Keywords

blocking setfinite geometrysymmetric designexpander mixing lemma

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial aspects of block designs (05B05) Combinatorial aspects of finite geometries (05B25) Blocking sets, ovals, (k)-arcs (51E21)

Cites Work

• Spectra of graphs
• Interlacing eigenvalues and graphs
• Sets of type \((m,n)\) in the affine and projective planes of order nine
• On small complete arcs in a finite plane
• Small complete arcs in projective planes
• Expander graphs and their applications
• Unitals in projective planes
• Title not available (Why is that?)
• The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields
• Multiple Blocking Sets and Arcs in Finite Planes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite geometries.
• Polarities in finite projective planes
• Blocking sets
• Notes on semiarcs
• Some \(p\)-ranks related to orthogonal spaces
• The return of the Baer subplane
• Unitäre Polaritäten endlicher projektiver Ebenen
• A point-line incidence identity in finite fields, and applications
• Large incidence-free sets in geometries
• Hyperplane coverings and blocking sets
• Note on the existence of large minimal blocking sets in Galois planes
• Some new results on sets of type (m,n) in projective planes
• On semi ovals and semi ovoids
• Incidence bounds for block designs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite field Kakeya and Nikodym sets in three dimensions
• On large minimal blocking sets in PG(2,q)
• Finite geometry and combinatorial applications

Cited In (12)

• Unique reducibility of multiple blocking sets
• A geometric characterization of minimal codes and their asymptotic performance
• On multiple blocking sets in Galois planes
• On sensitivity in bipartite Cayley graphs
• On monoid graphs
• Large blocking sets in \(\mathrm{PG}(2,q^2)\)
• Triangle-free induced subgraphs of the unitary polarity graph
• Minimum blocking configurations
• Title not available (Why is that?)
• Generalizing Korchmáros-Mazzocca arcs
• A \(t\pmod p\) result on weighted multiple \((n-k)\)-blocking sets in \(\mathrm{PG}(n,q)\)
• Small Strong Blocking Sets by Concatenation

This page was built for publication: Minimal multiple blocking sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q668041)