2
$\begingroup$

I have been reading the paper 'Improved Bounds for the Sunflower Lemma' (Ann. of Math., Vol. 194(3), pp. 795-815), and have not managed to understand the following:

  1. I would like a formalization for what a $p$-biased distribution (pg. 796) is, since $R$ is treated both as a set and a random-variable in Definition 1.5 (pg. 796) and I am not certain how this is done.
    What I have tried: Consider the measure space $(X, \mathcal{P}(X), \mathbb{P})$ and the measurable space $(X, \mathcal{P}(X))$. We define the random-variable $\mathcal{R}: X \to X$ such that $\mathcal{R}: t \mapsto t$, and the probability-measure $\mathbb{P}: \mathcal{P}(X) \to [0, \infty]$, such that $\forall \, t \in X: \mathbb{P}(\{t\}) = p$, and $\forall \, S \subseteq X:$ $\mathbb{P}(S) := \prod_{s \in S} \mathbb{P}(\{s\}).$ Then, the distribution function is as follows- $\forall \, A \in \mathcal{P}(X):$ $$\mathbb{P}^{X}(A) = \mathbb{P}(\{w \in X: \mathcal{R}(w) \in A\}) = \mathbb{P}(A).$$ Is this indeed the formal definition of a $p$-biased distribution? If so, what does Definition 1.5 mean (, since $R$ is considered both as a r.v. and a set in the definition)? If not, what is a $p$-biased distribution formally?

  2. Assuming a heuristic understanding of $U(X,p)$ as being as stated by the authors on pg. 796 before Definition 1.5, we consider Lemma 1.6. On pg. 797, the paper claims that by 'the union bound', we have that $$\textrm{Pr} \: [\forall \, i \in [r], \, \exists \, S \in \mathcal{F}: S \subseteq Y_{i}] > 0$$, where $Y_{i}$ is the set of all points in $X$ coloured with colour $i$. I am not able to follow this, since I am not able to say anything non-trivial about $\textrm{Pr} (\cup_{i \in [r]} \varepsilon_{i})$.

  3. When the authors define the weight function $\sigma$ on pg. 799, they restrict its domain to $\mathcal{F}$, but on pg. 800, they refer to $\sigma(\mathcal{F}_T)$, which doesn't make sense to me, since it doesn't appear that $\forall \, T \subseteq X, \, T \neq \emptyset: \mathcal{F}_T \subset \mathcal{F}.$ Therefore, I was wondering if we require that the domain of $\sigma$ be $\mathcal{P}(X)$ instead.

  4. On pg. 800, after Definition 2.1, the authors state that if $(\mathcal{F},\sigma)$ is s-spread, where $s= (s_{0}; s_{1}, \dots, s_{w})$ is a weight-profile, in particular, $\mathcal{F}$ is a $w$-set-system. What I am able to show is that if indeed $\mathcal{F}$ contains a set $S$ with $|S| > w$, then, we have $$\forall R \in \mathcal{F}, S \subset R: \sigma (R \, \backslash \, S) = 0.$$ What I thought I could try showing was that $\sigma$ would be $0$ everywhere, which is not allowed, by definition of a weight function on pg. 799.

Any help on any or all of these questions is appreciated.

$\endgroup$
0

1 Answer 1

7
$\begingroup$
  1. The random variable $R$ here takes values in the power set ${\mathcal P}(X)$ of $X$, not in $X$: it's a random set in $X$, not a random point. For the purposes of this argument, the only important features of $R$ are that the events $(x \in R)$ for each $x \in X$ are independent events of probability $p$. But if you really wanted to formally model this random variable by a measurable map on a probability space as you attempted to do above, one could do so by taking the probability space $({\mathcal P}(X), {\mathcal P}({\mathcal P}(X)), {\mathbb P})$ with the probablity measure $$ {\mathbb P}(\{R_0\}) = p^{\# R_0} (1-p)^{\# (X \backslash R_0)}$$ for all $R_0 \subset X$ (i.e., $R_0 \in {\mathcal P}(X))$), and take $R: {\mathcal P}(X) \to {\mathcal P}(X)$ to be the identity map $R: R_0 \mapsto R_0$. However, the precise probability space model for this random set $R$ is not of particular relevance; see this post of mine for some further discussion.

  2. Once one can prove that ${\mathbb P}(E_i) > 1-1/r$ for all $i=1,\dots,r$, the union bound (applied to the complements of $E_i$) shows that ${\mathbb P}(\bigwedge_{i=1}^r E_i) > 0$, thus the $E_i$ simultaneously hold with positive probability.

  3. Presumably this will become clearer at the later stages of the argument where the quantity $\sigma({\mathcal F}_T)$ is actually used, but I would guess that here the authors are implicitly abusing notation by identifying the link ${\mathcal F}_T = \{ S \backslash T: S \in {\mathcal F}, T \subset S \}$ with the associated subset $\{ S: S \in {\mathcal F}, T \subset S \}$ of ${\mathcal F}$ for the purpose of computing weights.

  4. Apply Definition 2.1(ii) with $T$ replaced by your set $S$ with $|S| > w$ and with the conventions indicated in my response to item 3.

More generally, you might like to look at my general advice on how to read mathematical papers (in particular how to resolve issues like 3, 4 that are often coming from some typo or implicit convention on the author's part).

$\endgroup$

Your Answer

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