ID: 1302.1162

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

February 5, 2013

View on ArXiv

Similar papers 2

Sharp threshold functions for the random intersection graph via coupling method?

October 5, 2009

81% Match
Katarzyna Rybarczyk
Combinatorics

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.

Find SimilarView on arXiv

A Survey of Best Monotone Degree Conditions for Graph Properties

May 22, 2014

81% Match
D. Bauer, H. J. Broersma, J. van den Heuvel, N. Kahl, A. Nevo, E. Schmeichel, ... , Yatauro M.
Combinatorics

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.

Find SimilarView on arXiv

Upper bounds on the graph minor theorem

June 30, 2019

80% Match
Martin Krombholz, Michael Rathjen
Logic
Computational Complexity

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.

Find SimilarView on arXiv

On the Distribution of the Fourier Spectrum of Halfspaces

February 29, 2012

80% Match
Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, ... , Wan Andrew
Computational Complexity
Discrete Mathematics
Probability

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.

Find SimilarView on arXiv

Thresholds and expectation-thresholds of monotone properties with small minterms

December 9, 2013

80% Match
Ehud Friedgut, Jeff Kahn, Clara Shikhelman
Combinatorics

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

Find SimilarView on arXiv
Ilya D. Shkredov
Number Theory
Combinatorics

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.

Immediate Neighbours of Monotone Boolean Functions

July 1, 2024

80% Match
José E. R. Cury, Patrícia Tenera Roxo, Vasco Manquinho, ... , Monteiro Pedro T.
Discrete Mathematics
Molecular Networks

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

Find SimilarView on arXiv

On the Typical Structure of Graphs in a Monotone Property

April 9, 2014

80% Match
Svante Janson, Andrew J. Uzzell
Combinatorics

Given a graph property $\mathcal{P}$, it is interesting to determine the typical structure of graphs that satisfy $\mathcal{P}$. In this paper, we consider monotone properties, that is, properties that are closed under taking subgraphs. Using results from the theory of graph limits, we show that if $\mathcal{P}$ is a monotone property and $r$ is the largest integer for which every $r$-colorable graph satisfies $\mathcal{P}$, then almost every graph with $\mathcal{P}$ is close...

Find SimilarView on arXiv

The Park-Pham Theorem with Optimal Convergence Rate

October 7, 2022

80% Match
Tolson Bell
Combinatorics
Discrete Mathematics

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

Find SimilarView on arXiv

A Polynomial Lower Bound for Testing Monotonicity

November 16, 2015

80% Match
Aleksandrs Belovs, Eric Blais
Computational Complexity
Discrete Mathematics
Data Structures and Algorith...

We show that every algorithm for testing $n$-variate Boolean functions for monotonicity must have query complexity $\tilde{\Omega}(n^{1/4})$. All previous lower bounds for this problem were designed for non-adaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only $\Omega(\log n)$. Combined with the query complexity of the non-adaptive monotonicity tester of Khot, Minzer, and Safra (FOCS 2015), our lower ...

Find SimilarView on arXiv