Invariant random graphs with iid degrees in a general geography

Let D be a non-negative integer-valued random variable and let G = (V, E) be an infinite transitive finite-degree graph. Continuing the work of Deijfen and Meester (Adv Appl Probab 38:287–298) and Deijfen and Jonasson (Electron Comm Probab 11:336–346), we seek an Aut(G)-invariant random graph model with V as vertex set, iid degrees distributed as D and finite mean connections (i.e., the sum of the edge lengths in the graph metric of G of a given vertex has finite expectation). It is shown that if G has either polynomial growth or rapid growth, then such a random graph model exists if and only if ${\mathbb{E}[D\,R(D)] < \infty}$ . Here R(n) is the smallest possible radius of a combinatorial ball containing more than n vertices. With rapid growth we mean that the number of vertices in a ball of radius n is of at least order exp(n ^c ) for some c > 0. All known transitive graphs have either polynomial or rapid growth. It is believed that no other growth rates are possible. When G has rapid growth, the result holds also when the degrees form an arbitrary invariant process. A counter-example shows that this is not the case when G grows polynomially. For this case, we provide other, quite sharp, conditions under which the stronger statement does and does not hold respectively. Our work simplifies and generalizes the results for ${G\,=\,\mathbb {Z}}$ in [4] and proves, e.g., that with ${G\,=\,\mathbb {Z}^d}$ , there exists an invariant model with finite mean connections if and only if ${\mathbb {E}[D^{(d+1)/d}] < \infty}$ . When G has exponential growth, e.g., when G is a regular tree, the condition becomes ${\mathbb {E}[D\,\log\,D] < \infty}$ .     

Shintani lifting and real-valued characters

We study Shintani lifting of real-valued irreducible characters of finite reductive groups. In particular, if G is a connected reductive group defined over ${\mathbb{F}_q}$ , and ψ is an irreducible character of G( ${\mathbb{F}_{q^m}}$ ) which is the lift of an irreducible character χ of G( ${\mathbb{F}_q}$ ), we prove ψ is real-valued if and only if χ is real-valued. In the case m = 2, we show that if χ is invariant under the twisting operator of G( ${\mathbb{F}_{q^2}}$ ), and is a real-valued irreducible character in the image of lifting from G( ${\mathbb{F}_q}$ ), then χ must be an orthogonal character. We also study properties of the Frobenius–Schur indicator under Shintani lifting of regular, semisimple, and irreducible Deligne–Lusztig characters of finite reductive groups.     

Symmetric diameter two graphs with affine-type vertex-quasiprimitive automorphism group

We study the class of G-symmetric graphs Γ with diameter 2, where G is an affine-type quasiprimitive group on the vertex set of Γ. These graphs arise from normal quotient analysis as basic graphs in the class of symmetric diameter 2 graphs. It is known that ${G \cong V \rtimes G_0}$ , where V is a finite-dimensional vector space over a finite field and G ₀ is an irreducible subgroup of GL (V), and Γ is a Cayley graph on V. In particular, we consider the case where ${V = \mathbb {F}_p^d}$ for some prime p and G ₀ is maximal in GL (d, p), with G ₀ belonging to the Aschbacher classes ${\mathcal {C}_2, \mathcal {C}_4, \mathcal {C}_6, \mathcal {C}_7}$ , and ${\mathcal {C}_8}$ . For ${G_0 \in \mathcal {C}_i, i = 2,4,8}$ , we determine all diameter 2 graphs which arise. For ${G_0 \in \mathcal {C}_6, \mathcal {C}_7}$ we obtain necessary conditions for diameter 2, which restrict the number of unresolved cases to be investigated, and in some special cases determine all diameter 2 graphs.     

Diagram Groupoids and von Neumann Algebras

The main purpose of this paper is to study certain algebraic structures induced by directed graphs. We have studied graph groupoids, which are algebraic structures induced by given graphs. By defining a certain groupoid-homomorphism ?? on the graph groupoid ${\mathbb{G}}$ of a given graph G, we define the diagram of G by the image ${\delta(\mathbb{G})}$ of ??, equipped with the inherited binary operation on ${\mathbb{G}}$ . We study the fundamental properties of the diagram ${\delta(\mathbb{G})}$ , and compare them with those of ${\mathbb{G}}$ . Similar to Cho (Acta Appl Math 95:95?C134, 2007), we construct the groupoid von Neumann algebra ${\mathcal{M}_{G}=vN(\delta(\mathbb{G}))}$ , generated by ${\delta(\mathbb{G})}$ , and consider the operator algebraic properties of ${\mathcal{M}_{G}}$ . In particular, we show ${\mathcal{M}_{G}}$ is *-isomorphic to a von Neumann algebra generated by a family of idempotent operators and nilpotent operators, under suitable representations.     

On Zero-Sum {\mathbb{Z}_k} -Magic Labelings of 3-Regular Graphs

Let G =  (V, E) be a finite loopless graph and let (A, +) be an abelian group with identity 0. Then an A-magic labeling of G is a function ${\phi}$ from E into A ? {0} such that for some ${a \in A, \sum_{e \in E(v)} \phi(e) = a}$ for every ${v \in V}$ , where E(v) is the set of edges incident to v. If ${\phi}$ exists such that a =  0, then G is zero-sum A-magic. Let zim(G) denote the subset of ${\mathbb{N}}$ (the positive integers) such that ${1 \in zim(G)}$ if and only if G is zero-sum ${\mathbb{Z}}$ -magic and ${k \geq 2 \in zim(G)}$ if and only if G is zero-sum ${\mathbb{Z}_k}$ -magic. We establish that if G is 3-regular, then ${zim(G) = \mathbb{N} - \{2\}}$ or ${\mathbb{N} - \{2,4\}.}$      

Techniques of computations of Dolbeault cohomology of solvmanifolds

We consider semi-direct products ${\mathbb{C}^{n}\ltimes_{\phi}N}$ of Lie groups with lattices Γ such that N are nilpotent Lie groups with left-invariant complex structures. We compute the Dolbeault cohomology of direct sums of holomorphic line bundles over G/Γ by using the Dolbeaut cohomology of the Lie algebras of the direct product ${\mathbb{C}^{n}\times N}$ . As a corollary of this computation, we can compute the Dolbeault cohomology H ^p,q (G/Γ) of G/Γ by using a finite dimensional cochain complexes. Computing some examples, we observe that the Dolbeault cohomology varies for choices of lattices Γ.     

Moment Functions and Central Limit Theorem for Jacobi Hypergroups on [0,\infty [

In this paper, we derive sharp estimates and asymptotic results for moment functions on Jacobi type hypergroups. Moreover, we use these estimates to prove a central limit theorem (CLT) for random walks on Jacobi hypergroups with growing parameters $\alpha ,\beta \rightarrow \infty $ . As a special case, we obtain a CLT for random walks on the hyperbolic spaces ${H}_d(\mathbb F )$ with growing dimensions $d$ over the fields $\mathbb F =\mathbb R ,\ \mathbb C $ or the quaternions $\mathbb H $ .     

An analogue of Artin’s conjecture for multiplicative subgroups of the rationals

Given ${\Gamma \subset \mathbb{Q}^*}$ a multiplicative subgroup and ${m \in \mathbb{N}^+}$ , assuming the Generalized Riemann Hypothesis, we determine an asymptotic formula for the number of primes p ≤ x for which ind _p Γ = m, where ind _p Γ = (p ? 1)/|Γ _p | and Γ _p is the reduction of Γ modulo p. This problem is a generalization of some earlier works by Cangelmi–Pappalardi, Lenstra, Moree, Murata, Wagstaff, and probably others. We prove, on GRH, that the primes with this property have a density and, in the case when Γ contains only positive numbers, we give an explicit expression for it in terms of an Euler product. We conclude with some numerical computations.     

Metrization of Weighted Graphs

We find a set of necessary and sufficient conditions under which the weight ${w: E \rightarrow \mathbb{R}^{+}}$ on the graph G = (V, E) can be extended to a pseudometric ${d : V \times V \rightarrow \mathbb{R}^{+}}$ . We describe the structure of graphs G for which the set ${\mathfrak{M}_{w}}$ of all such extensions contains a metric whenever w is strictly positive. Ordering ${\mathfrak{M}_{w}}$ by the pointwise order, we have found that the posets $({\mathfrak{M}_{w}, \leqslant)}$ contain the least elements ρ _0,w if and only if G is a complete k-partite graph with ${k \, \geqslant \, 2}$ . In this case the symmetric functions ${f : V \times V \rightarrow \mathbb{R}^{+}}$ , lying between ρ _0,w and the shortest-path pseudometric, belong to ${\mathfrak{M}_{w}}$ for every metrizable w if and only if the cardinality of all parts in the partition of V is at most two.     

Generic representations of abelian groups and extreme amenability

If G is a Polish group and Γ is a countable group, denote by Hom(Γ, G) the space of all homomorphisms Γ → G. We study properties of the group $\overline {\pi (\Gamma )} $ for the generic π ∈ Hom(Γ, G), when Γ is abelian and G is one of the following three groups: the unitary group of an infinite-dimensional Hilbert space, the automorphism group of a standard probability space, and the isometry group of the Urysohn metric space. Under mild assumptions on Γ, we prove that in the first case, there is (up to isomorphism of topological groups) a unique generic $\overline {\pi (\Gamma )} $ ; in the other two, we show that the generic $\overline {\pi (\Gamma )} $ is extremely amenable. We also show that if Γ is torsionfree, the centralizer of the generic π is as small as possible, extending a result of Chacon and Schwartzbauer from ergodic theory.     

Embedding median algebras in products of trees

We show that a metric median algebra satisfying certain conditions admits a bilipschitz embedding into a finite product of $\mathbb{R }$ -trees. This gives rise to a characterisation of closed connected subalgebras of finite products of complete $\mathbb{R }$ -trees up to bilipschitz equivalence. Spaces of this sort arise as asymptotic cones of coarse median spaces. This applies to a large class of finitely generated groups, via their Cayley graphs. We show that such groups satisfy the rapid decay property. We also recover the result of Behrstock, Dru?u and Sapir, that the asymptotic cone of the mapping class group embeds in a finite product of $\mathbb{R }$ -trees.     

Graphs with Average Degree Smaller Than {\frac {30}{11}} Burn Slowly

In this paper, we consider the following firefighter problem on a finite graph G =  (V, E). Suppose that a fire breaks out at a given vertex ${v \in V}$ . In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbours of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate ${\rho(G)}$ of G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a random vertex of G. Let ε >  0. We show that any graph G on n vertices with at most ${(\frac {15}{11} - \varepsilon)n}$ edges can be well protected, that is, ${\rho(G) > \frac {\varepsilon}{60} > 0}$ . Moreover, a construction of a random graph is proposed to show that the constant ${\frac {15}{11}}$ cannot be improved.     

On Rational Pairings of Functors

In the theory of coalgebras C over a ring R, the rational functor relates the category $_{C^*}{\mathbb{M}}$ of modules over the algebra C ^* (with convolution product) with the category $^C{\mathbb{M}}$ of comodules over C. This is based on the pairing of the algebra C ^* with the coalgebra C provided by the evaluation map ${\rm ev}:C^*\otimes_R C\to R$ . The (rationality) condition under consideration ensures that $^C{\mathbb{M}}$ becomes a coreflective full subcategory of $_{C^*}{\mathbb{M}}$ . We generalise this situation by defining a pairing between endofunctors T and G on any category ${\mathbb{A}}$ as a map, natural in $a,b\in {\mathbb{A}}$ , $$ \beta_{a,b}:{\mathbb{A}}(a, G(b)) \to {\mathbb{A}}(T(a),b), $$ and we call it rational if these all are injective. In case T?=?(T, m _T , e _T ) is a monad and G?=?(G, δ _G , ε _G ) is a comonad on ${\mathbb{A}}$ , additional compatibility conditions are imposed on a pairing between T and G. If such a pairing is given and is rational, and T has a right adjoint monad T ^???, we construct a rational functor as the functor-part of an idempotent comonad on the T-modules ${\mathbb{A}}_{T}$ which generalises the crucial properties of the rational functor for coalgebras. As a special case we consider pairings on monoidal categories.     

Ricci Flow on Open 4-Manifolds with Positive Isotropic Curvature

In this note we prove the following result: Let X be a complete, connected 4-manifold with uniformly positive isotropic curvature, with bounded geometry, and with no essential incompressible space form. Then X is diffeomorphic to $\mathbb{S}^{4}$ , or $\mathbb{RP}^{4}$ , or $\mathbb{S}^{3}\times\mathbb {S}^{1}$ , or $\mathbb{S}^{3}\widetilde{\times} \mathbb{S}^{1}$ , or a possibly infinite connected sum of them. This extends work of Hamilton and Chen–Zhu to the noncompact case. The proof uses Ricci flow with surgery on complete 4-manifolds, and is inspired by recent work of Bessières, Besson, and Maillot.     

Applications of Automata and Graphs: Labeling-Operators in Hilbert Space I

We show that certain representations of graphs by operators on Hilbert space have uses in signal processing and in symbolic dynamics. Our main result is that graphs built on automata have fractal characteristics. We make this precise with the use of Representation Theory and of Spectral Theory of a certain family of Hecke operators. Let G be a directed graph. We begin by building the graph groupoid $\Bbb{G}$ induced by G, and representations of  $\Bbb{G}$ . Our main application is to the groupoids defined from automata. By assigning weights to the edges of a fixed graph G, we give conditions for $\Bbb{G}$ to acquire fractal-like properties, and hence we can have fractaloids or G-fractals. Our standing assumption on G is that it is locally finite and connected, and our labeling of G is determined by the “out-degrees of vertices”. From our labeling, we arrive at a family of Hecke-type operators whose spectrum is computed. As applications, we are able to build representations by operators on Hilbert spaces (including the Hecke operators); and we further show that automata built on a finite alphabet generate fractaloids. Our Hecke-type operators, or labeling operators, come from an amalgamated free probability construction, and we compute the corresponding amalgamated free moments. We show that the free moments are completely determined by certain scalar-valued functions.     

Sets with finite {\mathbb H}-perimeter and controlled normal

In the Heisenberg group, we prove that the boundary of sets with finite ${\mathbb H}$ -perimeter and having a bound on the measure theoretic normal is an ${\mathbb H}$ -Lipschitz graph. Then we show that if the normal is, on the boundary, the restriction of a continuous mapping, then the boundary is an ${\mathbb H}$ -regular surface.     

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.     

Note on Group Distance Magic Graphs G[C 4]

A group distance magic labeling or a ${\mathcal{G}}$ -distance magic labeling of a graph G =  (V, E) with ${|V | = n}$ is a bijection f from V to an Abelian group ${\mathcal{G}}$ of order n such that the weight ${w(x) = \sum_{y\in N_G(x)}f(y)}$ of every vertex ${x \in V}$ is equal to the same element ${\mu \in \mathcal{G}}$ , called the magic constant. In this paper we will show that if G is a graph of order n =  2 ^p (2k + 1) for some natural numbers p, k such that ${\deg(v)\equiv c \mod {2^{p+1}}}$ for some constant c for any ${v \in V(G)}$ , then there exists a ${\mathcal{G}}$ -distance magic labeling for any Abelian group ${\mathcal{G}}$ of order 4n for the composition G[C ₄]. Moreover we prove that if ${\mathcal{G}}$ is an arbitrary Abelian group of order 4n such that ${\mathcal{G} \cong \mathbb{Z}_2 \times\mathbb{Z}_2 \times \mathcal{A}}$ for some Abelian group ${\mathcal{A}}$ of order n, then there exists a ${\mathcal{G}}$ -distance magic labeling for any graph G[C ₄], where G is a graph of order n and n is an arbitrary natural number.