Actions of arithmetic groups on homology spheres and acyclic homology manifolds

We establish lower bounds on the dimensions in which arithmetic groups with torsion can act on acyclic manifolds and homology spheres. The bounds rely on the existence of elementary $p$ -groups in the groups concerned. In some cases, including ${\mathrm{Sp}}(2n,\mathbb Z )$ , the bounds we obtain are sharp: if $X$ is a generalized $\mathbb Z /3$ -homology sphere of dimension less than $2n-1$ or a $\mathbb Z /3$ -acyclic $\mathbb Z /3$ -homology manifold of dimension less than $2n$ , and if $n\ge 3$ , then any action of ${\mathrm{Sp}}(2n,\mathbb Z )$ by homeomorphisms on $X$ is trivial; if $n=2$ , then every action of ${\mathrm{Sp}}(2n,\mathbb Z )$ on $X$ factors through the abelianization of ${\mathrm{Sp}}(4,\mathbb Z )$ , which is $\mathbb Z /2$ .     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

Sharp energy estimates for nonlinear fractional diffusion equations

We study the nonlinear fractional equation $(-\Delta )^su=f(u)$ in $\mathbb R ^n,$ for all fractions $0<s<1$ and all nonlinearities $f$ . For every fractional power $s\in (0,1)$ , we obtain sharp energy estimates for bounded global minimizers and for bounded monotone solutions. They are sharp since they are optimal for solutions depending only on one Euclidian variable. As a consequence, we deduce the one-dimensional symmetry of bounded global minimizers and of bounded monotone solutions in dimension $n=3$ whenever $1/2\le s<1$ . This result is the analogue of a conjecture of De Giorgi on one-dimensional symmetry for the classical equation $-\Delta u=f(u)$ in $\mathbb R ^n$ . It remains open for $n=3$ and $s<1/2$ , and also for $n\ge 4$ and all $s$ .     

[1,1,t]-Colorings of Complete Graphs

Given non-negative integers $r, s,$ and $t,$ an $[r,s,t]$ -coloring of a graph $G = (V(G),E(G))$ is a mapping $c$ from $V(G) \cup E(G)$ to the color set $\{1,\ldots ,k\}$ such that $\left|c(v_i) - c(v_j)\right| \ge r$ for every two adjacent vertices $v_i,v_j, \left|c({e_i}) - c(e_j)\right| \ge s$ for every two adjacent edges $e_i,e_j,$ and $\left|c(v_i) - c(e_j)\right| \ge t$ for all pairs of incident vertices and edges, respectively. The $[r,s,t]$ -chromatic number $\chi _{r,s,t}(G)$ of $G$ is defined to be the minimum $k$ such that $G$ admits an $[r,s,t]$ -coloring. In this note we examine $\chi _{1,1,t}(K_p)$ for complete graphs $K_p.$ We prove, among others, that $\chi _{1,1,t}(K_p)$ is equal to $p+t-2+\min \{p,t\}$ whenever $t \ge \left\lfloor {\frac{p}{2}}\right\rfloor -1,$ but is strictly larger if $p$ is even and sufficiently large with respect to $t.$ Moreover, as $p \rightarrow \infty $ and $t=t(p),$ we asymptotically have $\chi _{1,1,t}(K_p)=p+o(p)$ if and only if $t=o(p).$      

A Helly-type theorem for intersections of orthogonally starshaped sets in \mathbb R^d

Let $\mathcal K$ be a finite family of orthogonal polytopes in $\mathbb R^d$ such that, for every nonempty subfamily $\mathcal K^\prime $ of $\mathcal K, \cap \{K : K$ in $\mathcal K^\prime \}$ , if nonempty, is a finite union of boxes whose intersection graph is a tree. Assume that every $d + 1$ (not necessarily distinct) members of $\mathcal K$ meet in a (nonempty) staircase starshaped set. Then $S \equiv \cap \{ K : K$ in $\mathcal K\}$ is nonempty and staircase starshaped.     

Localization and delocalization of eigenvectors for heavy-tailed random matrices

Consider an $n \times n$ Hermitian random matrix with, above the diagonal, independent entries with $\alpha $ -stable symmetric distribution and $0 < \alpha < 2$ . We establish new bounds on the rate of convergence of the empirical spectral distribution of this random matrix as $n$ goes to infinity. When $1 < \alpha < 2$ and $ p > 2$ , we give vanishing bounds on the $L^p$ -norm of the eigenvectors normalized to have unit $L^2$ -norm. On the contrary, when $0 < \alpha < 2/3$ , we prove that these eigenvectors are localized.     

A graph associated to a lattice

In this paper, we associate a simple graph to a lattice $\mathcal L $ , in which the vertex set is being the set of all elements of $\mathcal L $ , and two distinct vertices $x$ and $y$ are adjacent if $x\vee y\in S$ , when $S$ is a multiplicatively closed subset of $\mathcal L $ . We denote this graph by $\Gamma _S(\mathcal L )$ . We study some properties of $\Gamma _S(\mathcal L )$ . Moreover, we investigate the planarity of $\Gamma _S(\mathcal L )$ , whenever $S$ is a saturated multiplicatively closed subset of $\mathcal L $ .     

On the Broadcast Independence Number of Grid Graph

A broadcast on a nontrivial connected graph G is a function ${f:V \longrightarrow \{0, \ldots,\operatorname{diam}(G)\}}$ such that for every vertex ${v \in V(G)}$ , ${f(v) \leq e(v)}$ , where ${\operatorname{diam}(G)}$ denotes the diameter of G and e(v) denotes the eccentricity of vertex v. The broadcast independence number is the maximum value of ${\sum_{v \in V} f(v)}$ over all broadcasts f that satisfy ${d(u,v) > \max \{f(u), f(v)\}}$ for every pair of distinct vertices u, v with positive values. We determine this invariant for grid graphs ${G_{m,n} = P_m \square P_n}$ , where ${2 \leq m \leq n}$ and □ denotes the Cartesian product. We hereby answer one of the open problems raised by Dunbar et al. in (Discrete Appl Math 154:59–75, 2006).     

Tiling Convex Polygons with Congruent Equilateral Triangles

We study the sets $\mathcal{T}_{v}=\{m \in\{1,2,\ldots\}: \mbox{there is a convex polygon in }\mathbb{R}^{2}\mbox{ that has }v\mbox{ vertices and can be tiled with $m$ congruent equilateral triangles}\}$ , v=3,4,5,6. $\mathcal{T}_{3}$ , $\mathcal{T}_{4}$ , and $\mathcal{T}_{6}$ can be quoted completely. The complement $\{1,2,\ldots\} \setminus\mathcal{T}_{5}$ of $\mathcal{T}_{5}$ turns out to be a subset of Euler’s numeri idonei. As a consequence, $\{1,2,\ldots\} \setminus\mathcal{T}_{5}$ can be characterized with up to two exceptions, and a complete characterization is given under the assumption of the Generalized Riemann Hypothesis.     

On a Class of Markov Semigroups on Discrete Ultra-Metric Spaces

We consider a discrete ultra-metric space $\left( X,d\right) $ with a measure m and construct in a natural way a symmetric Markov semigroup $ \left\{ P_{t}\right\} _{t\geq 0}$ in $L^{2}\left( X,m\right) $ and the corresponding Markov process $\left\{ \mathcal{X}_{t}\right\} $ . We prove upper and lower bounds of its transition function and its Green function, give a criterion for the transience, and estimate its moments.     

On the existence of Evans potentials

It is shown that, for every noncompact parabolic Riemannian manifold $X$ and every nonpolar compact $K$ in  $X$ , there exists a positive harmonic function on $X\setminus K$ which tends to $\infty $ at infinity. (This is trivial for $\mathbb{R }$ , easy for  $\mathbb{R }^2$ , and known for parabolic Riemann surfaces.) In fact, the statement is proven, more generally, for any noncompact connected Brelot harmonic space  $X$ , where constants are the only positive superharmonic functions and, for every nonpolar compact set  $K$ , there is a symmetric (positive) Green function for $X\setminus K$ . This includes the case of parabolic Riemannian manifolds. Without symmetry, however, the statement may fail. This is shown by an example, where the underlying space is a graph (the union of the parallel half-lines $\left[0,\infty \right)\times \{0\}, \left[0,\infty \right)\times \{1\}$ , and the line segments $\{n\}\times [0,1], n=0,1,2,\dots $ ).     

On the signed star domination number of regular multigraphs

Let $G$ be a graph with the vertex set $V(G)$ and the edge set $E(G)$ . A function $f: E(G)\longrightarrow \{-1, 1\}$ is said to be a signed star dominating function of $G$ if $\sum _{e \in E_G(v)}f (e)\ge 1 $ , for every $v \in V(G)$ , where $E_G(v) = \{uv\in E(G)\,|\,u \in V (G)\}$ . The minimum values of $\sum _{e \in E_G(v)}f (e)$ , taken over all signed star dominating functions $f$ on $G$ , is called the signed star domination number of $G$ and denoted by $\gamma _{SS}(G)$ . In this paper we determine the signed star domination number of regular multigraphs.     

Exact Lagrangian immersions with one double point revisited

We study exact Lagrangian immersions with one double point of a closed orientable manifold $K$ into $\mathbb{C }^{n}$ . We prove that if the Maslov grading of the double point does not equal $1$ then $K$ is homotopy equivalent to the sphere, and if, in addition, the Lagrangian Gauss map of the immersion is stably homotopic to that of the Whitney immersion, then $K$ bounds a parallelizable $(n+1)$ -manifold. The hypothesis on the Gauss map always holds when $n=2k$ or when $n=8k-1$ . The argument studies a filling of $K$ obtained from solutions to perturbed Cauchy–Riemann equations with boundary on the image $f(K)$ of the immersion. This leads to a new and simplified proof of some of the main results of Ekholm and Smith (Exact Lagrangian immersions with a single double point 2011)). which treated Lagrangian immersions in the case $n=2k$ by applying similar techniques to a Lagrange surgery of the immersion, as well as to an extension of these results to the odd-dimensional case.     

On the zeros of Meixner polynomials

We investigate the zeros of a family of hypergeometric polynomials $M_n(x;\beta ,c)=(\beta )_n\,{}_2F_1(-n,-x;\beta ;1-\frac{1}{c})$ , $n\in \mathbb N ,$ known as Meixner polynomials, that are orthogonal on $(0,\infty )$ with respect to a discrete measure for $\beta >0$ and $0<c<1.$ When $\beta =-N$ , $N\in \mathbb N $ and $c=\frac{p}{p-1}$ , the polynomials $K_n(x;p,N)=(-N)_n\,{}_2F_1(-n,-x;-N;\frac{1}{p})$ , $n=0,1,\ldots , N$ , $0<p<1$ are referred to as Krawtchouk polynomials. We prove results for the zero location of the orthogonal polynomials $M_n(x;\beta ,c)$ , $c<0$ and $n<1-\beta $ , the quasi-orthogonal polynomials $M_n(x;\beta ,c)$ , $-k<\beta <-k+1$ , $k=1,\ldots ,n-1$ and $0<c<1$ or $c>1,$ as well as the polynomials $K_{n}(x;p,N)$ with non-Hermitian orthogonality for $0<p<1$ and $n=N+1,N+2,\ldots $ . We also show that the polynomials $M_n(x;\beta ,c)$ , $\beta \in \mathbb R $ are real-rooted when $c\rightarrow 0$ .     

Chromatic Gallai identities operating on Lovász number

If $G$ is a triangle-free graph, then two Gallai identities can be written as $\alpha (G)+\overline{\chi }(L(G))=|V(G)|=\alpha (L(G))+\overline{\chi }(G)$ , where $\alpha $ and $\overline{\chi }$ denote the stability number and the clique-partition number, and $L(G)$ is the line graph of  $G$ . We show that, surprisingly, both equalities can be preserved for any graph $G$ by deleting the edges of the line graph corresponding to simplicial pairs of adjacent arcs, according to any acyclic orientation of  $G$ . As a consequence, one obtains an operator $\Phi $ which associates to any graph parameter $\beta $ such that $\alpha (G) \le \beta (G) \le \overline{\chi }(G)$ for all graph $G$ , a graph parameter $\Phi _\beta $ such that $\alpha (G) \le \Phi _\beta (G) \le \overline{\chi }(G)$ for all graph $G$ . We prove that $\vartheta (G) \le \Phi _\vartheta (G)$ and that $\Phi _{\overline{\chi }_f}(G)\le \overline{\chi }_f(G)$ for all graph  $G$ , where $\vartheta $ is Lovász theta function and $\overline{\chi }_f$ is the fractional clique-partition number. Moreover, $\overline{\chi }_f(G) \le \Phi _\vartheta (G)$ for triangle-free $G$ . Comparing to the previous strengthenings $\Psi _\vartheta $ and $\vartheta ^{+ \triangle }$ of $\vartheta $ , numerical experiments show that $\Phi _\vartheta $ is a significant better lower bound for $\overline{\chi }$ than $\vartheta $ .     

Explicit Constructions of Centrally Symmetric k-Neighborly Polytopes and Large Strictly Antipodal Sets

We present explicit constructions of centrally symmetric $2$ -neighborly $d$ -dimensional polytopes with about $3^{d/2}\approx (1.73)^d$ vertices and of centrally symmetric $k$ -neighborly $d$ -polytopes with about $2^{{3d}/{20k^2 2^k}}$ vertices. Using this result, we construct for a fixed $k\ge 2$ and arbitrarily large $d$ and $N$ , a centrally symmetric $d$ -polytope with $N$ vertices that has at least $\left( 1-k^2\cdot (\gamma _k)^d\right) \genfrac(){0.0pt}{}{N}{k}$ faces of dimension $k-1$ , where $\gamma _2=1/\sqrt{3}\approx 0.58$ and $\gamma _k = 2^{-3/{20k^2 2^k}}$ for $k\ge 3$ . Another application is a construction of a set of $3^{\lfloor d/2 -1\rfloor }-1$ points in $\mathbb R ^d$ every two of which are strictly antipodal as well as a construction of an $n$ -point set (for an arbitrarily large $n$ ) in $\mathbb R ^d$ with many pairs of strictly antipodal points. The two latter results significantly improve the previous bounds by Talata, and Makai and Martini, respectively.     

Minimal simplices inscribed in a convex body

Measuring how far a convex body $\mathcal{K }$ (of dimension $n$ ) with a base point ${O}\in \,\text{ int }\,\mathcal{K }$ is from an inscribed simplex $\Delta \ni {O}$ in “minimal” position, the interior point ${O}$ can display regular or singular behavior. If ${O}$ is a regular point then the $n+1$ chords emanating from the vertices of $\Delta $ and meeting at ${O}$ are affine diameters, chords ending in pairs of parallel hyperplanes supporting $\mathcal{K }$ . At a singular point ${O}$ the minimal simplex $\Delta $ degenerates. In general, singular points tend to cluster near the boundary of $\mathcal{K }$ . As connection to a number of difficult and unsolved problems about affine diameters shows, regular points are elusive, often non-existent. The first result of this paper uses Klee’s fundamental inequality for the critical ratio and the dimension of the critical set to obtain a general existence for regular points in a convex body with large distortion (Theorem A). This, in various specific settings, gives information about the structure of the set of regular and singular points (Theorem B). At the other extreme when regular points are in abundance, a detailed study of examples leads to the conjecture that the simplices are the only convex bodies with no singular points. The second and main result of this paper is to prove this conjecture in two different settings, when (1) $\mathcal{K }$ has a flat point on its boundary, or (2) $\mathcal{K }$ has $n$ isolated extremal points (Theorem C).     

Growth estimates for orbits of self-adjoint groups

Let $G$ denote a closed, connected, self-adjoint, noncompact subgroup of $GL(n,\mathbb R )$ , and let $d_{R}$ and $d_{L}$ denote respectively the right and left invariant Riemannian metrics defined by the canonical inner product on $M(n,\mathbb R ) = T_{I} GL(n,\mathbb R )$ . Let $v$ be a nonzero vector of $\mathbb R ^{n}$ such that the orbit $G(v)$ is unbounded in $\mathbb R ^{n}$ . Then the function $g \rightarrow d_{R}(g, G_{v})$ is unbounded, where $G_{v} = \{g \in G : g(v) = v \}$ , and we obtain algebraically defined upper and lower bounds $\lambda ^{+}(v)$ and $\lambda ^{-}(v)$ for the asymptotic behavior of the function $\frac{log|g(v)|}{d_{R}(g, G_{v})}$ as $d_{R}(g, G_{v}) \rightarrow \infty $ . The upper bound $\lambda ^{+}(v)$ is at most 1. The orbit $G(v)$ is closed in $\mathbb R ^{n} \Leftrightarrow \lambda ^{-}(w)$ is positive for some w $\in G(v)$ . If $G_{v}$ is compact, then $g \rightarrow |d_{R}(g,I) - d_{L}(g,I)|$ is uniformly bounded in $G$ , and the exponents $\lambda ^{+}(v)$ and $\lambda ^{-}(v)$ are sharp upper and lower asymptotic bounds for the functions $\frac{log|g(v)|}{d_{R}(g,I)}$ and $\frac{log|g(v)|}{d_{L}(g,I)}$ as $d_{R}(g,I) \rightarrow \infty $ or as $d_{L}(g,I) \rightarrow \infty $ . However, we show by example that if $G_{v}$ is noncompact, then there need not exist asymptotic upper and lower bounds for the function $\frac{log|g(v)|}{d_{L}(g, G_{v})}$ as $d_{L}(g, G_{v}) \rightarrow \infty $ . The results apply to representations of noncompact semisimple Lie groups $G$ on finite dimensional real vector spaces. We compute $\lambda ^{+}$ and $\lambda ^{-}$ for the irreducible, real representations of $SL(2,\mathbb R )$ , and we show that if the dimension of the $SL(2,\mathbb R )$ -module $V$ is odd, then $\lambda ^{+} = \lambda ^{-}$ on a nonempty open subset of $V$ . We show that the function $\lambda ^{-}$ is $K$ -invariant, where $K = O(n,\mathbb R ) \cap G$ . We do not know if $\lambda ^{-}$ is $G$ -invariant.     

The effect of linear perturbations on the Yamabe problem

In conformal geometry, the Compactness Conjecture asserts that the set of Yamabe metrics on a smooth, compact, aspherical Riemannian manifold $\left( M,g\right) $ is compact. Established in the locally conformally flat case by Schoen (Lecture Notes in Mathematics, vol. 1365, pp. 120–154. Springer, Berlin 1989, Surveys Pure Application and Mathematics, 52 Longman Science, Technology, pp. 311–320. Harlow 1991) and for $n\le 24$ by Khuri–Marques–Schoen (J Differ Geom 81(1):143–196, 2009), it has revealed to be generally false for $n\ge 25$ as shown by Brendle (J Am Math Soc 21(4):951–979, 2008) and Brendle–Marques (J Differ Geom 81(2):225–250, 2009). A stronger version of it, the compactness under perturbations of the Yamabe equation, is addressed here with respect to the linear geometric potential $\frac{n-2}{4(n-1)} {{\mathrm{Scal}}}_g,\, {{\mathrm{Scal}}}_g$ being the Scalar curvature of $\left( M,g\right) $ . We show that a-priori $L^\infty $ –bounds fail for linear perturbations on all manifolds with $n\ge 4$ as well as a-priori gradient $L^2$ –bounds fail for non-locally conformally flat manifolds with $n\ge 6$ and for locally conformally flat manifolds with $n\ge 7$ . In several situations, the results are optimal. Our proof combines a finite dimensional reduction and the construction of a suitable ansatz for the solutions generated by a family of varying metrics in the conformal class of $g$ .     

Asymptotic learning on Bayesian social networks

We study a standard model of economic agents on the nodes of a social network graph who learn a binary “state of the world” $S$ , from initial signals, by repeatedly observing each other’s best guesses. Asymptotic learning is said to occur on a family of graphs $G_n = (V_n,E_n)$ with $|V_n| \rightarrow \infty $ if with probability tending to $1$ as $n \rightarrow \infty $ all agents in $G_n$ eventually estimate $S$ correctly. We identify sufficient conditions for asymptotic learning and contruct examples where learning does not occur when the conditions do not hold.