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

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the smallest number of edge deletions that are needed in order to turn G into a graph satisfying P. We denote this quantity by E_P(G). Our first result states that for any monotone graph property P, any \epsilon >0 and n-vertex input graph G one can approximate E_P(G) up to an addi...

We present a new structural (or syntatic) approach for estimating the satisfiability threshold of random 3-SAT formulae. We show its efficiency in obtaining a jump from the previous upper bounds, lowering them to 4.506. The method combines well with other techniques, and also applies to other problems, such as the 3-colourability of random graphs.

We consider the regular balanced model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad, Dubois, Interian, and Selman. We say that a formula is $p$-satisfying if there is a truth assignment satisfying $1-2^{-k}+p 2^{-k}$ fraction of clauses. Using the first moment method we determine upper bound on the threshold clause density such that there are no $p$-satisfying assignments with high probability above this upper bound. There are two aspects in d...

The classical hypercontractive inequality for the noise operator on the discrete cube plays a crucial role in many of the fundamental results in the Analysis of Boolean functions, such as the KKL (Kahn-Kalai-Linial) theorem, Friedgut's junta theorem and the invariance principle of Mossel, O'Donnell and Oleszkiewicz. In these results the cube is equipped with the uniform ($1/2$-biased) measure, but it is desirable, particularly for applications to the theory of sharp threshold...

In this paper, we show that there exists a balanced linear threshold function (LTF) which is unique games hard to approximate, refuting a conjecture of Austrin, Benabbas, and Magen. We also show that the almost monarchy predicate on k variables is approximable for sufficiently large k.

In this note, we present a simple non-directed graph proof of Sharkovsky's theorem which is different from the one given in [2].

We prove that Sherali-Adams with polynomially bounded coefficients requires proofs of size $n^{\Omega(d)}$ to rule out the existence of an $n^{\Theta(1)}$-clique in Erd\H{o}s-R\'{e}nyi random graphs whose maximum clique is of size $d\leq 2\log n$. This lower bound is tight up to the multiplicative constant in the exponent. We obtain this result by introducing a technique inspired by pseudo-calibration which may be of independent interest. The technique involves defining a mea...

We consider the graph dynamical systems known as k-reversible processes. In such processes, each vertex in the graph has one of two possible states at each discrete time step. Each vertex changes its state between the current time and the next if and only if it currently has at least k neighbors in a state different than its own. For such processes, we present a monotonic function similar to the decreasing energy functions used to study threshold networks. Using this new func...

A graph property is a function $\Phi$ that maps every graph to {0, 1} and is invariant under isomorphism. In the $\#IndSub(\Phi)$ problem, given a graph $G$ and an integer $k$, the task is to count the number of $k$-vertex induced subgraphs $G'$ with $\Phi(G')=1$. $\#IndSub(\Phi)$ can be naturally generalized to graph parameters, that is, to functions $\Phi$ on graphs that do not necessarily map to {0, 1}: now the task is to compute the sum $\sum_{G'} \Phi(G')$ taken over all...

We study the parameterized complexity of #IndSub($\Phi$), where given a graph $G$ and an integer $k$, the task is to count the number of induced subgraphs on $k$ vertices that satisfy the graph property $\Phi$. Focke and Roth [STOC 2022] completely characterized the complexity for each $\Phi$ that is a hereditary property (that is, closed under vertex deletions): #IndSub($\Phi$) is #W[1]-hard except in the degenerate cases when every graph satisfies $\Phi$ or only finitely ma...