More Like this

1. Zeroes of polynomials on definable hypersurfaces: pathologies exist, but they are rare

   https://doi.org/10.1093/qmath/haz022  

   Basu, Saugata; Lerario, Antonio; Natarajan, Abhiram (October 2019, The Quarterly Journal of Mathematics)

   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
2. Short Proof of the Asymptotic Confirmation of the Faudree-Lehel Conjecture

   https://doi.org/10.37236/11413  

   Przybyło, Jakub; Wei, Fan (October 2023, The Electronic Journal of Combinatorics)

   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
3. Interpolation for Curves in Projective Space with Bounded Error

   https://doi.org/10.1093/imrn/rnz136  

   Larson, Eric (July 2019, International Mathematics Research Notices)

   Abstract Given $$n$$ general points $$p_1, p_2, \ldots , p_n \in{\mathbb{P}}^r$$ it is natural to ask whether there is a curve of given degree $$d$$ and genus $$g$$ passing through them; by counting dimensions a natural conjecture is that such a curve exists if and only if $$\begin{equation*}n \leq \left\lfloor \frac{(r + 1)d - (r - 3)(g - 1)}{r - 1}\right\rfloor.\end{equation*}$$The case of curves with nonspecial hyperplane section was recently studied in [2], where the above conjecture was shown to hold with exactly three exceptions. In this paper, we prove a “bounded-error analog” for special linear series on general curves; more precisely we show that existence of such a curve subject to the stronger inequality $$\begin{equation*}n \leq \left\lfloor \frac{(r + 1)d - (r - 3)(g - 1)}{r - 1}\right\rfloor - 3.\end{equation*}$$Note that the $-3$ cannot be replaced with $-2$ without introducing exceptions (as a canonical curve in $${\mathbb{P}}^3$$ can only pass through nine general points, while a naive dimension count predicts twelve). We also use the same technique to prove that the twist of the normal bundle $$N_C(-1)$$ satisfies interpolation for curves whose degree is sufficiently large relative to their genus, and deduce from this that the number of general points contained in the hyperplane section of a general curve is at least $$\begin{equation*}\min\left(d, \frac{(r - 1)^2 d - (r - 2)^2 g - (2r^2 - 5r + 12)}{(r - 2)^2}\right).\end{equation*}$$ As explained in [7], these results play a key role in the author’s proof of the maximal rank conjecture [9]. 

   more » « less
4. Irregular subgraphs

   https://doi.org/10.1017/S0963548322000220  

   Alon, Noga; Wei, Fan (March 2023, Combinatorics, Probability and Computing)

   Abstract We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any $$d$$ -regular graph on $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ deviates from $$\frac{n}{d+1}$$ by at most $$2$$ . The second is that every graph on $$n$$ vertices with minimum degree $$\delta$$ contains a spanning subgraph in which the number of vertices of each degree does not exceed $$\frac{n}{\delta +1}+2$$ . Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices $$n$$ . In particular we show that if $$d^3 \log n \leq o(n)$$ then every $$d$$ -regular graph with $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ is $$(1+o(1))\frac{n}{d+1}$$ . We also prove that any graph with $$n$$ vertices and minimum degree $$\delta$$ contains a spanning subgraph in which no degree is repeated more than $$(1+o(1))\frac{n}{\delta +1}+2$$ times. 

   more » « less
5. On the edit distance function of the random graph

   https://doi.org/10.1017/S0963548321000353  

   Martin, Ryan R.; Riasanovsky, Alex W. (March 2022, Combinatorics, Probability and Computing)

   Abstract Given a hereditary property of graphs $$\mathcal{H}$$ and a $$p\in [0,1]$$ , the edit distance function $$\textrm{ed}_{\mathcal{H}}(p)$$ is asymptotically the maximum proportion of edge additions plus edge deletions applied to a graph of edge density p sufficient to ensure that the resulting graph satisfies $$\mathcal{H}$$ . The edit distance function is directly related to other well-studied quantities such as the speed function for $$\mathcal{H}$$ and the $$\mathcal{H}$$ -chromatic number of a random graph. Let $$\mathcal{H}$$ be the property of forbidding an Erdős–Rényi random graph $$F\sim \mathbb{G}(n_0,p_0)$$ , and let $$\varphi$$ represent the golden ratio. In this paper, we show that if $$p_0\in [1-1/\varphi,1/\varphi]$$ , then a.a.s. as $$n_0\to\infty$$ , \begin{align*} {\textrm{ed}}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $$p\in [1/3,2/3]$$ for any $$p_0\in (0,1)$$ . A primary tool in the proof is the categorization of p -core coloured regularity graphs in the range $$p\in[1-1/\varphi,1/\varphi]$$ . Such coloured regularity graphs must have the property that the non-grey edges form vertex-disjoint cliques. 

   more » « less