Large minimal multiple blocking sets

That’s four adjectives to describe the topic of my most recent preprint with Anurag Bishnoi and Jeroen Schillewaert. Although the object itself isn’t that hard to grasp, it doesn’t quite roll off the tongue very well. It deals with the following problem, for which we will start explaining adjectives right to left.

Consider a finite projective plane \Pi of order n. A blocking set of \Pi is a set of points such that every line contains at least one point. A t-fold blocking set, 1 \leq t \leq n+1, is a set of points such that every line contains at least, you guessed it, t points. If we do not wish to specify the number t, we can talk about multiple blocking sets. A t-fold blocking set is minimal if through every point of the blocking set there exists a line intersecting the set in exactly t points. Lastly,  large just refers to the size.

In general, most of the research in blocking sets has been occupied with how small a (t-fold) blocking set can be. This is probably the most natural question when first encountering this object. However, one can also look at the other end of the spectrum and ask how large it can be. Clearly, a blocking set has size at most n^2+n+1, so for this question to make sense, people have introduced the notion of minimality. It is equivalent to saying that we cannot remove any point of the blocking set without destroying the t-fold blocking property, so it is indeed minimal w.r.t. to set containment.

In this way, Bruen and Thas proved in 1977 that the size of a minimal blocking set is upper bounded by n\sqrt{n}+1. In the preprint, we managed to generalize this upper bound from blocking sets to t-fold blocking sets, and showed that equality can only occur in some simple examples. Furthermore, it contains a variety of other results and some open questions at the end in which finite geometry people might be interested. So other than copy-pasting these results, I’d like to mention the technique we used to obtain the upper bound and how we got there.

In fact, the main technique, which is the expander mixing lemma, has already been elaborated on by Anurag in his blog, in which you can already see the upper bound appearing. It is a tool in graph theory, based on eigenvalue techniques, that is widely applicable (one can check the preprint for references thereof). However, there is little added value in retelling the same story as Anurag did, so perhaps the motivation is more interesting.

He told me he was first interested in this lemma for the following idea. It is an open question whether there exists a finite projective plane containing two disjoint unitals. A unital is the unique largest minimal blocking set, so perhaps if we had two disjoint unitals, we could create a very large minimal 2-fold blocking set, perhaps too large (i.e. in contradiction with upper bounds). However, such upper bounds were non-existent, which immediately gave the motivation for this work (for which he did most of the groundwork).

Now, if you skimmed through the paper, you will probably see that there is no mention of disjoint unitals anywhere. This is for the following reason: two disjoint unitals form a minimal 2-fold blocking set if and only if every tangent to one unital is tangent to the other. Therefore, these upper bounds can’t say anything about the problem of disjoint unitals in general. However, using them, there is a little bit of information on the number of shared tangents we can extract in the following way. Whether or not this is useful is a question for the experts.

The upper bound for a minimal 2-fold blocking set in a projective plane of order n is

\frac{1}{2}n(\sqrt{8n-7}+1)+2.

Clearly, two disjoint unitals cannot share all tangents, as this would imply a minimal 2-fold blocking set of size 2(n\sqrt{n}+1) which is strictly larger than the upper bound above. So suppose they share all but one. Then there exists a point x_1 on the first unital and a point x_2 on the second, such that their respective tangents are secant to the other unital. Therefore, we can remove both these points and obtain a 2-fold blocking set, which is again minimal, as all other tangents were shared. However, one can compute that the size of this set is again larger than the upper bound. This means that two disjoint unitals cannot share all tangents but one. One can do the same for all but two, all but three, up to all but \sqrt{n}+1. Therefore, we obtain the following fact.

Proposition. Two disjoint unitals have at least \sqrt{n}+1 non-shared tangents.

Although one can do better with direct methods, I still liked this fact as an example of a connection between two questions that are unrelated at first sight and how an idea for one problem can lead you to other unexpected and uncharted areas.

 

 

Advertisements
This entry was posted in Geen categorie. Bookmark the permalink.

2 Responses to Large minimal multiple blocking sets

  1. Pingback: An extremal problem in projective planes | Points And Lines

  2. Pingback: What I have learned in finite geometry | Anurag's Math Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s