Maximum Family of Subsets Intersecting in Exactly One Element
Source: Asked to me by Santosh Ananthakrishnan (EE IITB Fifth year undergraduate, To be Worldquant Analyst)
Problem:
At most, how many subsets can you find of the set A = {1, 2, ..., n} such that any two intersect in exactly one element?
Problem:
At most, how many subsets can you find of the set A = {1, 2, ..., n} such that any two intersect in exactly one element?
Solution:
Highlight the part between the * symbols for the answer.
* Answer: n.
Construction (n subsets): {1}, {1,2}, {1,3}, ..., {1,n} - every pair intersects in exactly {1}.
Upper bound: let A_1, ..., A_K be such a family and v_1, ..., v_K their 0-1 incidence vectors in R^n; the condition says v_i . v_j = 1 for i != j. The Gram matrix G (entries v_i . v_j) has |A_i| on the diagonal and 1 everywhere off it. If every |A_i| >= 2 then G = diag(|A_i| - 1) + J, a positive diagonal matrix plus a positive semidefinite one, hence invertible - so the v_i are linearly independent in an n-dimensional space and K <= n. If instead some set is a singleton, say A_1 = {x}: every other set must contain x (to meet A_1 in one element), and no two other sets can share any second element, so deleting x from each gives pairwise disjoint nonempty subsets of the remaining n - 1 elements - at most n - 1 of them, so K <= n again.
Solution by Dinesh Krithivasan (linear-algebra bound) and Kapil Dubey (induction) from the comments. *
is it 2 raised to n-1??
ReplyDeletebecause u can include one element in all the sets and then u have n-1 elements left , which can have 2^n-1 subsets....
Is the set A itself is excluded from the set of those subsets? Because the answer will be different in that case.
ReplyDeleteFor each set in the family, let v be a n-length binary vector that indicates which elements of {1,2,...,n} belong to that set. Then, the intersection criterion becomes v_i^T v_j = 1. Let K be the largest collection of sets satisfying this criterion. If we can find the rank of {v_1,v_2,...,v_K} as a function of K, this will have to be upper bounded by n and we will have an upper bound on K.
ReplyDeleteSome experimentation shows that K=n is possible. Take the family to be {{1,2,3,...,n-1},{1,n},{2,n},...{n-1,n}}. For n=2, it is easy to see that we can't do better than K=2. This suggests that we should try to prove that the vectors v1,v2...,v_K are linearly independent.
Computing the Gram determinant of these basis vectors is easy. The diagonal elements are the cardinalities of the sets in the family and all off-diagonals are 1. The determinant of this matrix is P + \sum_{i=1}^n P/(|A_i|-1) where P = \prod_{i=1}^n (|A_i|-1). Thus, as long as the sets are not singletons, the vectors will be linearly independent. QED.
Coming up with a non-easy example (other than the example above and {{1,n},{2,n}...{n-1,n},{n}}) of such families is an interesting exercise in its own right.
A similar approach:
ReplyDeleteThe characteristic functions of the sets can be viewed as vectors in n dimensions (with the added restriction that all components are either 1 or 0).
Upper bound:
Consider solving the problem: Given an n-dimensional space, find the largest set S of vectors such that the pairwise dot product is a.
We attempt a problem reduction as follows: Choose an arbitrary vector from the set, v. Rotate the space such that v points along one of the axes, say x. This does not change the pairwise dot product. Let the length of v be b. Now, since the dot product of v with all other vectors is a, for any other vector w in S, w . x = a / b.
Therefore, we must now solve the problem - find the set S' of vectors in n - 1 dimensions such that the pairwise dot product is a - a/ b.
This problem makes sense when a > a / b (This is always true). In the best case, we can assume that the dot product does not reduce in each step. Since each step reduces the number of dimensions by 1, |S| is upper bounded by n.
Lower bound: Example - The vectors
1 0 0 0 ...
1 1 0 0 0 ...
1 0 1 0 0 ...
1 0 0 1 0 ...
i.e.
x_0 = 1, x_i (i > 0) = 0;
x_0 = 1, x_i (unique i) = 1;
satisfy the conditions. This set is of size n.
2^n-2 if sum of elements of subset should be n
ReplyDeleteotherwise
n-2
Σ r(n-r-1)
r=1
Any 3 element subset, say (i,j,k) cannot be in the answer, because you can remove it and include (i,j) and (j,k) instead. Same holds for subsets with 4,5,... elements.
ReplyDeleteSo the answer is C(n,2)+C(n,1)+C(n,0).
"any 2 should intersect in exactly 1 element".
ReplyDeleteI should change my answer to C(n,2).
n*3^(n-1)
ReplyDeleteFind number of subsets such that element 1 is common between them. It is equivalent to choosing 2 disjoint subsets from remaining n-1 elements which is 3^(n-1).
Do that for element in the set.
i think it is n*2^(n-1) using the same logic as above.
ReplyDeleten
ReplyDeleteexplanation:
1 element can be chosen to shared.
then there be a maximum of n-1 disjoint sets of the left out n-1 elements, now if removed element is added to each of these sets we have n-1 subsets, the removed element itself will intersect with the rest of subsets in only one element,
hence the total no of subsets is n.
Incresing the size of any of these sets decreases the number of disjoint sets available, so the number of elements in each set should be kept to bare minumum ie 1
i think it's n-1.
ReplyDeleten-1 different elements in n-1 different subsets while remaining 1 element with each of the n-1 subsets.
The answer should be n.I agree with Karthi's logic and explanation.
ReplyDelete@gj: You forgot the n-th element could individually forma a subset as well
It should be n, the only way this seems possible is if (n-1) elements are taken in one of the subsets, and in each of the remaining subsets, the one element left out in the first subset is paired with the remaining elements of the first subset. (one by one) This makes n-1 subsets(with 2 elements each) plus the initial sub set (with n-1 elements).
ReplyDeleteIt is easy to see that the answer is n for n=2
ReplyDeleteNow, using induction, lets suppose that answer is k for k-set for all k <=n-1
So, if answer is more than n for an n-set, then removing n from each of the chosen subsets, we have two possibilities:
a) one of the subsets is {n} itself
b) none of the subsets is {n}
Case b) : immediately a contradiction after removal of n from each of the subsets
Case a) : every other subset contains {n}. Also, all the other subsets have only {n} as their intersection. So, there can be atmost n-1 more subsets. But, our supposition was that we have more than n subsets, which is proved wrong.
So, in both of the cases a and b, we have proved that the answer is <=n for an n-set.
And we have an example of n subsets for every n. So, the answer is n
it should be n*(n-1)/2
ReplyDeleteIt should be seen like this, intersection should give only one element so we can have 1,2,3 ...n as intersection,
ReplyDeletefor 1 as intersection we can have subsets: {1} {1,2} {1,3} {1,4}......{1,n} we cant have more than 2 elements in a subset other wise it would give two element by intersection with some subset out of {1,2} to {1,n}
for 2 as intersection we can have subsets{ {2} {2,3} {2,4}......{2,n}
so it is n+(n-1)+(n-2)+....+1 =n*(n-1)/2
Agree with ur logic....but as it clearly specify that we shud have exactly one common element in any 2 set... it means Eg:{1}&{2,3} both are not possible bcoz they dont have common element.
DeleteU can take any number 1 or 2....n.
for eg:{3,1},{3,2},{3},{3,4}....{3,n} = n subsets.
The answer is n.
The answer is n.
ReplyDeleteTry induction:
for n=1: {1};
for n=2: {1},{1,2};
for n=3: {1},{1,2},{1,3};
for n=4: {1},{1,2},{1,3},{1,4};
.......
for n=n: {1},.........{1,n);
Let the intersection element be 1 to start with,
ReplyDeleteNow, the 2 subsets could be (or can be selected by) -> C(n-1,x)*(2^n-1-x) (if x=1 it means one of the 2 subsets has only one element i.e. =1)
So, total no. of subsets = n*C(n-1,x)*(2^n-1-x)
I am not sure if this has a closed form expression. But I remember solving this using DP for some coding competition.
ReplyDeleteDP step is f(n)=max(f(k)+f(n-k)+k*n-k) (for k=1...n-1)
Explanation: say you partitioned {1..n} into to subsets, one of size k and the other of size n-k.
(f computer the answer at any x)
now the subsets with this partitioning would be f(k)+f(n-k) (obviously)
and now the interesting part k*(n-k) , this represents the number of sets that can be included in your set of sets that contains elements from both the partitions. And it is easy to see why you have to pick exactly one from each partition for the condition to hold to form a new set that you would want to include.
for those of you who came up with formulas other than f(n)=f(f)+f(n-k)+k*(n-k)
ReplyDeleteexplain why f(4)=8 {1 2 3 4 14 24 13 23 }
@Dinesh: Awesome solution! By the way how did u calculate the determinant of the matrix? Is it a well known formula?
ReplyDeleteLet any subset be represented by a n-length binary bit string.
ReplyDeleteIt is easy to see that we can form n subsets.
eg: {1,2,3,...,n-1},{1,n},{2,n},{3,n},...{n-1,n} (many other combinations are possible)
So we get the number of subsets, N>=n
Now consider 3 distinct subsets in the form of binary bit strings - a, b, and c.
[+ and . are bit-wise OR and AND operators]
So a.b, b.c and c.a has 1 element only, as per the criteria.
For N>n, we must have some vectors which are linear combinations of other vectors.
Let c be one such vector, such that c=a+b
a.c = a.(a+b) = a.a + a.b -> It will have one element only if a is a single element vector.
Similarly, b.c = b.b + b.a -> Here again, b will have to be a single element vector.
Also, a.b = 1
If a and b are single element vectors and a.b=1, then a = b -> contradiction!
So c cannot be a linear combination of a and b i.e. no vector in the set can be a linear combination of other vectors => N<=n
Combining both inequalities, we get N = n.
The answer would be:
ReplyDeleten*2^(n-1).
First you can pick any number and then, build any set from the rest of the numbers. And put the initial number into that set as well. This way you can have the number of sets such that exactly one element is common.
^@gaurushh Abey, ghar se hagg ke aaya kr na. Itne toh subsets hi nhin hote total.
DeleteNo - far smaller. The catch is that two of your subsets can share the common element AND nothing else: arbitrary subsets of the remaining n-1 elements intersect each other in more than the one common element. The answer is n. (replied using AI)
ReplyDeleteIt need not be excluded, but it does not help: if A itself is in the family, any other set B satisfies A ∩ B = B, so B must have exactly one element - and two distinct singletons are disjoint, so you get at most 2 sets. The maximum (n) comes from other constructions. (replied using AI)
ReplyDeleteThis is the right road - it is essentially the linear-algebra proof of the nonuniform Fisher inequality. Cleanest version: the incidence vectors v_i satisfy v_i . v_j = 1 for i != j, and v_i . v_i = |A_i|. If some |A_i| = 1 the family is small directly; otherwise the v_i are linearly independent (a combination summing to zero dotted with each v_j forces all coefficients equal, then the dot with the all-ones structure kills it), so the family has at most n sets. Answer: n. (replied using AI)
ReplyDeleteNo - see the thread; the answer is n. (replied using AI)
ReplyDeleteYour correction still misses: two pairs like {1,2} and {3,4} are disjoint, so you cannot take all C(n,2) pairs. Valid families of size n: {1},{1,2},{1,3},...,{1,n}, or the near-pencil {2,...,n},{1,2},{1,3},...,{1,n-1}... The answer is n. (replied using AI)
ReplyDeleteThe 3^(n-1) counts ways to pick two disjoint subsets - but you may only add ONE subset per "slot" of the family, and the family as a whole must stay pairwise-one-intersecting. Multiplying independent choices overcounts wildly; the true answer is n (see karthi's construction and the Fisher bound). (replied using AI)
ReplyDeleteSame issue as Gibraltar's count: the sets built this way intersect each other in more than one element. The answer is n. (replied using AI)
ReplyDeleteCorrect - the star family {c},{c,1},{c,2},...,{c,n-1} has n sets and pairwise intersection exactly {c}. And the matching upper bound (at most n) is the nonuniform Fisher inequality, via linear independence of the incidence vectors. Full solution. (replied using AI)
ReplyDeleteOne short - as the next commenter says, the shared element can also appear as a singleton set on its own, giving n. (replied using AI)
ReplyDeleteAgreed - n, with karthi's construction and the Fisher inequality for the upper bound. (replied using AI)
ReplyDeleteExactly - that is the "near-pencil" construction: {2,3,...,n}, {1,2}, {1,3}, ..., {1,n-1}... check pairs: the big set meets each pair in one element, and two pairs meet in {1}. n sets, and Fisher's inequality says you cannot do better. (replied using AI)
ReplyDeleteNice induction - case (a) is the heart: if {n} is in the family, every other set contains n, and deleting n from all of them leav
ReplyDeleteThe construction fails: in your "intersection 1" block you list {1},{1,2},...,{1,n} (fine so far), but then "intersection 2" add
ReplyDeleteBoth correct - the star construction achieves n, and the "exactly one common element" condition forbids disjoint pairs, which is
ReplyDeleteThe formula counts pairs of sets sharing element 1, but the family constraint is global - every pair simultaneously - so choices
ReplyDeleteYour example family does not satisfy the condition: {1,4} ∩ {2,3} is empty. The recurrence looks like it solves a different prob
ReplyDeleteThe matrix in the Fisher proof has the form M = D + J where D is diagonal with entries (|A_i| - 1) and J is the all-ones matrix.
ReplyDeleteRight approach - this is the linear-independence core of the Fisher inequality. One fix: work over the reals, not bitwise OR (OR
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteNo - sets built independently this way intersect each other in more than the one chosen element. The answer is n (star or near-p
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis recurrence solves a different problem - it assumes the family splits the ground set into two parts with sets taking exactly
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThe answer is indeed n, but what you have written is only the CONSTRUCTION (a family of size n), not an induction - listing {1},
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteToo small - already at n = 2 your formula gives 1, but {1} and {1,2} are two valid sets. The star construction {1},{1,2},...,{1,
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThe replacement move is invalid: (i,j) and (j,k) must each intersect EVERY other set in the family in exactly one element, not j
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete