3
$\begingroup$

Let $M$ be a $n\times n$ triangular matrix, that entries are $0$ and $1$ , and such that diagonal entries are $1$.

A row or a column will be said to be small, if its number of $1$s is at most $(n+1)/2$. A row will be said to be 2-irreducible if it is not the conjunction of exactly two other rows. (The row $(a_1,a_2...,a_n)$ is the conjunction of the rows $(b_1,...,b_n) $ and $(c_1,...,c_n)$ iff $a_i=b_i.c_i$ for all non zero positive integer $i\leq n$).

Let's now suppose that every column is small in our matrix $M$

is there a row of $M$ that is small and 2-irreducible?

Note that if we ask $M$ to be the matrix of a lattice, then the question is equivalent to the Frankl conjecture. Note also that if one can disprove the new conjecture, there is still an intermediary question by asking $M$ to be the matrix of a (finite) partial order. In a lattice $2$-irreducible and irreducible is the same notion, but in a general partial order, not being the upper bound of two distinct members is different from not being the upper bound of some subset. Indeed if we ask the same thing for "irreducible" but not 2- irreducible, one can easily build a counterexample with $M$ matrix of some partial order

$\endgroup$
2
  • 1
    $\begingroup$ Since a positive answer to your question would imply the Frankl conjecture, one would expect the answer to your question to be negative in general. Is a negative answer to your general question still of interest? If not, are you merely asking someone to come along with a solution to the Frankl conjecture? $\endgroup$
    – Yemon Choi
    Nov 13, 2018 at 0:45
  • $\begingroup$ I made quite a long post and I did not want to make it heavier by saying : "of course I don't expect a positive answer" but it seems to me that if the question is not aswered (by the negative) after a lot if work, then it should deserve to be a new more general conjecture. And then, long reserches might give indication to solve the Frankl conjecture (FC). I would not dare to say that it would then be the "real point" of FC, because it would sound ridiculous if it's wrong, but my goal would be to give generalizations of FC that are not too easily brokable, as appear to be main such attempts $\endgroup$
    – jcdornano
    Nov 13, 2018 at 14:47

1 Answer 1

4
$\begingroup$

For $n\geq 5$, the answer is always yes: all rows are small (since $M$ is tridiagonal, at most 3 1's can show up in a row) and the first row is always 2-irreducible (the second row is the only other row that can contribute a 1 in the first position).

I don't see the equivalence to the Frankl conjecture - probably $M$ shouldn't be tridiagonal if you want that to be the case? Maybe by tridiagonal you mean something other than $M$ being zero everywhere except for possibly the main diagonal, the one above, and the one below?

$\endgroup$
1
  • 1
    $\begingroup$ no more battery but i will edit tomorrow : I made a translation mistake, i ment a triangular matrix $\endgroup$
    – jcdornano
    Dec 30, 2018 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.