(Definition: $\mathcal{F}$ is called downward closed if for any $A \in \mathcal{F}$ and $B \subseteq A$ it holds that $B \in \mathcal{F}.$)

Let $\mathcal{F}$ be a downward closed family of subsets of $\{1, ..., n\}$ generated by $m$ sets. Let $\chi(\mathcal{F})$ := number of odd cardinality members of $\mathcal{F}$ minus the number of even cardinality members of $\mathcal{F}.$ Prove or disprove: $|\chi(\mathcal{F})| \leq m^{O(\log n)}.$

MathOverflow Link: https://mathoverflow.net/questions/161471/is-euler-characteristic-of-a-simplicial-complex-on-n-vertices-and-f-facets-a?lq=1

As a side question, I am also curious about how easy/hard it is to compute/approximate $|\chi(\mathcal{F})|$ given $n$ and the $m$ generators of $\mathcal{F}.$

  • 2
    $\begingroup$ Why do you want to "prove or disprove" this ? $\endgroup$ Apr 19, 2014 at 8:16
  • 4
    $\begingroup$ Oh! I just stated it that way "prove or disprove" because although I would like this bound to be true I have no intuition yet about whether or not the bound holds. If it holds true then I have an application of this in mind which broadly speaking in a round-about chain of reductions proves some sort of lower bound for decision tree complexity. $\endgroup$ Apr 19, 2014 at 13:25
  • $\begingroup$ Ah ok. that makes sense. I asked because the question as phrased lacked motivation, but your clarification is helpful. $\endgroup$ Apr 19, 2014 at 17:29


Your Answer

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

Browse other questions tagged or ask your own question.