Covering with most possible equal size subsets having pairwise singleton intersections
$begingroup$
Assume I have a non-empty finite set $S$ with $x=|S|$. I want to divide the set $S$ into subsets $S_1, S_2, .., S_n$ (Edit: Yes, $S = cup S_i$, and I'm embarrassed that I forgot to include that) such that:
- $ |S_i| = y, forall 1 le i le n$ (The cardinality of each subset is fixed)
- $|S_i cap S_j| = 1, forall 1 le i,j le n, i neq j$ (Each subset has exactly 1 element in common with any other subset)
Edit: The second condition above excludes the possiblility of a pairwise disjoint division of subsets.
Is there a way to determine the maximum value of $n$ (the number of possible subsets), given $x$ and $y$?
combinatorics
$endgroup$
|
show 2 more comments
$begingroup$
Assume I have a non-empty finite set $S$ with $x=|S|$. I want to divide the set $S$ into subsets $S_1, S_2, .., S_n$ (Edit: Yes, $S = cup S_i$, and I'm embarrassed that I forgot to include that) such that:
- $ |S_i| = y, forall 1 le i le n$ (The cardinality of each subset is fixed)
- $|S_i cap S_j| = 1, forall 1 le i,j le n, i neq j$ (Each subset has exactly 1 element in common with any other subset)
Edit: The second condition above excludes the possiblility of a pairwise disjoint division of subsets.
Is there a way to determine the maximum value of $n$ (the number of possible subsets), given $x$ and $y$?
combinatorics
$endgroup$
$begingroup$
Are there any constraints on $x$ and $y$? For example with $x = 1$ and $y = 2013$ you might have some trouble doing that.
$endgroup$
– dtldarek
Jul 12 '13 at 13:35
$begingroup$
@dtldarek If we don't require $S=bigcup S_i$, then this merely implies that $n=0$ is maximal for such $(x,y)$.
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:37
$begingroup$
@HagenvonEitzen Well, I would say that the phrase "divide the set $S$ into subsets..." does imply $S = bigcup S_i$.
$endgroup$
– dtldarek
Jul 12 '13 at 13:39
1
$begingroup$
@dtldarek Then again, I'd also say that divide implies $S_icap S_j=emptyset$ ...
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:40
2
$begingroup$
Whatever it is, I'd be great if OP could clarify ;-)
$endgroup$
– dtldarek
Jul 12 '13 at 13:42
|
show 2 more comments
$begingroup$
Assume I have a non-empty finite set $S$ with $x=|S|$. I want to divide the set $S$ into subsets $S_1, S_2, .., S_n$ (Edit: Yes, $S = cup S_i$, and I'm embarrassed that I forgot to include that) such that:
- $ |S_i| = y, forall 1 le i le n$ (The cardinality of each subset is fixed)
- $|S_i cap S_j| = 1, forall 1 le i,j le n, i neq j$ (Each subset has exactly 1 element in common with any other subset)
Edit: The second condition above excludes the possiblility of a pairwise disjoint division of subsets.
Is there a way to determine the maximum value of $n$ (the number of possible subsets), given $x$ and $y$?
combinatorics
$endgroup$
Assume I have a non-empty finite set $S$ with $x=|S|$. I want to divide the set $S$ into subsets $S_1, S_2, .., S_n$ (Edit: Yes, $S = cup S_i$, and I'm embarrassed that I forgot to include that) such that:
- $ |S_i| = y, forall 1 le i le n$ (The cardinality of each subset is fixed)
- $|S_i cap S_j| = 1, forall 1 le i,j le n, i neq j$ (Each subset has exactly 1 element in common with any other subset)
Edit: The second condition above excludes the possiblility of a pairwise disjoint division of subsets.
Is there a way to determine the maximum value of $n$ (the number of possible subsets), given $x$ and $y$?
combinatorics
combinatorics
edited Jul 17 '13 at 12:50
hardmath
29.3k953101
29.3k953101
asked Jul 12 '13 at 13:33
taseriantaserian
25229
25229
$begingroup$
Are there any constraints on $x$ and $y$? For example with $x = 1$ and $y = 2013$ you might have some trouble doing that.
$endgroup$
– dtldarek
Jul 12 '13 at 13:35
$begingroup$
@dtldarek If we don't require $S=bigcup S_i$, then this merely implies that $n=0$ is maximal for such $(x,y)$.
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:37
$begingroup$
@HagenvonEitzen Well, I would say that the phrase "divide the set $S$ into subsets..." does imply $S = bigcup S_i$.
$endgroup$
– dtldarek
Jul 12 '13 at 13:39
1
$begingroup$
@dtldarek Then again, I'd also say that divide implies $S_icap S_j=emptyset$ ...
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:40
2
$begingroup$
Whatever it is, I'd be great if OP could clarify ;-)
$endgroup$
– dtldarek
Jul 12 '13 at 13:42
|
show 2 more comments
$begingroup$
Are there any constraints on $x$ and $y$? For example with $x = 1$ and $y = 2013$ you might have some trouble doing that.
$endgroup$
– dtldarek
Jul 12 '13 at 13:35
$begingroup$
@dtldarek If we don't require $S=bigcup S_i$, then this merely implies that $n=0$ is maximal for such $(x,y)$.
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:37
$begingroup$
@HagenvonEitzen Well, I would say that the phrase "divide the set $S$ into subsets..." does imply $S = bigcup S_i$.
$endgroup$
– dtldarek
Jul 12 '13 at 13:39
1
$begingroup$
@dtldarek Then again, I'd also say that divide implies $S_icap S_j=emptyset$ ...
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:40
2
$begingroup$
Whatever it is, I'd be great if OP could clarify ;-)
$endgroup$
– dtldarek
Jul 12 '13 at 13:42
$begingroup$
Are there any constraints on $x$ and $y$? For example with $x = 1$ and $y = 2013$ you might have some trouble doing that.
$endgroup$
– dtldarek
Jul 12 '13 at 13:35
$begingroup$
Are there any constraints on $x$ and $y$? For example with $x = 1$ and $y = 2013$ you might have some trouble doing that.
$endgroup$
– dtldarek
Jul 12 '13 at 13:35
$begingroup$
@dtldarek If we don't require $S=bigcup S_i$, then this merely implies that $n=0$ is maximal for such $(x,y)$.
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:37
$begingroup$
@dtldarek If we don't require $S=bigcup S_i$, then this merely implies that $n=0$ is maximal for such $(x,y)$.
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:37
$begingroup$
@HagenvonEitzen Well, I would say that the phrase "divide the set $S$ into subsets..." does imply $S = bigcup S_i$.
$endgroup$
– dtldarek
Jul 12 '13 at 13:39
$begingroup$
@HagenvonEitzen Well, I would say that the phrase "divide the set $S$ into subsets..." does imply $S = bigcup S_i$.
$endgroup$
– dtldarek
Jul 12 '13 at 13:39
1
1
$begingroup$
@dtldarek Then again, I'd also say that divide implies $S_icap S_j=emptyset$ ...
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:40
$begingroup$
@dtldarek Then again, I'd also say that divide implies $S_icap S_j=emptyset$ ...
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:40
2
2
$begingroup$
Whatever it is, I'd be great if OP could clarify ;-)
$endgroup$
– dtldarek
Jul 12 '13 at 13:42
$begingroup$
Whatever it is, I'd be great if OP could clarify ;-)
$endgroup$
– dtldarek
Jul 12 '13 at 13:42
|
show 2 more comments
3 Answers
3
active
oldest
votes
$begingroup$
Update: After filling up several sheets of scratch notes, and much Internet browsing, it dawned on me that the dual of the designs considered here are pairwise balanced designs on $n$ "points" (namely the sets $S_i$ described in the Question). Another way to put this insight is to say that if the original points of $S$ which are covered by only one set $S_i$, the reduced design that remains would be the dual of a linear space, rehabilitating the idea I broached as an Aside at the bottom of my first post. I'm working on integrating this new insight into a revised Answer.
The combinatorial objects described here can be approached from several directions. Perhaps most natural is (finite) incidence geometry, treating the finite set $S$ as the set of $x$ "points" and the $n$ subsets $S_i$ as "lines". Other approaches include covering 1-designs and hypergraph incidence matrices.
A partial linear space is an elementary kind of incidence geometry, satisfying two (redundant) axioms:
(1a) Two distinct lines meet in at most one point.
(1b) Through two distinct points there exists at most one line.
Here we have two specializations, specifically that:
(1p) Two lines meet in exactly one point.
(2u) Every line contain exactly y points.
Terminology for this precise combination of specialized partial linear spaces does not seem to be well established. For (2u) one can speak of a uniform partial linear space, those whose "block sizes" are uniform (equal). For (1p) the term that comes to mind most readily would be "projective", as projective planes are well-known for their absence of parallel lines (lines that do not meet), but trying to use that term here proves tricky because a projective geometry has also the unwanted property that there is one line through every pair of distinct points. So far the most concise yet precise phrase I can coin for the objects under study is uniform partial linear spaces with no parallel lines.
If the goal is to obtain as many lines $n$ as possible, then certainly the finite projective planes provide one family of maximal examples. It is well-known that a projective plane of order $q$ exists for each prime power $q$, and it is conjectured that these are the only ones. For a projective plane of order $q$, there are $x = q^2 + q + 1$ points, each line contains $y = q+1$ points, and there are $n = x$ equally many lines as points.
Unfortunately this is essentially a one-parameter family of solution sizes (although two projective planes of equal order and size need not be isomorphic). Designs with fewer lines than points are possible, and these must be considered where $x$ and $y$ differ from the projective plane possibilities. I've assembled a short table of the maximum $n$ for certain small values of $x$ and $y$ (still preliminary), highlighting the projective plane cases with a dagger ($dagger$).
$$ begin{array} {|r|c|c|c|c|}
hline
text{ x y}& 2 & 3 & 4 & 5 \
hline
2; & 1 & text{---} & text{---} & text{---} \
3; & 3^dagger & 1 & text{---} & text{---} \
4; & 3 & text{---} & 1 & text{---} \
5; & 4 & 2 & text{---} & 1 \
6; & 5 & 4 & text{---} & text{---} \
7; & 6 & 7^dagger & 2 & text{---} \
8; & 7 & text{---} & text{---} & text{---} \
9; & 8 & 4 & 3 & 2 \
10; & 9 & text{---} & 4 & text{---} \
11; & 10 & 5 & 4 & text{---} \
12; & 11 & text{---} & 5 & 3 \
13; & 12 & 6 & 13^dagger & 3 \
14; & 13 & text{---} & 7 & 4 \
15; & 14 & 7 & text{?} & 6 \
16; & 15 & text{---} & text{?} & text{?} \
hline end{array} $$
Aside: A linear space is a partial linear space satisfying additional assumptions:
(L1) Two distinct points share exactly one line.
(L2) Every line contains at least two points.
(L3) There are at least two lines.
At first it appears we might adopt the terminology of dual linear space, a derived notion where the roles of "point" and "line" interchange. Then (L1) would become the (1p) that we want (and (L3) is unobjectionable). Unfortunately (L2) would in dual terms say every point is covered by at least two lines, which though not necessarily a bad thing if you want more lines, still lies apart from the assumptions proscribed by the Question. It also makes it awkward to include the term "uniform" in a phrase as ambigous whether we mean the dual of a uniform (partial) linear space or a dual linear space that happens to be uniform (it is this latter we would want to convey).
$endgroup$
add a comment |
$begingroup$
To add to what @hardmath had written, Fisher's inequality guarantees $n leq x$.
See, e.g., here for a statement and a proof.
$endgroup$
$begingroup$
Thanks! I thought I'd said so, but clearly I got lost wandering around in the vast realm of incidence structures.
$endgroup$
– hardmath
May 14 '14 at 11:42
add a comment |
$begingroup$
Adding to @hardmath's aside. An interesting family of solutions in addition to the finite projective spaces are the dual finite affine planes (2-d vector spaces) over finite fields: $GF(q)^2$ . In those, it holds that
(a) two distinct points share exactly one line.
(b) each line contains exactly $q$ points,
(c) each point is incident with exactly $q+1$ lines.
(d) There are $q(q+1)$ total lines, and $q^2$ total points.
Not every two lines intersect, but as the accepted answer's aside mentioned, if we take the dual space, (a) implies (1p), and (c) implies (1u).
So to connect to the original question, the set $S$ is the set of all lines. The subsets would be indexed by each point $i$:
$S_i={l in S | I(i,l)}$ - the set of lines intersecting with point $i$.
$forall_i|S_i|=q+1$. And $S_i cap S_{j}=$the single line connecting $i$ and $j$, so $|S_p cap S_{p'}|=1$.
So this is a family of solutions with: $x=q(q+1),space y=q+1,space n=q^2$ for all $q$ which is a prime power. Not 100% sure this is maximal, though it sounds like it should be.
Edit: Just realized that in the same way that the affine plane is obtained from the projective plane by removing one line and all the points incident with it, so we can continue to remove additional lines and all the points incident with them from the affine plane. Each two remaining points would still be connected with exactly one line, but not every line will contain an equal number of points, but this wasn't a requirement in the original question. This is pretty wasteful, since it removes many points for each line, but maybe still finds solutions.
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f442043%2fcovering-with-most-possible-equal-size-subsets-having-pairwise-singleton-interse%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Update: After filling up several sheets of scratch notes, and much Internet browsing, it dawned on me that the dual of the designs considered here are pairwise balanced designs on $n$ "points" (namely the sets $S_i$ described in the Question). Another way to put this insight is to say that if the original points of $S$ which are covered by only one set $S_i$, the reduced design that remains would be the dual of a linear space, rehabilitating the idea I broached as an Aside at the bottom of my first post. I'm working on integrating this new insight into a revised Answer.
The combinatorial objects described here can be approached from several directions. Perhaps most natural is (finite) incidence geometry, treating the finite set $S$ as the set of $x$ "points" and the $n$ subsets $S_i$ as "lines". Other approaches include covering 1-designs and hypergraph incidence matrices.
A partial linear space is an elementary kind of incidence geometry, satisfying two (redundant) axioms:
(1a) Two distinct lines meet in at most one point.
(1b) Through two distinct points there exists at most one line.
Here we have two specializations, specifically that:
(1p) Two lines meet in exactly one point.
(2u) Every line contain exactly y points.
Terminology for this precise combination of specialized partial linear spaces does not seem to be well established. For (2u) one can speak of a uniform partial linear space, those whose "block sizes" are uniform (equal). For (1p) the term that comes to mind most readily would be "projective", as projective planes are well-known for their absence of parallel lines (lines that do not meet), but trying to use that term here proves tricky because a projective geometry has also the unwanted property that there is one line through every pair of distinct points. So far the most concise yet precise phrase I can coin for the objects under study is uniform partial linear spaces with no parallel lines.
If the goal is to obtain as many lines $n$ as possible, then certainly the finite projective planes provide one family of maximal examples. It is well-known that a projective plane of order $q$ exists for each prime power $q$, and it is conjectured that these are the only ones. For a projective plane of order $q$, there are $x = q^2 + q + 1$ points, each line contains $y = q+1$ points, and there are $n = x$ equally many lines as points.
Unfortunately this is essentially a one-parameter family of solution sizes (although two projective planes of equal order and size need not be isomorphic). Designs with fewer lines than points are possible, and these must be considered where $x$ and $y$ differ from the projective plane possibilities. I've assembled a short table of the maximum $n$ for certain small values of $x$ and $y$ (still preliminary), highlighting the projective plane cases with a dagger ($dagger$).
$$ begin{array} {|r|c|c|c|c|}
hline
text{ x y}& 2 & 3 & 4 & 5 \
hline
2; & 1 & text{---} & text{---} & text{---} \
3; & 3^dagger & 1 & text{---} & text{---} \
4; & 3 & text{---} & 1 & text{---} \
5; & 4 & 2 & text{---} & 1 \
6; & 5 & 4 & text{---} & text{---} \
7; & 6 & 7^dagger & 2 & text{---} \
8; & 7 & text{---} & text{---} & text{---} \
9; & 8 & 4 & 3 & 2 \
10; & 9 & text{---} & 4 & text{---} \
11; & 10 & 5 & 4 & text{---} \
12; & 11 & text{---} & 5 & 3 \
13; & 12 & 6 & 13^dagger & 3 \
14; & 13 & text{---} & 7 & 4 \
15; & 14 & 7 & text{?} & 6 \
16; & 15 & text{---} & text{?} & text{?} \
hline end{array} $$
Aside: A linear space is a partial linear space satisfying additional assumptions:
(L1) Two distinct points share exactly one line.
(L2) Every line contains at least two points.
(L3) There are at least two lines.
At first it appears we might adopt the terminology of dual linear space, a derived notion where the roles of "point" and "line" interchange. Then (L1) would become the (1p) that we want (and (L3) is unobjectionable). Unfortunately (L2) would in dual terms say every point is covered by at least two lines, which though not necessarily a bad thing if you want more lines, still lies apart from the assumptions proscribed by the Question. It also makes it awkward to include the term "uniform" in a phrase as ambigous whether we mean the dual of a uniform (partial) linear space or a dual linear space that happens to be uniform (it is this latter we would want to convey).
$endgroup$
add a comment |
$begingroup$
Update: After filling up several sheets of scratch notes, and much Internet browsing, it dawned on me that the dual of the designs considered here are pairwise balanced designs on $n$ "points" (namely the sets $S_i$ described in the Question). Another way to put this insight is to say that if the original points of $S$ which are covered by only one set $S_i$, the reduced design that remains would be the dual of a linear space, rehabilitating the idea I broached as an Aside at the bottom of my first post. I'm working on integrating this new insight into a revised Answer.
The combinatorial objects described here can be approached from several directions. Perhaps most natural is (finite) incidence geometry, treating the finite set $S$ as the set of $x$ "points" and the $n$ subsets $S_i$ as "lines". Other approaches include covering 1-designs and hypergraph incidence matrices.
A partial linear space is an elementary kind of incidence geometry, satisfying two (redundant) axioms:
(1a) Two distinct lines meet in at most one point.
(1b) Through two distinct points there exists at most one line.
Here we have two specializations, specifically that:
(1p) Two lines meet in exactly one point.
(2u) Every line contain exactly y points.
Terminology for this precise combination of specialized partial linear spaces does not seem to be well established. For (2u) one can speak of a uniform partial linear space, those whose "block sizes" are uniform (equal). For (1p) the term that comes to mind most readily would be "projective", as projective planes are well-known for their absence of parallel lines (lines that do not meet), but trying to use that term here proves tricky because a projective geometry has also the unwanted property that there is one line through every pair of distinct points. So far the most concise yet precise phrase I can coin for the objects under study is uniform partial linear spaces with no parallel lines.
If the goal is to obtain as many lines $n$ as possible, then certainly the finite projective planes provide one family of maximal examples. It is well-known that a projective plane of order $q$ exists for each prime power $q$, and it is conjectured that these are the only ones. For a projective plane of order $q$, there are $x = q^2 + q + 1$ points, each line contains $y = q+1$ points, and there are $n = x$ equally many lines as points.
Unfortunately this is essentially a one-parameter family of solution sizes (although two projective planes of equal order and size need not be isomorphic). Designs with fewer lines than points are possible, and these must be considered where $x$ and $y$ differ from the projective plane possibilities. I've assembled a short table of the maximum $n$ for certain small values of $x$ and $y$ (still preliminary), highlighting the projective plane cases with a dagger ($dagger$).
$$ begin{array} {|r|c|c|c|c|}
hline
text{ x y}& 2 & 3 & 4 & 5 \
hline
2; & 1 & text{---} & text{---} & text{---} \
3; & 3^dagger & 1 & text{---} & text{---} \
4; & 3 & text{---} & 1 & text{---} \
5; & 4 & 2 & text{---} & 1 \
6; & 5 & 4 & text{---} & text{---} \
7; & 6 & 7^dagger & 2 & text{---} \
8; & 7 & text{---} & text{---} & text{---} \
9; & 8 & 4 & 3 & 2 \
10; & 9 & text{---} & 4 & text{---} \
11; & 10 & 5 & 4 & text{---} \
12; & 11 & text{---} & 5 & 3 \
13; & 12 & 6 & 13^dagger & 3 \
14; & 13 & text{---} & 7 & 4 \
15; & 14 & 7 & text{?} & 6 \
16; & 15 & text{---} & text{?} & text{?} \
hline end{array} $$
Aside: A linear space is a partial linear space satisfying additional assumptions:
(L1) Two distinct points share exactly one line.
(L2) Every line contains at least two points.
(L3) There are at least two lines.
At first it appears we might adopt the terminology of dual linear space, a derived notion where the roles of "point" and "line" interchange. Then (L1) would become the (1p) that we want (and (L3) is unobjectionable). Unfortunately (L2) would in dual terms say every point is covered by at least two lines, which though not necessarily a bad thing if you want more lines, still lies apart from the assumptions proscribed by the Question. It also makes it awkward to include the term "uniform" in a phrase as ambigous whether we mean the dual of a uniform (partial) linear space or a dual linear space that happens to be uniform (it is this latter we would want to convey).
$endgroup$
add a comment |
$begingroup$
Update: After filling up several sheets of scratch notes, and much Internet browsing, it dawned on me that the dual of the designs considered here are pairwise balanced designs on $n$ "points" (namely the sets $S_i$ described in the Question). Another way to put this insight is to say that if the original points of $S$ which are covered by only one set $S_i$, the reduced design that remains would be the dual of a linear space, rehabilitating the idea I broached as an Aside at the bottom of my first post. I'm working on integrating this new insight into a revised Answer.
The combinatorial objects described here can be approached from several directions. Perhaps most natural is (finite) incidence geometry, treating the finite set $S$ as the set of $x$ "points" and the $n$ subsets $S_i$ as "lines". Other approaches include covering 1-designs and hypergraph incidence matrices.
A partial linear space is an elementary kind of incidence geometry, satisfying two (redundant) axioms:
(1a) Two distinct lines meet in at most one point.
(1b) Through two distinct points there exists at most one line.
Here we have two specializations, specifically that:
(1p) Two lines meet in exactly one point.
(2u) Every line contain exactly y points.
Terminology for this precise combination of specialized partial linear spaces does not seem to be well established. For (2u) one can speak of a uniform partial linear space, those whose "block sizes" are uniform (equal). For (1p) the term that comes to mind most readily would be "projective", as projective planes are well-known for their absence of parallel lines (lines that do not meet), but trying to use that term here proves tricky because a projective geometry has also the unwanted property that there is one line through every pair of distinct points. So far the most concise yet precise phrase I can coin for the objects under study is uniform partial linear spaces with no parallel lines.
If the goal is to obtain as many lines $n$ as possible, then certainly the finite projective planes provide one family of maximal examples. It is well-known that a projective plane of order $q$ exists for each prime power $q$, and it is conjectured that these are the only ones. For a projective plane of order $q$, there are $x = q^2 + q + 1$ points, each line contains $y = q+1$ points, and there are $n = x$ equally many lines as points.
Unfortunately this is essentially a one-parameter family of solution sizes (although two projective planes of equal order and size need not be isomorphic). Designs with fewer lines than points are possible, and these must be considered where $x$ and $y$ differ from the projective plane possibilities. I've assembled a short table of the maximum $n$ for certain small values of $x$ and $y$ (still preliminary), highlighting the projective plane cases with a dagger ($dagger$).
$$ begin{array} {|r|c|c|c|c|}
hline
text{ x y}& 2 & 3 & 4 & 5 \
hline
2; & 1 & text{---} & text{---} & text{---} \
3; & 3^dagger & 1 & text{---} & text{---} \
4; & 3 & text{---} & 1 & text{---} \
5; & 4 & 2 & text{---} & 1 \
6; & 5 & 4 & text{---} & text{---} \
7; & 6 & 7^dagger & 2 & text{---} \
8; & 7 & text{---} & text{---} & text{---} \
9; & 8 & 4 & 3 & 2 \
10; & 9 & text{---} & 4 & text{---} \
11; & 10 & 5 & 4 & text{---} \
12; & 11 & text{---} & 5 & 3 \
13; & 12 & 6 & 13^dagger & 3 \
14; & 13 & text{---} & 7 & 4 \
15; & 14 & 7 & text{?} & 6 \
16; & 15 & text{---} & text{?} & text{?} \
hline end{array} $$
Aside: A linear space is a partial linear space satisfying additional assumptions:
(L1) Two distinct points share exactly one line.
(L2) Every line contains at least two points.
(L3) There are at least two lines.
At first it appears we might adopt the terminology of dual linear space, a derived notion where the roles of "point" and "line" interchange. Then (L1) would become the (1p) that we want (and (L3) is unobjectionable). Unfortunately (L2) would in dual terms say every point is covered by at least two lines, which though not necessarily a bad thing if you want more lines, still lies apart from the assumptions proscribed by the Question. It also makes it awkward to include the term "uniform" in a phrase as ambigous whether we mean the dual of a uniform (partial) linear space or a dual linear space that happens to be uniform (it is this latter we would want to convey).
$endgroup$
Update: After filling up several sheets of scratch notes, and much Internet browsing, it dawned on me that the dual of the designs considered here are pairwise balanced designs on $n$ "points" (namely the sets $S_i$ described in the Question). Another way to put this insight is to say that if the original points of $S$ which are covered by only one set $S_i$, the reduced design that remains would be the dual of a linear space, rehabilitating the idea I broached as an Aside at the bottom of my first post. I'm working on integrating this new insight into a revised Answer.
The combinatorial objects described here can be approached from several directions. Perhaps most natural is (finite) incidence geometry, treating the finite set $S$ as the set of $x$ "points" and the $n$ subsets $S_i$ as "lines". Other approaches include covering 1-designs and hypergraph incidence matrices.
A partial linear space is an elementary kind of incidence geometry, satisfying two (redundant) axioms:
(1a) Two distinct lines meet in at most one point.
(1b) Through two distinct points there exists at most one line.
Here we have two specializations, specifically that:
(1p) Two lines meet in exactly one point.
(2u) Every line contain exactly y points.
Terminology for this precise combination of specialized partial linear spaces does not seem to be well established. For (2u) one can speak of a uniform partial linear space, those whose "block sizes" are uniform (equal). For (1p) the term that comes to mind most readily would be "projective", as projective planes are well-known for their absence of parallel lines (lines that do not meet), but trying to use that term here proves tricky because a projective geometry has also the unwanted property that there is one line through every pair of distinct points. So far the most concise yet precise phrase I can coin for the objects under study is uniform partial linear spaces with no parallel lines.
If the goal is to obtain as many lines $n$ as possible, then certainly the finite projective planes provide one family of maximal examples. It is well-known that a projective plane of order $q$ exists for each prime power $q$, and it is conjectured that these are the only ones. For a projective plane of order $q$, there are $x = q^2 + q + 1$ points, each line contains $y = q+1$ points, and there are $n = x$ equally many lines as points.
Unfortunately this is essentially a one-parameter family of solution sizes (although two projective planes of equal order and size need not be isomorphic). Designs with fewer lines than points are possible, and these must be considered where $x$ and $y$ differ from the projective plane possibilities. I've assembled a short table of the maximum $n$ for certain small values of $x$ and $y$ (still preliminary), highlighting the projective plane cases with a dagger ($dagger$).
$$ begin{array} {|r|c|c|c|c|}
hline
text{ x y}& 2 & 3 & 4 & 5 \
hline
2; & 1 & text{---} & text{---} & text{---} \
3; & 3^dagger & 1 & text{---} & text{---} \
4; & 3 & text{---} & 1 & text{---} \
5; & 4 & 2 & text{---} & 1 \
6; & 5 & 4 & text{---} & text{---} \
7; & 6 & 7^dagger & 2 & text{---} \
8; & 7 & text{---} & text{---} & text{---} \
9; & 8 & 4 & 3 & 2 \
10; & 9 & text{---} & 4 & text{---} \
11; & 10 & 5 & 4 & text{---} \
12; & 11 & text{---} & 5 & 3 \
13; & 12 & 6 & 13^dagger & 3 \
14; & 13 & text{---} & 7 & 4 \
15; & 14 & 7 & text{?} & 6 \
16; & 15 & text{---} & text{?} & text{?} \
hline end{array} $$
Aside: A linear space is a partial linear space satisfying additional assumptions:
(L1) Two distinct points share exactly one line.
(L2) Every line contains at least two points.
(L3) There are at least two lines.
At first it appears we might adopt the terminology of dual linear space, a derived notion where the roles of "point" and "line" interchange. Then (L1) would become the (1p) that we want (and (L3) is unobjectionable). Unfortunately (L2) would in dual terms say every point is covered by at least two lines, which though not necessarily a bad thing if you want more lines, still lies apart from the assumptions proscribed by the Question. It also makes it awkward to include the term "uniform" in a phrase as ambigous whether we mean the dual of a uniform (partial) linear space or a dual linear space that happens to be uniform (it is this latter we would want to convey).
edited Jul 24 '13 at 14:24
answered Jul 16 '13 at 17:41
hardmathhardmath
29.3k953101
29.3k953101
add a comment |
add a comment |
$begingroup$
To add to what @hardmath had written, Fisher's inequality guarantees $n leq x$.
See, e.g., here for a statement and a proof.
$endgroup$
$begingroup$
Thanks! I thought I'd said so, but clearly I got lost wandering around in the vast realm of incidence structures.
$endgroup$
– hardmath
May 14 '14 at 11:42
add a comment |
$begingroup$
To add to what @hardmath had written, Fisher's inequality guarantees $n leq x$.
See, e.g., here for a statement and a proof.
$endgroup$
$begingroup$
Thanks! I thought I'd said so, but clearly I got lost wandering around in the vast realm of incidence structures.
$endgroup$
– hardmath
May 14 '14 at 11:42
add a comment |
$begingroup$
To add to what @hardmath had written, Fisher's inequality guarantees $n leq x$.
See, e.g., here for a statement and a proof.
$endgroup$
To add to what @hardmath had written, Fisher's inequality guarantees $n leq x$.
See, e.g., here for a statement and a proof.
answered May 14 '14 at 8:16
Felix GoldbergFelix Goldberg
22337
22337
$begingroup$
Thanks! I thought I'd said so, but clearly I got lost wandering around in the vast realm of incidence structures.
$endgroup$
– hardmath
May 14 '14 at 11:42
add a comment |
$begingroup$
Thanks! I thought I'd said so, but clearly I got lost wandering around in the vast realm of incidence structures.
$endgroup$
– hardmath
May 14 '14 at 11:42
$begingroup$
Thanks! I thought I'd said so, but clearly I got lost wandering around in the vast realm of incidence structures.
$endgroup$
– hardmath
May 14 '14 at 11:42
$begingroup$
Thanks! I thought I'd said so, but clearly I got lost wandering around in the vast realm of incidence structures.
$endgroup$
– hardmath
May 14 '14 at 11:42
add a comment |
$begingroup$
Adding to @hardmath's aside. An interesting family of solutions in addition to the finite projective spaces are the dual finite affine planes (2-d vector spaces) over finite fields: $GF(q)^2$ . In those, it holds that
(a) two distinct points share exactly one line.
(b) each line contains exactly $q$ points,
(c) each point is incident with exactly $q+1$ lines.
(d) There are $q(q+1)$ total lines, and $q^2$ total points.
Not every two lines intersect, but as the accepted answer's aside mentioned, if we take the dual space, (a) implies (1p), and (c) implies (1u).
So to connect to the original question, the set $S$ is the set of all lines. The subsets would be indexed by each point $i$:
$S_i={l in S | I(i,l)}$ - the set of lines intersecting with point $i$.
$forall_i|S_i|=q+1$. And $S_i cap S_{j}=$the single line connecting $i$ and $j$, so $|S_p cap S_{p'}|=1$.
So this is a family of solutions with: $x=q(q+1),space y=q+1,space n=q^2$ for all $q$ which is a prime power. Not 100% sure this is maximal, though it sounds like it should be.
Edit: Just realized that in the same way that the affine plane is obtained from the projective plane by removing one line and all the points incident with it, so we can continue to remove additional lines and all the points incident with them from the affine plane. Each two remaining points would still be connected with exactly one line, but not every line will contain an equal number of points, but this wasn't a requirement in the original question. This is pretty wasteful, since it removes many points for each line, but maybe still finds solutions.
$endgroup$
add a comment |
$begingroup$
Adding to @hardmath's aside. An interesting family of solutions in addition to the finite projective spaces are the dual finite affine planes (2-d vector spaces) over finite fields: $GF(q)^2$ . In those, it holds that
(a) two distinct points share exactly one line.
(b) each line contains exactly $q$ points,
(c) each point is incident with exactly $q+1$ lines.
(d) There are $q(q+1)$ total lines, and $q^2$ total points.
Not every two lines intersect, but as the accepted answer's aside mentioned, if we take the dual space, (a) implies (1p), and (c) implies (1u).
So to connect to the original question, the set $S$ is the set of all lines. The subsets would be indexed by each point $i$:
$S_i={l in S | I(i,l)}$ - the set of lines intersecting with point $i$.
$forall_i|S_i|=q+1$. And $S_i cap S_{j}=$the single line connecting $i$ and $j$, so $|S_p cap S_{p'}|=1$.
So this is a family of solutions with: $x=q(q+1),space y=q+1,space n=q^2$ for all $q$ which is a prime power. Not 100% sure this is maximal, though it sounds like it should be.
Edit: Just realized that in the same way that the affine plane is obtained from the projective plane by removing one line and all the points incident with it, so we can continue to remove additional lines and all the points incident with them from the affine plane. Each two remaining points would still be connected with exactly one line, but not every line will contain an equal number of points, but this wasn't a requirement in the original question. This is pretty wasteful, since it removes many points for each line, but maybe still finds solutions.
$endgroup$
add a comment |
$begingroup$
Adding to @hardmath's aside. An interesting family of solutions in addition to the finite projective spaces are the dual finite affine planes (2-d vector spaces) over finite fields: $GF(q)^2$ . In those, it holds that
(a) two distinct points share exactly one line.
(b) each line contains exactly $q$ points,
(c) each point is incident with exactly $q+1$ lines.
(d) There are $q(q+1)$ total lines, and $q^2$ total points.
Not every two lines intersect, but as the accepted answer's aside mentioned, if we take the dual space, (a) implies (1p), and (c) implies (1u).
So to connect to the original question, the set $S$ is the set of all lines. The subsets would be indexed by each point $i$:
$S_i={l in S | I(i,l)}$ - the set of lines intersecting with point $i$.
$forall_i|S_i|=q+1$. And $S_i cap S_{j}=$the single line connecting $i$ and $j$, so $|S_p cap S_{p'}|=1$.
So this is a family of solutions with: $x=q(q+1),space y=q+1,space n=q^2$ for all $q$ which is a prime power. Not 100% sure this is maximal, though it sounds like it should be.
Edit: Just realized that in the same way that the affine plane is obtained from the projective plane by removing one line and all the points incident with it, so we can continue to remove additional lines and all the points incident with them from the affine plane. Each two remaining points would still be connected with exactly one line, but not every line will contain an equal number of points, but this wasn't a requirement in the original question. This is pretty wasteful, since it removes many points for each line, but maybe still finds solutions.
$endgroup$
Adding to @hardmath's aside. An interesting family of solutions in addition to the finite projective spaces are the dual finite affine planes (2-d vector spaces) over finite fields: $GF(q)^2$ . In those, it holds that
(a) two distinct points share exactly one line.
(b) each line contains exactly $q$ points,
(c) each point is incident with exactly $q+1$ lines.
(d) There are $q(q+1)$ total lines, and $q^2$ total points.
Not every two lines intersect, but as the accepted answer's aside mentioned, if we take the dual space, (a) implies (1p), and (c) implies (1u).
So to connect to the original question, the set $S$ is the set of all lines. The subsets would be indexed by each point $i$:
$S_i={l in S | I(i,l)}$ - the set of lines intersecting with point $i$.
$forall_i|S_i|=q+1$. And $S_i cap S_{j}=$the single line connecting $i$ and $j$, so $|S_p cap S_{p'}|=1$.
So this is a family of solutions with: $x=q(q+1),space y=q+1,space n=q^2$ for all $q$ which is a prime power. Not 100% sure this is maximal, though it sounds like it should be.
Edit: Just realized that in the same way that the affine plane is obtained from the projective plane by removing one line and all the points incident with it, so we can continue to remove additional lines and all the points incident with them from the affine plane. Each two remaining points would still be connected with exactly one line, but not every line will contain an equal number of points, but this wasn't a requirement in the original question. This is pretty wasteful, since it removes many points for each line, but maybe still finds solutions.
edited Jan 8 at 16:53
answered Jan 7 at 19:28
ErnestScribblerErnestScribbler
1113
1113
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f442043%2fcovering-with-most-possible-equal-size-subsets-having-pairwise-singleton-interse%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Are there any constraints on $x$ and $y$? For example with $x = 1$ and $y = 2013$ you might have some trouble doing that.
$endgroup$
– dtldarek
Jul 12 '13 at 13:35
$begingroup$
@dtldarek If we don't require $S=bigcup S_i$, then this merely implies that $n=0$ is maximal for such $(x,y)$.
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:37
$begingroup$
@HagenvonEitzen Well, I would say that the phrase "divide the set $S$ into subsets..." does imply $S = bigcup S_i$.
$endgroup$
– dtldarek
Jul 12 '13 at 13:39
1
$begingroup$
@dtldarek Then again, I'd also say that divide implies $S_icap S_j=emptyset$ ...
$endgroup$
– Hagen von Eitzen
Jul 12 '13 at 13:40
2
$begingroup$
Whatever it is, I'd be great if OP could clarify ;-)
$endgroup$
– dtldarek
Jul 12 '13 at 13:42