# Upper bound on Euler characteristic of downward closed family

(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)}.$

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}.$

• Why do you want to "prove or disprove" this ? Apr 19, 2014 at 8:16
• 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. Apr 19, 2014 at 13:25
• Ah ok. that makes sense. I asked because the question as phrased lacked motivation, but your clarification is helpful. Apr 19, 2014 at 17:29