Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHypercontractivity for global functions and sharp thresholds
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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, Friedguts junta theorem and the invariance principle of Mossel, ODonnell 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 thresholds, to also obtain such results for general $p$-biased measures. However, simple examples show that when $p$ is small there is no hypercontractive inequality that is strong enough for such applications. In this paper, we establish an effective hypercontractivity inequality for general $p$ that applies to `global functions, i.e. functions that are not significantly affected by a restriction of a small set of coordinates. This class of functions appears naturally, e.g. in Bourgains sharp threshold theorem, which states that such functions exhibit a sharp threshold. We demonstrate the power of our tool by strengthening Bourgains theorem, thereby making progress on a conjecture of Kahn and Kalai. An additional application of our hypercontractivity theorem, is a $p$-biased analog of the seminal invariance principle of Mossel, ODonnell, and Oleszkiewicz. In a companion paper, we give applications to the solution of two open problems in Extremal Combinatorics.
rate research
Read More
The hypercontractive inequality on the discrete cube plays a crucial role in many fundamental results in the Analysis of Boolean functions, such as the KKL theorem, Friedguts junta theorem and the invariance principle. In these results the cube is equipped with the uniform measure, but it is desirable, particularly for applications to the theory of sharp thresholds, to also obtain such results for general $p$-biased measures. However, simple examples show that when $p = o(1)$, there is no hypercontractive inequality that is strong enough. In this paper, we establish an effective hypercontractive inequality for general $p$ that applies to `global functions, i.e. functions that are not significantly affected by a restriction of a small set of coordinates. This class of functions appears naturally, e.g. in Bourgains sharp threshold theorem, which states that such functions exhibit a sharp threshold. We demonstrate the power of our tool by strengthening Bourgains theorem, thereby making progress on a conjecture of Kahn and Kalai and by establishing a $p$-biased analog of the invariance principle. Our results have significant applications in Extremal Combinatorics. Here we obtain new results on the Turan number of any bounded degree uniform hypergraph obtained as the expansion of a hypergraph of bounded uniformity. These are asymptotically sharp over an essentially optimal regime for both the uniformity and the number of edges and solve a number of open problems in the area. In particular, we give general conditions under which the crosscut parameter asymptotically determines the Turan number, answering a question of Mubayi and Verstraete. We also apply the Junta Method to refine our asymptotic results and obtain several exact results, including proofs of the Huang--Loh--Sudakov conjecture on cross matchings and the Furedi--Jiang--Seiver conjecture on path expansions.
If $G$ is a graph and $vec H$ is an oriented graph, we write $Gto vec H$ to say that every orientation of the edges of $G$ contains $vec H$ as a subdigraph. We consider the case in which $G=G(n,p)$, the binomial random graph. We determine the threshold $p_{vec H}=p_{vec H}(n)$ for the property $G(n,p)to vec H$ for the cases in which $vec H$ is an acyclic orientation of a complete graph or of a cycle.
We study community detection in the contextual stochastic block model arXiv:1807.09596 [cs.SI], arXiv:1607.02675 [stat.ME]. In arXiv:1807.09596 [cs.SI], the second author studied this problem in the setting of sparse graphs with high-dimensional node-covariates. Using the non-rigorous cavity method from statistical physics, they conjectured the sharp limits for community detection in this setting. Further, the information theoretic threshold was verified, assuming that the average degree of the observed graph is large. It is expected that the conjecture holds as soon as the average degree exceeds one, so that the graph has a giant component. We establish this conjecture, and characterize the sharp threshold for detection and weak recovery.
For a real constant $alpha$, let $pi_3^alpha(G)$ be the minimum of twice the number of $K_2$s plus $alpha$ times the number of $K_3$s over all edge decompositions of $G$ into copies of $K_2$ and $K_3$, where $K_r$ denotes the complete graph on $r$ vertices. Let $pi_3^alpha(n)$ be the maximum of $pi_3^alpha(G)$ over all graphs $G$ with $n$ vertices. The extremal function $pi_3^3(n)$ was first studied by GyH{o}ri and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320]. In a recent progress on this problem, Kral, Lidicky, Martins and Pehova [Decomposing graphs into edges and triangles, Combin. Prob. Comput. 28 (2019) 465--472] proved via flag algebras that $pi_3^3(n)le (1/2+o(1))n^2$. We extend their result by determining the exact value of $pi_3^alpha(n)$ and the set of extremal graphs for all $alpha$ and sufficiently large $n$. In particular, we show for $alpha=3$ that $K_n$ and the complete bipartite graph $K_{lfloor n/2rfloor,lceil n/2rceil}$ are the only possible extremal examples for large $n$.
We had shown earlier that for a standard graded ring $R$ and a graded ideal $I$ in characteristic $p>0$, with $ell(R/I) <infty$, there exists a compactly supported continuous function $f_{R, I}$ whose Riemann integral is the HK multiplicity $e_{HK}(R, I)$. We explore further some other invariants, namely the shape of the graph of $f_{R, {bf m}}$ (where ${bf m}$ is the graded maximal ideal of $R$) and the maximum support (denoted as $alpha(R,I)$) of $f_{R, I}$. In case $R$ is a domain of dimension $dgeq 2$, we prove that $(R, {bf m})$ is a regular ring if and only if $f_{R, {bf m}}$ has a symmetry $f_{R, {bf m}}(x) = f_{R, {bf m}}(d-x)$, for all $x$. If $R$ is strongly $F$-regular on the punctured spectrum then we prove that the $F$-threshold $c^I({bf m})$ coincides with $alpha(R,I)$. As a consequence, if $R$ is a two dimensional domain and $I$ is generated by homogeneous elements of the same degree, thene have (1) a formula for the $F$-threshold $c^I({bf m})$ in terms of the minimum strong Harder-Narasimahan slope of the syzygy bundle and (2) a well defined notion of the $F$-threshold $c^I({bf m})$ in characteristic $0$. This characterisation readily computes $c^{I(n)}({bf m})$, for the set of all irreducible plane trinomials $k[x,y,z]/(h)$, where ${bf m} = (x,y,z)$ and $I(n) = (x^n, y^n, z^n)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
