5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Why do you want to "prove or disprove" this ? $\endgroup$
    – Suresh Venkat
    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$
    – Raghav Kulkarni
    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$
    – Suresh Venkat
    Apr 19, 2014 at 17:29

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.