An official website of the United States government
Abstract Given a sequence $$\{Z_d\}_{d\in \mathbb{N}}$$ of smooth and compact hypersurfaces in $${\mathbb{R}}^{n-1}$$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$ such that each manifold $$Z_d$$ is diffeomorphic to a component of the zero set on $$\Gamma$$ of some polynomial of degree $$d$$. (This is in sharp contrast with the case when $$\Gamma$$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $$p$$ on $$\Gamma$$ is bounded by a polynomial in $$\deg (p)$$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$$ containing a subset $$D$$ homeomorphic to a disk, and a family of polynomials $$\{p_m\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that $$(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$$ i.e. the zero set of $$p_m$$ in $$D$$ is isotopic to $$Z_{d_m}$$ in $${\mathbb{R}}^{n-1}$$. This says that, up to extracting subsequences, the intersection of $$\Gamma$$ with a hypersurface of degree $$d$$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $$0 \leq k \leq n-2$$ and every sequence of natural numbers $$a=\{a_d\}_{d\in \mathbb{N}}$$ there is a regular, compact semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$, a subsequence $$\{a_{d_m}\}_{m\in \mathbb{N}}$$ and homogeneous polynomials $$\{p_{m}\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $$b_k$$ denotes the $$k$$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $$\Gamma$$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $$d$$, of the set $$\Sigma _{d_m,a, \Gamma }$$ of polynomials verifying (0.1) is positive, but there exists a constant $$c_\Gamma$$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n-1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $$a$$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $$\Gamma$$, for most polynomials a Bézout-type bound holds for the intersection $$\Gamma \cap Z(p)$$: for every $$0\leq k\leq n-2$$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n-1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n-1}{2}}}.\end{equation*}$$
more »
« less
Additive Energies on Discrete Cubes
We prove that for $$d\geq 0$$ and $$k\geq 2$$, for any subset $$A$$ of a discrete cube $$\{0,1\}^d$$, the $k-$higher energy of $$A$$ (i.e., the number of $2k-$tuples $$(a_1,a_2,\dots,a_{2k})$$ in $$A^{2k}$$ with $$a_1-a_2=a_3-a_4=\dots=a_{2k-1}-a_{2k}$$) is at most $$|A|^{\log_{2}(2^k+2)}$$, and $$\log_{2}(2^k+2)$$ is the best possible exponent. We also show that if $$d\geq 0$$ and $$2\leq k\leq 10$$, for any subset $$A$$ of a discrete cube $$\{0,1\}^d$$, the $k-$additive energy of $$A$$ (i.e., the number of $2k-$tuples $$(a_1,a_2,\dots,a_{2k})$$ in $$A^{2k}$$ with $$a_1+a_2+\dots+a_k=a_{k+1}+a_{k+2}+\dots+a_{2k}$$) is at most $$|A|^{\log_2{ \binom{2k}{k}}}$$, and $$\log_2{ \binom{2k}{k}}$$ is the best possible exponent. We discuss the analogous problems for the sets $$\{0,1,\dots,n\}^d$$ for $$n\geq2$$.
more »
« less
- PAR ID:
- 10504628
- Editor(s):
- Gowers, Tim
- Publisher / Repository:
- Scholastica
- Date Published:
- Journal Name:
- Discrete analysis
- ISSN:
- 2397-3129
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Given a simple graph $$G$$, the irregularity strength of $$G$$, denoted $s(G)$, is the least positive integer $$k$$ such that there is a weight assignment on edges $$f: E(G) \to \{1,2,\dots, k\}$$ for which each vertex weight $$f^V(v):= \sum_{u: \{u,v\}\in E(G)} f(\{u,v\})$$ is unique amongst all $$v\in V(G)$$. In 1987, Faudree and Lehel conjectured that there is a constant $$c$$ such that $$s(G) \leq n/d + c$$ for all $$d$$-regular graphs $$G$$ on $$n$$ vertices with $d>1$, whereas it is trivial that $$s(G) \geq n/d$$. In this short note we prove that the Faudree-Lehel Conjecture holds when $$d \geq n^{0.8+\epsilon}$$ for any fixed $$\epsilon >0$$, with a small additive constant $c=28$ for $$n$$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $$\beta\in(0,1/4)$$ there is a constant $$C$$ such that for all $$d$$-regular graphs $$G$$, $$s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28$$, extending and improving a recent result of Przybyło that $$s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})$$ whenever $$d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]$$ and $$n$$ is large enough.more » « less
-
The Bollobás set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for $$n \geqslant k \geqslant t \geqslant 2$$, we consider a collection of $$k$$ families $$\mathcal{A}_i: 1 \leq i \leqslant k$$ where $$\mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \}$$ so that $$A_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \varnothing$$ if and only if there are at least $$t$$ distinct indices $$i_1,i_2,\dots,i_k$$. Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size $$\beta_{k,t}(n)$$ of the families with ground set $[n]$.more » « less
-
Abstract Singmaster’s conjecture asserts that every natural number greater than one occurs at most a bounded number of times in Pascal’s triangle; that is, for any natural number $$t \geq 2$$, the number of solutions to the equation $$\binom{n}{m} = t$$ for natural numbers $$1 \leq m \lt n$$ is bounded. In this paper we establish this result in the interior region $$\exp(\log^{2/3+\varepsilon} n) \leq m \leq n - \exp(\log^{2/3+\varepsilon} n)$$ for any fixed ɛ > 0. Indeed, when t is sufficiently large depending on ɛ, we show that there are at most four solutions (or at most two in either half of Pascal’s triangle) in this region. We also establish analogous results for the equation $$(n)_m = t$$, where $$(n)_m := n(n-1) \dots (n-m+1)$$ denotes the falling factorial.more » « less
-
null (Ed.)Boolean functions play an important role in many different areas of computer science. The _local sensitivity_ of a Boolean function $$f:\{0,1\}^n\to \{0,1\}$$ on an input $$x\in\{0,1\}^n$$ is the number of coordinates whose flip changes the value of $f(x)$, i.e., the number of i's such that $$f(x)\not=f(x+e_i)$$, where $$e_i$$ is the $$i$$-th unit vector. The _sensitivity_ of a Boolean function is its maximum local sensitivity. In other words, the sensitivity measures the robustness of a Boolean function with respect to a perturbation of its input. Another notion that measures the robustness is block sensitivity. The _local block sensitivity_ of a Boolean function $$f:\{0,1\}^n\to \{0,1\}$ on an input $$x\in\{0,1\}^n$$ is the number of disjoint subsets $$I$$ of $$\{1,..,n\}$$ such that flipping the coordinates indexed by $$I$$ changes the value of $f(x)$$, and the _block sensitivity_ of $$f$$ is its maximum local block sensitivity. Since the local block sensitivity is at least the local sensitivity for any input $$x$$, the block sensitivity of $$f$$ is at least the sensitivity of $$f$$.The next example demonstrates that the block sensitivity of a Boolean function is not linearly bounded by its sensitivity. Fix an integer $$k\ge 2$$ and define a Boolean function $$f:\{0,1\}^{2k^2}\to\{0,1\}$$ as follows: the coordinates of $$x\in\{0,1\}^{2k^2}$$ are split into $$k$$ blocks of size $2k$ each and $f(x)=1$ if and only if at least one of the blocks contains exactly two entries equal to one and these entries are consecutive. While the sensitivity of the function $$f$$ is $2k$, its block sensitivity is $k^2$. The Sensitivity Conjecture, made by Nisan and Szegedy in 1992, asserts that the block sensitivity of a Boolean function is polynomially bounded by its sensivity. The example above shows that the degree of such a polynomial must be at least two.The Sensitivity Conjecture has been recently proven by Huang in [Annals of Mathematics 190 (2019), 949-955](https://doi.org/10.4007/annals.2019.190.3.6). He proved the following combinatorial statement that implies the conjecture (with the degree of the polynomial equal to four): any subset of more than half of the vertices of the $$n$$-dimensional cube $$\{0,1\}^n$$ induces a subgraph that contains a vertex with degree at least $$\sqrt{n}$$. The present article extends this result as follows: every Cayley graph with the vertex set $$\{0,1\}^n$$ and any generating set of size $$d$$ (the vertex set is viewed as a vector space over the binary field) satisfies that any subset of more than half of its vertices induces a subgraph that contains a vertex of degree at least $$\sqrt{d}$$. In particular, when the generating set consists of the $$n$$ unit vectors, the Cayley graph is the $$n$$-dimensional hypercube.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
