Abstract We prove an inequality that unifies previous works of the authors on the properties of the Radon transform on convex bodies including an extension of the Busemann–Petty problem and a slicing inequality for arbitrary functions. Let $K$ and $L$ be star bodies in ${\mathbb R}^n,$ let $0<k<n$ be an integer, and let $f,g$ be non-negative continuous functions on $K$ and $L$, respectively, so that $\|g\|_\infty =g(0)=1.$ Then $$\begin{align*} & \frac{\int_Kf}{\left(\int_L g\right)^{\frac{n-k}n}|K|^{\frac kn}} \le \frac n{n-k} \left(d_{\textrm{ovr}}(K,\mathcal{B}\mathcal{P}_k^n)\right)^k \max_{H} \frac{\int_{K\cap H} f}{\int_{L\cap H} g}, \end{align*}$$where $|K|$ stands for volume of proper dimension, $C$ is an absolute constant, the maximum is taken over all $(n-k)$-dimensional subspaces of ${\mathbb R}^n,$ and $d_{\textrm{ovr}}(K,\mathcal{B}\mathcal{P}_k^n)$ is the outer volume ratio distance from $K$ to the class of generalized $k$-intersection bodies in ${\mathbb R}^n.$ Another consequence of this result is a mean value inequality for the Radon transform. We also obtain a generalization of the isomorphic version of the Shephard problem.
more »
« less
On the edit distance function of the random graph
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
- Award ID(s):
- 1839918
- NSF-PAR ID:
- 10318851
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- Volume:
- 31
- Issue:
- 2
- ISSN:
- 0963-5483
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let $\Omega_q$ denote the set of proper $[q]$-colorings of the random graph $G_{n,m}, m=dn/2$ and let $H_q$ be the graph with vertex set $\Omega_q$ and an edge $\set{\s,\t}$ where $\s,\t$ are mappings $[n]\to[q]$ iff $h(\s,\t)=1$. Here $h(\s,\t)$ is the Hamming distance $|\set{v\in [n]:\s(v)\neq\t(v)}|$. We show that w.h.p. $H_q$ contains a single giant component containing almost all colorings in $\Omega_q$ if $d$ is sufficiently large and $q\geq \frac{cd}{\log d}$ for a constant $c>3/2$.more » « less
-
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
-
Abstract Let $\gamma(G)$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n -vertex graph of minimum degree at least d , then $$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$ In this paper the main result is that if G is any n -vertex d -regular graph of girth at least five, then $$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$ for some constant c independent of d . This result is sharp in the sense that as $d \rightarrow \infty$ , almost all d -regular n -vertex graphs G of girth at least five have $$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$ Furthermore, if G is a disjoint union of ${n}/{(2d)}$ complete bipartite graphs $K_{d,d}$ , then ${\gamma_\circ}(G) = \frac{n}{2}$ . We also prove that there are n -vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that ${\gamma_\circ}(G) \sim {n}/{2}$ as $d \rightarrow \infty$ . Therefore both the girth and regularity conditions are required for the main result.more » « less
-
null (Ed.)Abstract We show how to construct a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner over a set $${P}$$ P of n points in $${\mathbb {R}}^d$$ R d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $${\vartheta },\varepsilon \in (0,1)$$ ϑ , ε ∈ ( 0 , 1 ) , the computed spanner $${G}$$ G has $$\begin{aligned} {{\mathcal {O}}}\bigl (\varepsilon ^{-O(d)} {\vartheta }^{-6} n(\log \log n)^6 \log n \bigr ) \end{aligned}$$ O ( ε - O ( d ) ϑ - 6 n ( log log n ) 6 log n ) edges. Furthermore, for any k , and any deleted set $${{B}}\subseteq {P}$$ B ⊆ P of k points, the residual graph $${G}\setminus {{B}}$$ G \ B is a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner for all the points of $${P}$$ P except for $$(1+{\vartheta })k$$ ( 1 + ϑ ) k of them. No previous constructions, beyond the trivial clique with $${{\mathcal {O}}}(n^2)$$ O ( n 2 ) edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices, $$\vartheta |B|$$ ϑ | B | , lose their distance preserving connectivity). Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black-box fashion.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/S0963548321000353
