Return to Question

Let $n=\left\{0,1,...,n-1\right\}$, $n>1$, and $\mathcal F=\left\{F_i\subset n+1,\, i\in n \right\}$ such that, for any $i\in n$,

$i\in F_i\subset i+1,\,\,\,\,\,(*)$

main question :

Does there exists $l\in n$ such that for any $i,j\in n\setminus \left\{l\right\}$, $F_i\cap F_j\ne F_l$, and $|F_l|<n/2$ ?

I'm hoping for a counterexample, and not for demonstration of a "yes" answer because this "yes" implies the Frankl Conjecture. Indeed, if $(G,\leq)=(\left\{G_i,i\in n+1\right\},\leq)$ with $G_n=0_G$ is a lattice and you take as $F_i=\left\{j\in i+1,\, G_j\leq G_i\right\}$, then $\left\{0,F_0,...,F_{n-1}\right\}$ is an intersection closed family (that satisfies the condition $(*)$ up to a fine indexation of elements in $G$. $(\mathcal F,\subset)$ is then a lattice that is isomorphic to $G$. If the answer to the question is "yes", then you will find some meet irréductible $G_i$ with at most $n/2$ lower elements. (The Frankl conjecture is known to be equivalent to the existence of such a $G_i$ in any lattice that cardinality is $n$.)

So the question seems much stronger than Frankl conjecture. So I expect it to "fail", never the less, there is an interesting intermediary question that can be asked if answer to main question is found to be "no".

Question 2

If $(H,\leq)$ is a partial order, does there exists, $h\in H$, such that $h$ is not the greater lower bound of any pair included in $H\setminus\left\{h\right\}$, (let's say that $H$ is then "quasi-irreductible") and such that $|\left\{x\in H, x\leq h\right\}|<|H|/2$.

If $H$ is a lattice, then "quasi-irreductible" and "irreductible" is the same thing.

But answer 2, in the general case, would not be "yes" , if we replace "any pair" by "any subset" :

Take any set $M$ of cardinality $n$ that elements are subset of $4n$ and such that each $m\in M$ has cardinality $3n$ suppose also that the smallest intersection closed set that contain $M$ also contain $S$ the set of singleton of $4n$. (it is not hard to build such a set if $n$ is big enought let's say $n>4$ for example). Now consider $M'=M\cup S$, than each member of $M'$ is a quasi-irreductible and the question 2 is yes in this trivial case, because any element of $S\subset M$' has zero member that are smaller then them, witch is less then $|M'|/2$. But if your definition of $h$ irreductible is "$h$ is not the greater lower bound of some subset of $M'\setminus\left\{h\right\}$" than the irreductible are exactly elements of $M$, each one of them has cardinality $3n$ and then contain $3n$ members of $S\subset M'$, and now... $3n>|M'|/2=(4n+n)/2$.

Let $n=\left\{0,1,...,n-1\right\}$, $n>1$, and $\mathcal F=\left\{F_i\subset n+1,\, i\in n \right\}$ such that, for any $i\in n$,

$i\in F_i\subset i+1,\,\,\,\,\,(*)$

main question :

Does there exists $l\in n$ such that for any $i,j\in n\setminus \left\{l\right\}$, $F_i\cap F_j\ne F_l$, and $|F_l|<n/2+1$ ?

I'm hoping for a counterexample, and not for demonstration of a "yes" answer because this "yes" implies the Frankl Conjecture. Indeed, if $(G,\leq)=(\left\{G_i,i\in n+1\right\},\leq)$ with $G_n=0_G$ is a lattice and you take as $F_i=\left\{j\in i+1,\, G_j\leq G_i\right\}$, then $\left\{0,F_0,...,F_{n-1}\right\}$ is an intersection closed family (that satisfies the condition $(*)$ up to a fine indexation of elements in $G$. $(\mathcal F,\subset)$ is then a lattice that is isomorphic to $G$. If the answer to the question is "yes", then you will find some meet irréductible $G_i$ with at most $n/2$ lower elements. (The Frankl conjecture is known to be equivalent to the existence of such a $G_i$ in any lattice that cardinality is $n$.)

So the question seems much stronger than Frankl conjecture. So I expect it to "fail", never the less, there is an interesting intermediary question that can be asked if answer to main question is found to be "no".

Question 2

If $(H,\leq)$ is a partial order, does there exists, $h\in H$, such that $h$ is not the greater lower bound of any pair included in $H\setminus\left\{h\right\}$, (let's say that $H$ is then "quasi-irreductible") and such that $|\left\{x\in H, x\leq h\right\}|<|H|/2$.

If $H$ is a lattice, then "quasi-irreductible" and "irreductible" is the same thing.

But answer 2, in the general case, would not be "yes" , if we replace "any pair" by "any subset" :

Take any set $M$ of cardinality $n$ that elements are subset of $4n$ and such that each $m\in M$ has cardinality $3n$ suppose also that the smallest intersection closed set that contain $M$ also contain $S$ the set of singleton of $4n$. (it is not hard to build such a set if $n$ is big enought let's say $n>4$ for example). Now consider $M'=M\cup S$, than each member of $M'$ is a quasi-irreductible and the question 2 is yes in this trivial case, because any element of $S\subset M$' has zero member that are smaller then them, witch is less then $|M'|/2$. But if your definition of $h$ irreductible is "$h$ is not the greater lower bound of some subset of $M'\setminus\left\{h\right\}$" than the irreductible are exactly elements of $M$, each one of them has cardinality $3n$ and then contain $3n$ members of $S\subset M'$, and now... $3n>|M'|/2=(4n+n)/2$.

Let $n=\left\{0,1,...,n-1\right\}$, $n>1$, and $\mathcal F=\left\{F_i\subset n+1,\, i\in n \right\}$ such that, for any $i\in n$,

$i\in F_i\subset i+1,\,\,\,\,\,(*)$

main question :

Does there exists $l\in n$ such that for any $i,j\in n\setminus \left\{l\right\}$, $F_i\cap F_j\ne F_l$, and $|F_l|<n/2$ ?

I'm hoping for a counterexample, and not for demonstration of a "yes" answer because this "yes" implies the Frankl Conjecture. Indeed, if $(G,\leq)=(\left\{G_i,i\in n+1\right\},\leq)$ with $G_n=0_G$ is a lattice and you take as $F_i=\left\{j\in i+1,\, G_j\leq G_i\right\}$, then $\left\{0,F_0,...,F_{n-1}\right\}$ is an intersection closed family (that satisfies the condition $(*)$ up to a fine indexation of elements in $G$. $(\mathcal F,\subset)$ is then a lattice that is isomorphic to $G$. If the answer to the question is "yes", then you will find some meet irréductible $G_i$ with at most $n/2$ lower elements. (The Frankl conjecture is known to be equivalent to the existence of such a $G_i$ in any lattice that cardinality is $n$.)

So the question seems much stronger than Frankl conjecture. So I expect it to "fail", never the less, there is an interesting intermediary question that can be asked if answer to main question is found to be "no".

Question 2

If $(H,\leq)$ is a partial order, does there exists, $h\in H$, such that $h$ is not the greater lower bound of any pair included in $H\setminus\left\{h\right\}$, (let's say that $H$ is then "quasi-irreductible") and such that $|\left\{x\in H, x\leq h\right\}|<|H|/2$.

If $H$ is a lattice, then "quasi-irreductible" and "irreductible" is the same thing.

But answer 2, in the general case, would not be "yes" , if we replace "any pair" by "any subset" :

Consider a matrix $(M)$ with 10 columns and 45 distinct rows each containing eight $1$ and two $0$. Add a $45\times 45$ diagonal right bloc $(D)$ with $1$ on the diagonal. Each column of $(P)=(M\,\, D)$ is related to the characteristic fonction of some subsets of $45$, that are elements of our counterexample to question 2, if we had replace "any pair" by "any subset". In the first case any member is quasi-irreductible and then members related to the columns of $D$ have no lower bound for inclusion (then in this case, the answer 2 is yes) , but in the second case, the only members that are not the $\inf$ of any subset of our counterexample are the one related to columns of $(M)$, they have cardinality $45\times 8/10=36$ and then $36>(55+10)/2 $ members included in them. ( $36$ unit sets corresponding to "uni-one" rows of $D$).

Let $n=\left\{0,1,...,n-1\right\}$, $n>1$, and $\mathcal F=\left\{F_i\subset n+1,\, i\in n \right\}$ such that, for any $i\in n$,

$i\in F_i\subset i+1,\,\,\,\,\,(*)$

main question :

Does there exists $l\in n$ such that for any $i,j\in n\setminus \left\{l\right\}$, $F_i\cap F_j\ne F_l$, and $|F_l|<n/2$ ?

I'm hoping for a counterexample, and not for demonstration of a "yes" answer because this "yes" implies the Frankl Conjecture. Indeed, if $(G,\leq)=(\left\{G_i,i\in n+1\right\},\leq)$ with $G_n=0_G$ is a lattice and you take as $F_i=\left\{j\in i+1,\, G_j\leq G_i\right\}$, then $\left\{0,F_0,...,F_{n-1}\right\}$ is an intersection closed family (that satisfies the condition $(*)$ up to a fine indexation of elements in $G$. $(\mathcal F,\subset)$ is then a lattice that is isomorphic to $G$. If the answer to the question is "yes", then you will find some meet irréductible $G_i$ with at most $n/2$ lower elements. (The Frankl conjecture is known to be equivalent to the existence of such a $G_i$ in any lattice that cardinality is $n$.)

So the question seems much stronger than Frankl conjecture. So I expect it to "fail", never the less, there is an interesting intermediary question that can be asked if answer to main question is found to be "no".

Question 2

If $(H,\leq)$ is a partial order, does there exists, $h\in H$, such that $h$ is not the greater lower bound of any pair included in $H\setminus\left\{h\right\}$, (let's say that $H$ is then "quasi-irreductible") and such that $|\left\{x\in H, x\leq h\right\}|<|H|/2$.

If $H$ is a lattice, then "quasi-irreductible" and "irreductible" is the same thing.

But answer 2, in the general case, would not be "yes" , if we replace "any pair" by "any subset" :

Take any set $M$ of cardinality $n$ that elements are subset of $4n$ and such that each $m\in M$ has cardinality $3n$ suppose also that the smallest intersection closed set that contain $M$ also contain $S$ the set of singleton of $4n$. (it is not hard to build such a set if $n$ is big enought let's say $n>4$ for example). Now consider $M'=M\cup S$, than each member of $M'$ is a quasi-irreductible and the question 2 is yes in this trivial case, because any element of $S\subset M$' has zero member that are smaller then them, witch is less then $|M'|/2$. But if your definition of $h$ irreductible is "$h$ is not the greater lower bound of some subset of $M'\setminus\left\{h\right\}$" than the irreductible are exactly elements of $M$, each one of them has cardinality $3n$ and then contain $3n$ members of $S\subset M'$, and now... $3n>|M'|/2=(4n+n)/2$.

Let $n=\left\{0,1,...,n-1\right\}$, $n>1$, and $\mathcal F=\left\{F_i\subset n+1,\, i\in n \right\}$ such that, for any $i\in n$,

$i\in F_i\subset i+1,\,\,\,\,\,(*)$

main question :

Does there exists $l\in n$ such that for any $i,j\in n\setminus \left\{l\right\}$, $F_i\cap F_j\ne F_l$, and $|F_l|<n/2$ ?

I'm hoping for a counterexample, and not for demonstration of a "yes" answer because this "yes" implies the Frankl Conjecture. Indeed, if $(G,\leq)=(\left\{G_i,i\in n+1\right\},\leq)$ with $G_n=0_G$ is a lattice and you take as $F_i=\left\{j\in i+1,\, G_j\leq G_i\right\}$, then $\left\{0,F_0,...,F_{n-1}\right\}$ is an intersection closed family (that satisfies the condition $(*)$ up to a fine indexation of elements in $G$. $(\mathcal F,\subset)$ is then a lattice that is isomorphic to $G$. If the answer to the question is "yes", then you will find some meet irréductible $G_i$ with at most $n/2$ lower elements. (The Frankl conjecture is known to be equivalent to the existence of such a $G_i$ in any lattice that cardinality is $n$.)

So the question seems much stronger than Frankl conjecture. So I expect it to "fail", never the less, there is an interesting intermediary question that can be asked if answer to main question is found to be "no".

Question 2

If $(H,\leq)$ is a partial order, does there exists, $h\in H$, such that $h$ is not the greater lower bound of any pair included in $H\setminus\left\{h\right\}$, (let's say that $H$ is "quasi-irreductible") and such that $|\left\{x\in H, x\leq h\right\}|<|H|/2$.

If $H$ is a lattice, then "quasi-irreductible" and "irreductible" is the same thing.

But answer 2, in the general case, would not be "yes" , if we replace "any pair" by "any subset" :

Consider a matrix $(M)$ with 10 columns and 45 distinct rows each containing eight $1$ and two $0$. Add a $45\times 45$ diagonal right bloc $(D)$ with $1$ on the diagonal. Each column of $(P)=(M\,\, D)$ is related to the characteristic fonction of some subsets of $45$, that are elements of our counterexample to question 2, if we had replace "any pair" by "any subset". In the first case any member is quasi-irreductible and then members related to the columns of $D$ have no lower bound for inclusion (then in this case, the answer 2 is yes) , but in the second case, the only members that are not the $\inf$ of any subset of our counterexample are the one related to columns of $(M)$, they have cardinality $45x8/10=36$ and then $36>(55+10)/2 $ members included in them. ( $36$ unit sets corresponding to "uni-one" rows of $D$).

Let $n=\left\{0,1,...,n-1\right\}$, $n>1$, and $\mathcal F=\left\{F_i\subset n+1,\, i\in n \right\}$ such that, for any $i\in n$,

$i\in F_i\subset i+1,\,\,\,\,\,(*)$

main question :

Does there exists $l\in n$ such that for any $i,j\in n\setminus \left\{l\right\}$, $F_i\cap F_j\ne F_l$, and $|F_l|<n/2$ ?

I'm hoping for a counterexample, and not for demonstration of a "yes" answer because this "yes" implies the Frankl Conjecture. Indeed, if $(G,\leq)=(\left\{G_i,i\in n+1\right\},\leq)$ with $G_n=0_G$ is a lattice and you take as $F_i=\left\{j\in i+1,\, G_j\leq G_i\right\}$, then $\left\{0,F_0,...,F_{n-1}\right\}$ is an intersection closed family (that satisfies the condition $(*)$ up to a fine indexation of elements in $G$. $(\mathcal F,\subset)$ is then a lattice that is isomorphic to $G$. If the answer to the question is "yes", then you will find some meet irréductible $G_i$ with at most $n/2$ lower elements. (The Frankl conjecture is known to be equivalent to the existence of such a $G_i$ in any lattice that cardinality is $n$.)

So the question seems much stronger than Frankl conjecture. So I expect it to "fail", never the less, there is an interesting intermediary question that can be asked if answer to main question is found to be "no".

Question 2

If $(H,\leq)$ is a partial order, does there exists, $h\in H$, such that $h$ is not the greater lower bound of any pair included in $H\setminus\left\{h\right\}$, (let's say that $H$ is then "quasi-irreductible") and such that $|\left\{x\in H, x\leq h\right\}|<|H|/2$.

If $H$ is a lattice, then "quasi-irreductible" and "irreductible" is the same thing.

But answer 2, in the general case, would not be "yes" , if we replace "any pair" by "any subset" :

Consider a matrix $(M)$ with 10 columns and 45 distinct rows each containing eight $1$ and two $0$. Add a $45\times 45$ diagonal right bloc $(D)$ with $1$ on the diagonal. Each column of $(P)=(M\,\, D)$ is related to the characteristic fonction of some subsets of $45$, that are elements of our counterexample to question 2, if we had replace "any pair" by "any subset". In the first case any member is quasi-irreductible and then members related to the columns of $D$ have no lower bound for inclusion (then in this case, the answer 2 is yes) , but in the second case, the only members that are not the $\inf$ of any subset of our counterexample are the one related to columns of $(M)$, they have cardinality $45\times 8/10=36$ and then $36>(55+10)/2 $ members included in them. ( $36$ unit sets corresponding to "uni-one" rows of $D$).