Otdfbt

Are athlete's college degrees discounted by employers and graduate school admissions?

How can I find out about the game world without meta-influencing it?

What's the difference between DHCP and NAT? Are they mutually exclusive?

Simple log rotation script

What publication claimed that Michael Jackson died in a nuclear holocaust?

Why are backslashes included in this shell script?

Why would a home insurer offer a discount based on credit score?

I sent an angry e-mail to my interviewers about a conflict at my home institution. Could this affect my application?

Was the Lonely Mountain, where Smaug lived, a volcano?

Boss making me feel guilty for leaving the company at the end of my internship

A team managed by my peer is close to melting down

How to represent jealousy in a cute way?

Is fission/fusion to iron the most efficient way to convert mass to energy?

How to deal with an excess of white-space in a CRM UI?

Dedicated bike GPS computer over smartphone

Why does there seem to be an extreme lack of public trashcans in Taiwan?

Does WiFi affect the quality of images downloaded from the internet?

Why would a car salesman tell me not to get my credit pulled again?

Undocumented incompatibility between changes and siunitx?

What's the relation between у.е. to USD?

Is all-caps blackletter no longer taboo?

Must a CPU have a GPU if the motherboard provides a display port (when there isn't any separate video card)?

What do I need to do, tax-wise, for a sudden windfall?

What is the source of 'Ma'alin bekodesh'?

A “distinguishing” family of subsets

Lower bound for the number of coin weightingsProve Intersection of Large Enough Subsets is Non-emptyMinimal collection of subsets to reconstruct singletonsUse of pigeonhole principle in ramsey-theorem about monochromatic triangles.Size of family $mathcal F = F_1, ldots, F_m$ is at least $lceil log_2nrceil$.Set theory question on subsets (considering pairs)How to use generalized pigeonhole principle to be sure that at least one of the integers picked is even?Proving that a set of 2016 natural numbers contain a non-empty set with a sum divisible by 2016The pigeonhole principle(?)Prove by using the Pigeonhole Principle that there are at least $5$ of the $41$ chess pieces on the $10×10$ board that are not on the same row.

5

2

$begingroup$

Suppose $A$ is a finite set, $B$ is a collection of subsets of $A$, satisfying the following condition:

$$forall a, b in A, a neq b: exists C in B: (a in C) land (b notin C)$$

What is the least possible size of $B$.

Currently, I know that the minimal size of $B$ is not less than $lceil log_2 |A| rceil$ (by pigeonhole principle), and it does not exceed $2lceil log_2 |A| rceil$ (an example of that size can trivially be constructed). However, I do not know the exact answer to the question.

combinatorics discrete-mathematics elementary-set-theory pigeonhole-principle

share|cite|improve this question

edited May 28 at 17:10

Yanior Weg

asked May 28 at 16:32

Yanior WegYanior Weg

3,14531857

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  But you surely mean $B subseteq mathfrak P(A)$, not $B in mathfrak P(A)$.
  $endgroup$
  – Andreas Caranti
  May 28 at 16:52
  

  
  
  
  

add a comment | 

5

2

$begingroup$

Suppose $A$ is a finite set, $B$ is a collection of subsets of $A$, satisfying the following condition:

$$forall a, b in A, a neq b: exists C in B: (a in C) land (b notin C)$$

What is the least possible size of $B$.

Currently, I know that the minimal size of $B$ is not less than $lceil log_2 |A| rceil$ (by pigeonhole principle), and it does not exceed $2lceil log_2 |A| rceil$ (an example of that size can trivially be constructed). However, I do not know the exact answer to the question.

combinatorics discrete-mathematics elementary-set-theory pigeonhole-principle

share|cite|improve this question

edited May 28 at 17:10

Yanior Weg

asked May 28 at 16:32

Yanior WegYanior Weg

3,14531857

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  But you surely mean $B subseteq mathfrak P(A)$, not $B in mathfrak P(A)$.
  $endgroup$
  – Andreas Caranti
  May 28 at 16:52
  

  
  
  
  

add a comment | 

$begingroup$

Suppose $A$ is a finite set, $B$ is a collection of subsets of $A$, satisfying the following condition:

$$forall a, b in A, a neq b: exists C in B: (a in C) land (b notin C)$$

What is the least possible size of $B$.

Currently, I know that the minimal size of $B$ is not less than $lceil log_2 |A| rceil$ (by pigeonhole principle), and it does not exceed $2lceil log_2 |A| rceil$ (an example of that size can trivially be constructed). However, I do not know the exact answer to the question.

combinatorics discrete-mathematics elementary-set-theory pigeonhole-principle

share|cite|improve this question

edited May 28 at 17:10

Yanior Weg

asked May 28 at 16:32

Yanior WegYanior Weg

3,14531857

$endgroup$

share|cite|improve this question

edited May 28 at 17:10

Yanior Weg

asked May 28 at 16:32

Yanior WegYanior Weg

3,14531857

share|cite|improve this question

edited May 28 at 17:10

Yanior Weg

asked May 28 at 16:32

Yanior WegYanior Weg

3,14531857

asked May 28 at 16:32

Yanior WegYanior Weg

3,14531857

asked May 28 at 16:32

Yanior WegYanior Weg

3,14531857

2 Answers
2

active

oldest

votes

7

$begingroup$

The answer by @FabioSomenzi is not just an upperbound - it is actually tight.

• Define $S(a) = C in B: a in C$ for all $a in A$. Note that $S(a) subset B$.




• The main condition $forall aneq b: exists C in B: a in C land b notin C$ becomes $forall aneq b: S(a) notsubset S(b)$




• Therefore the sets $S(a)_ain A$ form a Sperner family of size $|A|$.




• The result now follows from Sperner's theorem, that the maximum sized Sperner family formed by subsets of $B$ has size $ choose $

---

UPDATE 2019-05-29: Lets see if we can get an estimate on the coefficient. Using Stirling's approximation $n! sim sqrt2 pi n (n over e)^n$, we have

$$n choose n/2 = n! over (n/2)! (n/2)! sim sqrt2 pi n (n over e)^n over sqrtpi n (n/2 over e)^n/2 sqrtpi n (n/2 over e)^n/2 = sqrt2 over pi n 2^n > |A|$$

So asymptotically we have $n sim log_2 |A|$, i.e. the coefficient is $1$, i.e. the pigeonhole-based lower bound is pretty tight.

share|cite|improve this answer

edited May 29 at 13:07

answered May 28 at 23:39

antkamantkam

5,174415

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YaniorWeg - much as I appreciate the checkmark :) the credit really goes to Fabio, both for coming up with the idea and for a great explanation. As soon as I understood his proof, it's immediately obvious that his row vectors form an antichain / Sperner family, and then it's just a matter of me having heard of Sperner's theorem.
  $endgroup$
  – antkam
  May 29 at 12:49
  

  
  
  
  

add a comment | 

6

$begingroup$

An improved upper bound is given by the smallest $n$ such that

$$ binomnlfloor n/2 rfloor geq |A| enspace. $$

For $A = a,b,c,d,e$, we get $n=4$ and, for example, the following encoding:
$$
beginarrayc
a & 1100 \
b & 1010 \
c & 1001 \
d & 0110 \
e & 0101
endarray
$$
Reading the columns of the table, $B_1 = a,b,c, B_2 = a,d,e, B_3 = b,d, B_4 = c,e$. Since each element of $A$ appears in the same number of subsets, and no two elements appear in the same subsets, the condition is satisfied.

share|cite|improve this answer

answered May 28 at 17:56

Fabio SomenziFabio Somenzi

6,81121321

$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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3242984%2fa-distinguishing-family-of-subsets%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

7

$begingroup$

The answer by @FabioSomenzi is not just an upperbound - it is actually tight.

• Define $S(a) = C in B: a in C$ for all $a in A$. Note that $S(a) subset B$.




• The main condition $forall aneq b: exists C in B: a in C land b notin C$ becomes $forall aneq b: S(a) notsubset S(b)$




• Therefore the sets $S(a)_ain A$ form a Sperner family of size $|A|$.




• The result now follows from Sperner's theorem, that the maximum sized Sperner family formed by subsets of $B$ has size $ choose $

---

UPDATE 2019-05-29: Lets see if we can get an estimate on the coefficient. Using Stirling's approximation $n! sim sqrt2 pi n (n over e)^n$, we have

$$n choose n/2 = n! over (n/2)! (n/2)! sim sqrt2 pi n (n over e)^n over sqrtpi n (n/2 over e)^n/2 sqrtpi n (n/2 over e)^n/2 = sqrt2 over pi n 2^n > |A|$$

So asymptotically we have $n sim log_2 |A|$, i.e. the coefficient is $1$, i.e. the pigeonhole-based lower bound is pretty tight.

share|cite|improve this answer

edited May 29 at 13:07

answered May 28 at 23:39

antkamantkam

5,174415

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YaniorWeg - much as I appreciate the checkmark :) the credit really goes to Fabio, both for coming up with the idea and for a great explanation. As soon as I understood his proof, it's immediately obvious that his row vectors form an antichain / Sperner family, and then it's just a matter of me having heard of Sperner's theorem.
  $endgroup$
  – antkam
  May 29 at 12:49
  

  
  
  
  

add a comment | 

7

$begingroup$

The answer by @FabioSomenzi is not just an upperbound - it is actually tight.

• Define $S(a) = C in B: a in C$ for all $a in A$. Note that $S(a) subset B$.




• The main condition $forall aneq b: exists C in B: a in C land b notin C$ becomes $forall aneq b: S(a) notsubset S(b)$




• Therefore the sets $S(a)_ain A$ form a Sperner family of size $|A|$.




• The result now follows from Sperner's theorem, that the maximum sized Sperner family formed by subsets of $B$ has size $ choose $

---

UPDATE 2019-05-29: Lets see if we can get an estimate on the coefficient. Using Stirling's approximation $n! sim sqrt2 pi n (n over e)^n$, we have

$$n choose n/2 = n! over (n/2)! (n/2)! sim sqrt2 pi n (n over e)^n over sqrtpi n (n/2 over e)^n/2 sqrtpi n (n/2 over e)^n/2 = sqrt2 over pi n 2^n > |A|$$

So asymptotically we have $n sim log_2 |A|$, i.e. the coefficient is $1$, i.e. the pigeonhole-based lower bound is pretty tight.

share|cite|improve this answer

edited May 29 at 13:07

answered May 28 at 23:39

antkamantkam

5,174415

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YaniorWeg - much as I appreciate the checkmark :) the credit really goes to Fabio, both for coming up with the idea and for a great explanation. As soon as I understood his proof, it's immediately obvious that his row vectors form an antichain / Sperner family, and then it's just a matter of me having heard of Sperner's theorem.
  $endgroup$
  – antkam
  May 29 at 12:49
  

  
  
  
  

add a comment | 

$begingroup$

The answer by @FabioSomenzi is not just an upperbound - it is actually tight.

• Define $S(a) = C in B: a in C$ for all $a in A$. Note that $S(a) subset B$.




• The main condition $forall aneq b: exists C in B: a in C land b notin C$ becomes $forall aneq b: S(a) notsubset S(b)$




• Therefore the sets $S(a)_ain A$ form a Sperner family of size $|A|$.




• The result now follows from Sperner's theorem, that the maximum sized Sperner family formed by subsets of $B$ has size $ choose $

---

UPDATE 2019-05-29: Lets see if we can get an estimate on the coefficient. Using Stirling's approximation $n! sim sqrt2 pi n (n over e)^n$, we have

$$n choose n/2 = n! over (n/2)! (n/2)! sim sqrt2 pi n (n over e)^n over sqrtpi n (n/2 over e)^n/2 sqrtpi n (n/2 over e)^n/2 = sqrt2 over pi n 2^n > |A|$$

So asymptotically we have $n sim log_2 |A|$, i.e. the coefficient is $1$, i.e. the pigeonhole-based lower bound is pretty tight.

share|cite|improve this answer

edited May 29 at 13:07

answered May 28 at 23:39

antkamantkam

5,174415

$endgroup$

share|cite|improve this answer

edited May 29 at 13:07

answered May 28 at 23:39

antkamantkam

5,174415

answered May 28 at 23:39

antkamantkam

5,174415

answered May 28 at 23:39

antkamantkam

5,174415

6

$begingroup$

An improved upper bound is given by the smallest $n$ such that

$$ binomnlfloor n/2 rfloor geq |A| enspace. $$

For $A = a,b,c,d,e$, we get $n=4$ and, for example, the following encoding:
$$
beginarrayc
a & 1100 \
b & 1010 \
c & 1001 \
d & 0110 \
e & 0101
endarray
$$
Reading the columns of the table, $B_1 = a,b,c, B_2 = a,d,e, B_3 = b,d, B_4 = c,e$. Since each element of $A$ appears in the same number of subsets, and no two elements appear in the same subsets, the condition is satisfied.

share|cite|improve this answer

answered May 28 at 17:56

Fabio SomenziFabio Somenzi

6,81121321

$endgroup$

add a comment | 

6

$begingroup$

An improved upper bound is given by the smallest $n$ such that

$$ binomnlfloor n/2 rfloor geq |A| enspace. $$

For $A = a,b,c,d,e$, we get $n=4$ and, for example, the following encoding:
$$
beginarrayc
a & 1100 \
b & 1010 \
c & 1001 \
d & 0110 \
e & 0101
endarray
$$
Reading the columns of the table, $B_1 = a,b,c, B_2 = a,d,e, B_3 = b,d, B_4 = c,e$. Since each element of $A$ appears in the same number of subsets, and no two elements appear in the same subsets, the condition is satisfied.

share|cite|improve this answer

answered May 28 at 17:56

Fabio SomenziFabio Somenzi

6,81121321

$endgroup$

add a comment | 

$begingroup$

An improved upper bound is given by the smallest $n$ such that

$$ binomnlfloor n/2 rfloor geq |A| enspace. $$

For $A = a,b,c,d,e$, we get $n=4$ and, for example, the following encoding:
$$
beginarrayc
a & 1100 \
b & 1010 \
c & 1001 \
d & 0110 \
e & 0101
endarray
$$
Reading the columns of the table, $B_1 = a,b,c, B_2 = a,d,e, B_3 = b,d, B_4 = c,e$. Since each element of $A$ appears in the same number of subsets, and no two elements appear in the same subsets, the condition is satisfied.

share|cite|improve this answer

answered May 28 at 17:56

Fabio SomenziFabio Somenzi

6,81121321

$endgroup$

share|cite|improve this answer

answered May 28 at 17:56

Fabio SomenziFabio Somenzi

6,81121321

answered May 28 at 17:56

Fabio SomenziFabio Somenzi

6,81121321

answered May 28 at 17:56

Fabio SomenziFabio Somenzi

6,81121321