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
Khintchine-type recurrence for 3-point configurations
Abstract The goal of this paper is to generalise, refine and improve results on large intersections from [2, 8]. We show that if G is a countable discrete abelian group and $\varphi , \psi : G \to G$ are homomorphisms, such that at least two of the three subgroups $\varphi (G)$ , $\psi (G)$ and $(\psi -\varphi )(G)$ have finite index in G , then $\{\varphi , \psi \}$ has the large intersections property . That is, for any ergodic measure preserving system $\textbf {X}=(X,\mathcal {X},\mu ,(T_g)_{g\in G})$ , any $A\in \mathcal {X}$ and any $\varepsilon>0$ , the set $$ \begin{align*} \{g\in G : \mu(A\cap T_{\varphi(g)}^{-1} A \cap T_{\psi(g)}^{-1} A)>\mu(A)^3-\varepsilon\} \end{align*} $$ is syndetic (Theorem 1.11). Moreover, in the special case where $\varphi (g)=ag$ and $\psi (g)=bg$ for $a,b\in \mathbb {Z}$ , we show that we only need one of the groups $aG$ , $bG$ or $(b-a)G$ to be of finite index in G (Theorem 1.13), and we show that the property fails, in general, if all three groups are of infinite index (Theorem 1.14). One particularly interesting case is where $G=(\mathbb {Q}_{>0},\cdot )$ and $\varphi (g)=g$ , $\psi (g)=g^2$ , which leads to a multiplicative version of the Khintchine-type recurrence result in [8]. We also completely characterise the pairs of homomorphisms $\varphi ,\psi $ that have the large intersections property when $G = {{\mathbb Z}}^2$ . The proofs of our main results rely on analysis of the structure of the universal characteristic factor for the multiple ergodic averages $$ \begin{align*} \frac{1}{|\Phi_N|} \sum_{g\in \Phi_N}T_{\varphi(g)}f_1\cdot T_{\psi(g)} f_2. \end{align*} $$ In the case where G is finitely generated, the characteristic factor for such averages is the Kronecker factor . In this paper, we study actions of groups that are not necessarily finitely generated, showing, in particular, that, by passing to an extension of $\textbf {X}$ , one can describe the characteristic factor in terms of the Conze–Lesigne factor and the $\sigma $ -algebras of $\varphi (G)$ and $\psi (G)$ invariant functions (Theorem 4.10).
more »
« less
- Award ID(s):
- 1926686
- NSF-PAR ID:
- 10447724
- Date Published:
- Journal Name:
- Forum of Mathematics, Sigma
- Volume:
- 10
- ISSN:
- 2050-5094
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let $X$ be a measure space with a measure-preserving action $(g,x) \mapsto g \cdot x$ of an abelian group $G$. We consider the problem of understanding the structure of measurable tilings $F \odot A = X$ of $X$ by a measurable tile $A \subset X$ translated by a finite set $F \subset G$ of shifts, thus the translates $f \cdot A$, $f \in F$ partition $X$ up to null sets. Adapting arguments from previous literature, we establish a “dilation lemma” that asserts, roughly speaking, that $F \odot A = X$ implies $F^{r} \odot A = X$ for a large family of integer dilations $r$, and use this to establish a structure theorem for such tilings analogous to that established recently by the second and fourth authors. As applications of this theorem, we completely classify those random tilings of finitely generated abelian groups that are “factors of iid”, and show that measurable tilings of a torus ${\mathbb{T}}^{d}$ can always be continuously (in fact linearly) deformed into a tiling with rational shifts, with particularly strong results in the low-dimensional cases $d=1,2$ (in particular resolving a conjecture of Conley, the first author, and Pikhurko in the $d=1$ case).more » « less
-
null (Ed.)Abstract We initiate the study of Schrödinger operators with ergodic potentials defined over circle map dynamics, in particular over circle diffeomorphisms. For analytic circle diffeomorphisms and a set of rotation numbers satisfying Yoccoz’s ${{\mathcal{H}}}$ arithmetic condition, we discuss an extension of Avila’s global theory. We also give an abstract version and a short proof of a sharp Gordon-type theorem on the absence of eigenvalues for general potentials with repetitions. Coupled with the dynamical analysis, we obtain that, for every $C^{1+BV}$ circle diffeomorphism, with a super Liouville rotation number and an invariant measure $\mu $, and for $\mu $-almost all $x\in{{\mathbb{T}}}^1$, the corresponding Schrödinger operator has purely continuous spectrum for every Hölder continuous potential $V$.more » « less
-
Abstract Let M be a complete Riemannian manifold and suppose {p\in M} . For each unit vector {v\in T_{p}M} , the Jacobi operator , {\mathcal{J}_{v}:v^{\perp}\rightarrow v^{\perp}} is the symmetric endomorphism, {\mathcal{J}_{v}(w)=R(w,v)v} . Then p is an isotropic point if there exists a constant {\kappa_{p}\in{\mathbb{R}}} such that {\mathcal{J}_{v}=\kappa_{p}\operatorname{Id}_{v^{\perp}}} for each unit vector {v\in T_{p}M} . If all points are isotropic, then M is said to be isotropic; it is a classical result of Schur that isotropic manifolds of dimension at least 3 have constant sectional curvatures. In this paper we consider almost isotropic manifolds , i.e. manifolds having the property that for each {p\in M} , there exists a constant {\kappa_{p}\in\mathbb{R}} such that the Jacobi operators {\mathcal{J}_{v}} satisfy {\operatorname{rank}({\mathcal{J}_{v}-\kappa_{p}\operatorname{Id}_{v^{\perp}}}% )\leq 1} for each unit vector {v\in T_{p}M} . Our main theorem classifies the almost isotropic simply connected Kähler manifolds, proving that those of dimension {d=2n\geqslant 4} are either isometric to complex projective space or complex hyperbolic space or are totally geodesically foliated by leaves isometric to {{\mathbb{C}}^{n-1}} .more » « less
-
more » « less
Abstract Approximate integer programming is the following: For a given convex body
$$K \subseteq {\mathbb {R}}^n$$ $$K \cap {\mathbb {Z}}^n$$ $$2\cdot (K - c) +c$$ K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time$$2^{O(n)}$$ $$2^{O(n)} \cdot n^n$$ $$x^* \in (K \cap {\mathbb {Z}}^n)$$ $$2^{O(n)}$$ remainders of each component$$x_i^* \mod \ell $$ $$\ell \ge 5(n+1)$$ $$x^*$$ cutting-plane technique , iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$ asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ $$\prod _i O(\log u_i +1)$$ knapsack orsubset-sum problems withpolynomial variable range $$0 \le x_i \le p(n)$$ $$(\log n)^{O(n)}$$ $$n^n \cdot 2^{O(n)}$$
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/fms.2022.97
