An official website of the United States government
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
Sparse analytic systems
Abstract Erdős [7] proved that the Continuum Hypothesis (CH) is equivalent to the existence of an uncountable family $$\mathcal {F}$$ of (real or complex) analytic functions, such that $$\big \{ f(x) \ : \ f \in \mathcal {F} \big \}$$ is countable for every x . We strengthen Erdős’ result by proving that CH is equivalent to the existence of what we call sparse analytic systems of functions. We use such systems to construct, assuming CH, an equivalence relation $$\sim $$ on $$\mathbb {R}$$ such that any ‘analytic-anonymous’ attempt to predict the map $$x \mapsto [x]_\sim $$ must fail almost everywhere. This provides a consistently negative answer to a question of Bajpai-Velleman [2].
more »
« less
- Award ID(s):
- 2154141
- PAR ID:
- 10440950
- Date Published:
- Journal Name:
- Forum of Mathematics, Sigma
- Volume:
- 11
- ISSN:
- 2050-5094
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In this paper we prove a result on the effective generation of pluri-canonical linear systems on foliated surfaces of general type. Fix a function {P:\mathbb{Z}_{\geq 0}\to\mathbb{Z}} , then there exists an integer {N>0} such that if {(X,{\mathcal{F}})} is a canonical or nef model of a foliation of general type with Hilbert polynomial {\chi(X,{\mathcal{O}}_{X}(mK_{\mathcal{F}}))=P(m)} for all {m\in\mathbb{Z}_{\geq 0}} , then {|mK_{\mathcal{F}}|} defines a birational map for all {m\geq N} . On the way, we also prove a Grauert–Riemenschneider-type vanishing theorem for foliated surfaces with canonical singularities.more » « less
-
Abstract We prove an inequality between the conductor and the discriminant for all hyperelliptic curves defined over discretely valued fields $$K$$ with perfect residue field of characteristic not $$2$$. Specifically, if such a curve is given by $$y^{2} = f(x)$$ with $$f(x) \in \mathcal{O}_{K}[x]$$, and if $$\mathcal{X}$$ is its minimal regular model over $$\mathcal{O}_{K}$$, then the negative of the Artin conductor of $$\mathcal{X}$$ (and thus also the number of irreducible components of the special fiber of $$\mathcal{X}$$) is bounded above by the valuation of $$\operatorname{disc}(f)$$. There are no restrictions on genus of the curve or on the ramification of the splitting field of $$f$$. This generalizes earlier work of Ogg, Saito, Liu, and the second author.more » « less
-
Abstract A subset E of a metric space X is said to be starlike-equivalent if it has a neighbourhood which is mapped homeomorphically into $$\mathbb{R}^n$$ for some n , sending E to a starlike set. A subset $$E\subset X$$ is said to be recursively starlike-equivalent if it can be expressed as a finite nested union of closed subsets $$\{E_i\}_{i=0}^{N+1}$$ such that $$E_{i}/E_{i+1}\subset X/E_{i+1}$$ is starlike-equivalent for each i and $$E_{N+1}$$ is a point. A decomposition $$\mathcal{D}$$ of a metric space X is said to be recursively starlike-equivalent, if there exists $$N\geq 0$$ such that each element of $$\mathcal{D}$$ is recursively starlike-equivalent of filtration length N . We prove that any null, recursively starlike-equivalent decomposition $$\mathcal{D}$$ of a compact metric space X shrinks, that is, the quotient map $$X\to X/\mathcal{D}$$ is the limit of a sequence of homeomorphisms. This is a strong generalisation of results of Denman–Starbird and Freedman and is applicable to the proof of Freedman’s celebrated disc embedding theorem. The latter leads to a multitude of foundational results for topological 4-manifolds, including the four-dimensional Poincaré conjecture.more » « less
-
Abstract The classical Banach space $$L_1(L_p)$$ consists of measurable scalar functions f on the unit square for which $$ \begin{align*}\|f\| = \int_0^1\Big(\int_0^1 |f(x,y)|^p dy\Big)^{1/p}dx < \infty.\end{align*} $$ We show that $$L_1(L_p) (1 < p < \infty )$$ is primary, meaning that whenever $$L_1(L_p) = E\oplus F$$ , where E and F are closed subspaces of $$L_1(L_p)$$ , then either E or F is isomorphic to $$L_1(L_p)$$ . More generally, we show that $$L_1(X)$$ is primary for a large class of rearrangement-invariant Banach function spaces.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/fms.2023.54
