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

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

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

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

CC BY-SA 3.0
2014-04-19T08:16:38.707Z
Why do you want to "prove or disprove" this ?
Suresh Venkat
CC BY-SA 3.0
2014-04-19T13:25:21.523Z
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.
Raghav Kulkarni
CC BY-SA 3.0
2014-04-19T17:29:10.260Z
Ah ok. that makes sense. I asked because the question as phrased lacked motivation, but your clarification is helpful.
Suresh Venkat
<ds.algorithms><co.combinatorics>
Upper bound on Euler characteristic of downward closed family
Raghav Kulkarni
# Upper bound on Euler characteristic of downward closed family

(Asked by: username_0 on 2014-04-19)

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

**Tags:** ds.algorithms, co.combinatorics

> **Comments:**
> **username_1**: Why do you want to "prove or disprove" this ?  
> **username_0**: 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.  
> **username_1**: Ah ok. that makes sense. I asked because the question as phrased lacked motivation, but your clarification is helpful.  

---

## 0 answers

