2
$\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 numer of $1$ is at most $(n+1)/2$. A row will be said 2-irreducible if it is not the conjonction of exactly two other rows. (The row $(a_1,a_2...,a_n)$ is the conjonction 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 adjacency matrix of a lattice, then the question is equivalent to the Frankl conjecture. Note also that if one can broke the new conjecture, there is still an intermediary question by asking $M$ to be the adjacency 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$ adjacency matrix of some partial order

$\endgroup$
  • 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 '18 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 '18 at 14:47
  • $\begingroup$ To complete my precedent answer, I think that the answer of the question is no, because as soon as it might be a natural question to anyone that works on FC, I think it would have become a new conjecture if not answered by the negative. But maybe people who asked themself this simple question thought this too, and did not investigate that much in this direction. It does not cost a lot to ask, and that's why I do it. I continue to search for a counterexample and I will post it if I find it : it is never bad to be aware of a bad direction, in order to look somewhere else^^ $\endgroup$ – jcdornano Nov 13 '18 at 15:08
3
$\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$
  • $\begingroup$ tridiagonal (for me) means that everyone us zero above the diagonal. The link to Frankl cinjecture is given by taking M as the adjacency matrix of a lattice. $\endgroup$ – jcdornano Dec 30 '18 at 4:43
  • 1
    $\begingroup$ no more battery but i will edit tomorrow : I made a translation mistake, i ment a triangular matrix $\endgroup$ – jcdornano Dec 30 '18 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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