On Sharp Thresholds of Monotone Properties: Bourgain's Proof Revisited

Gunby-He-Narayanan showed that the logarithmic gap predictions of Kahn-Kalai and Talagrand (proved by Park-Pham and Frankston-Kahn-Narayanan-Park) about thresholds of up-sets do not apply to down-sets. In particular, for the down-set of triangle-free graphs, they showed that there is a polynomial gap between the threshold and the factional expectation threshold. In this short note we give a simpler proof of this result, and extend the polynomial threshold gap to down-sets of ...

We will present a new method, which enables us to find threshold functions for many properties in random intersection graphs. This method will be used to establish sharp threshold functions in random intersection graphs for k-connectivity, perfect matching containment and Hamilton cycle containment.

Let $f\colon \{0,1\}^n\to \{0,1\}$ be a monotone Boolean functions, let $\psi_k(f)$ denote the Shapley value of the $k$th variable and $b_k(f)$ denote the Banzhaf value (influence) of the $k$th variable. We prove that if we have $\psi_k(f) \le t$ for all $k$, then the threshold interval of $f$ has length $\displaystyle O \left(\frac {1}{\log (1/t)}\right)$. We also prove that if $f$ is balanced and $b_k(f) \le t$ for every $k$, then $\displaystyle \max_{k} \psi_k(f) \le O\lef...

We survey sufficient degree conditions, for a variety of graph properties, that are best possible in the same sense that Chvatal's well-known degree condition for hamiltonicity is best possible.

Lower bounds on the proof-theoretic strength of the graph minor theorem were found over 30 years ago by Friedman, Robertson and Seymour 1987, but upper bounds have always been elusive. We present recently found upper bounds on the graph minor theorem and other theorems appearing in the Graph Minors series. Further, we give some ideas as to how the lower bounds on some of these theorems might be improved.

Bourgain showed that any noise stable Boolean function $f$ can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's result under the additional assumption that $f$ is a halfspace.

Let $N$ be a finite set, let $p \in (0,1)$, and let $N_p$ denote a random binomial subset of $N$ where every element of $N$ is taken to belong to the subset independently with probability $p$ . This defines a product measure $\mu_p$ on the power set of $N$, where for $\mathcal{A} \subseteq 2^N$ $\mu_p(\mathcal{A}) := Pr[N_p \in \mathcal{A}]$. In this paper we study upward-closed families $\mathcal{A}$ for which all minimal sets in $\mathcal{A}$ have size at most $k$, for so...

A variant of the Bourgain-Gamburd machine without using any girth bounds is obtained. Also, we find series of applications of %our result the Bourgain-Gamburd machine to problems of Additive Combinatorics, Number Theory and Probability.

Boolean networks constitute relevant mathematical models to study the behaviours of genetic and signalling networks. These networks define regulatory influences between molecular nodes, each being associated to a Boolean variable and a regulatory (local) function specifying its dynamical behaviour depending on its regulators. However, existing data is mostly insufficient to adequately parametrise a model, that is to uniquely define a regulatory function for each node. With th...

Park and Pham's recent proof of the Kahn-Kalai conjecture was a major breakthrough in the field of graph and hypergraph thresholds. Their result gives an upper bound on the threshold at which a probabilistic construction has a $1-\epsilon$ chance of achieving a given monotone property. While their bound in other parameters is optimal up to constant factors for any fixed $\epsilon$, it does not have the optimal dependence on $\epsilon$ as $\epsilon\rightarrow 0$. In this short...