Generalization of transitive fraternal augmentations for directed graphs and its applications

Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,

1.

if and then or (fraternity);

2.

if and then (transitivity).

In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col₂(G)≤O(∇₁(G)∇₀(G)²), where ∇_k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇_k(G) bounds the distance (k+1)-coloring number col_k+1(G) with a function f(∇_k(G)). On the other hand, ∇_k(G)≤(col_2k+1(G))^2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.     

Extension of Fourier algebra homomorphisms to duals of algebras of uniformly continuous functionals

For a locally compact group G, let XG be one of the following introverted subspaces of VN(G): , the C^∗-algebra of uniformly continuous functionals on A(G); , the space of weakly almost periodic functionals on A(G); or , the C^∗-algebra generated by the left regular representation on the measure algebra of G. We discuss the extension of homomorphisms of (reduced) Fourier-Stieltjes algebras on G and H to cb-norm preserving, weak^∗-weak^∗-continuous homomorphisms of into , where (XG,XH) is one of the pairs , , or . When G is amenable, these extensions are characterized in terms of piecewise affine maps.     

Covering line graphs with equivalence relations

An equivalence graph is a disjoint union of cliques, and the equivalence number of a graph G is the minimum number of equivalence subgraphs needed to cover the edges of G. We consider the equivalence number of a line graph, giving improved upper and lower bounds: . This disproves a recent conjecture that is at most three for triangle-free G; indeed it can be arbitrarily large.To bound we bound the closely related invariant σ(G), which is the minimum number of orientations of G such that for any two edges e,f incident to some vertex v, both e and f are oriented out of v in some orientation. When G is triangle-free, . We prove that even when G is triangle-free, it is NP-complete to decide whether or not σ(G)≤3.     

Universal moduli spaces of surfaces with flat bundles and cobordism theory

For a compact, connected Lie group G, we study the moduli of pairs (Σ,E), where Σ is a genus g Riemann surface and E→Σ is a flat G-bundle. Varying both the Riemann surface Σ and the flat bundle leads to a moduli space , parametrizing families Riemann surfaces with flat G-bundles. We show that there is a stable range in which the homology of is independent of g. The stable range depends on the genus of the surface. We then identify the homology of this moduli space in the stable range, in terms of the homology of an explicit infinite loop space. Rationally, the stable cohomology of this moduli space is generated by the Mumford-Morita-Miller κ-classes, and the ring of characteristic classes of principal G-bundles, H^∗(BG). Equivalently, our theorem calculates the homology of the moduli space of semi-stable holomorphic bundles on Riemann surfaces.We then identify the homotopy type of the category of one-manifolds and surface cobordisms, each equipped with a flat G-bundle. Our methods combine the classical techniques of Atiyah and Bott, with the new techniques coming out of Madsen and Weiss's proof of Mumford's conjecture on the stable cohomology of the moduli space of Riemann surfaces.     

Multistage n-dimensional universal spaces and extensions

Let Iτ be the Tychonoff cube of weight τ?ω with a fixed point, στ and Στ be the correspondent σ- and Σ-products in Iτ and στ⊂(Σστ=ω(στ))⊂Στ. Then for any n∈{0,1,2,…}, there exists a compactum Unτ⊂Iτ of dimension n such that for any Z⊂Iτ of dimension?n, there exists a topological embedding of Z in Unτ that maps the intersections of Z with στ, Σστ and Στ to the intersections , and of Unτ with στ, Σστ and Στ, respectively; , and are n-dimensional and is σ-compact, is a Lindelöf Σ-space and is a sequentially compact normal Fréchet-Urysohn space. This theorem (on multistage universal spaces of given dimension and weight) implies multistage extension theorems (in particular, theorems on Corson and Eberlein compactifications) for Tychonoff spaces.     

Operators on the space of vector-valued totally measurable functions

Let L(X,Y) stand for the space of all bounded linear operators between real Banach spaces X and Y, and let Σ be a σ-algebra of sets. A bounded linear operator T from the Banach space B(Σ,X) of X-valued Σ-totally measurable functions to Y is said to be σ-smooth if ‖T(fn)Y_‖→0 whenever a sequence of scalar functions (‖fn(⋅)X_‖) is order convergent to 0 in B(Σ). It is shown that a bounded linear operator is σ-smooth if and only if its representing measure is variationally semi-regular, i.e., as An↓∅ (here stands for the semivariation of m on A∈Σ). As an application, we show that the space Lσs(B(Σ,X),Y) of all σ-smooth operators from B(Σ,X) to Y provided with the strong operator topology is sequentially complete. We derive a Banach-Steinhaus type theorem for σ-smooth operators from B(Σ,X) to Y. Moreover, we characterize countable additivity of measures in terms of continuity of the corresponding operators .     

Game colouring of the square of graphs

This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if G is a forest of maximum degree Δ≥9, then , and there are forests G with . It is also proved that for an outerplanar graph G of maximum degree Δ, , and for a planar graph G of maximum degree Δ, .     

On signed cycle domination in graphs

Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑_e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures.     

A generalization of Kneser's Addition Theorem

Let A=(A₁,…,Am) be a sequence of finite subsets from an additive abelian group G. Let Σ?(A) denote the set of all group elements representable as a sum of ? elements from distinct terms of A, and set . Our main theorem is the following lower bound:

     

On duality between étale groupoids and Hopf algebroids

For any étale Lie groupoid G over a smooth manifold M, the groupoid convolution algebra of smooth functions with compact support on G has a natural coalgebra structure over the commutative algebra which makes it into a Hopf algebroid. Conversely, for any Hopf algebroid A over we construct the associated spectral étale Lie groupoid over M such that is naturally isomorphic to G. Both these constructions are functorial, and is fully faithful left adjoint to . We give explicit conditions under which a Hopf algebroid is isomorphic to the Hopf algebroid of an étale Lie groupoid G.     

Some relations between rank, chromatic number and energy of graphs

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. Let G be a graph of order n and be the rank of the adjacency matrix of G. In this paper we characterize all graphs with . Among other results we show that apart from a few families of graphs, , where n is the number of vertices of G, and χ(G) are the complement and the chromatic number of G, respectively. Moreover some new lower bounds for E(G) in terms of are given.     

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line of the form [a_i,a_i+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G)≤t+⌈log(n−t)⌉−1 and , where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds.F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, and , where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then and this bound is tight. We also show that if G is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , s≥0, then , where χ(G) is the chromatic number of G.     

Quasi-convex density and determining subgroups of compact abelian groups

For an abelian topological group G, let denote the dual group of all continuous characters endowed with the compact open topology. Given a closed subset X of an infinite compact abelian group G such that w(X)<w(G), and an open neighborhood U of 0 in T, we show that . (Here, w(G) denotes the weight of G.) A subgroup D of G determines G if the map defined by r(χ)=χ?D for , is an isomorphism between and . We prove that

     

Note on the energy of regular graphs

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ₁ is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that .     

A unique solution to a nonlinear elliptic equation

The purpose of this paper is to prove the existence of a unique, classical solution to the nonlinear elliptic partial differential equation −∇⋅(a(u(x))∇u(x))=f(x) under periodic boundary conditions, where u(x₀)=u₀ at x₀∈Ω, with Ω=TN, the N-dimensional torus, and N=2,3. The function a is assumed to be smooth, and a(u(x))>0 for , where G⊂R is a bounded interval. We prove that if the functions f and a satisfy certain conditions, then a unique classical solution u exists. The range of the solution u is a subset of a specified interval . Applications of this work include stationary heat/diffusion problems with a source/sink, where the value of the solution is known at a spatial location x₀.     

Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, χ_p(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χ_p(G) in terms of the k-colouring number of G for k=2^p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χ_k+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:

(a)

For every positive integer p, χ_p(G) is bounded by a constant for all G∈K.

(b)

For every positive integer k, is bounded by a constant for all G∈K.

It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following:

(c)

For every positive integer q, ∇_q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.

Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇_q−(1/2)(G) and by showing that there is a function F_k such that . This gives an alternate proof of the equivalence of (a) and (c).     

Directed 3-cycle decompositions of complete directed graphs with quadratic leaves

Let G be a vertex-disjoint union of directed cycles in the complete directed graph D_t, let |E(G)| be the number of directed edges of G and suppose or if t=5, and if t=6. It is proved in this paper that for each positive integer t, there exist -decompositions for D_t−G if and only if .     

Upper bounds on the first eigenvalue for a diffusion operator via Bakry-Émery Ricci curvature

Let L=Δ−∇φ⋅∇ be a symmetric diffusion operator with an invariant measure on a complete Riemannian manifold. In this paper we give an upper bound estimate on the first eigenvalue of the diffusion operator L on the complete manifold with the m-dimensional Bakry-Émery Ricci curvature satisfying Ricm,n(L)?−(n−1), and therefore generalize a Cheng's result on the Laplacian (S.-Y. Cheng (1975) [8]) to the case of the diffusion operator.     

Excessive factorizations of bipartite multigraphs

An excessive factorization of a multigraph G is a set F={F₁,F₂,…,F_r} of 1-factors of G whose union is E(G) and, subject to this condition, r is minimum. The integer r is called the excessive index of G and denoted by . We set if an excessive factorization does not exist. Analogously, let m be a fixed positive integer. An excessive[m]-factorization is a set M={M₁,M₂,…,M_k} of matchings of G, all of size m, whose union is E(G) and, subject to this condition, k is minimum. The integer k is denoted by and called the excessive [m]-index of G. Again, we set if an excessive [m]-factorization does not exist. In this paper we shall prove that, for bipartite multigraphs, both the parameters and are computable in polynomial time, and we shall obtain an efficient algorithm for finding an excessive factorization and excessive [m]-factorization, respectively, of any bipartite multigraph.     

Logarithmic Sobolev Inequalities for Pinned Loop Groups

LetGbe a connected compact type Lie group equipped with anAd_G-invariant inner product on the Lie algebra ofG. Given this data there is a well known left invariant “H¹-Riemannian structure” on =(G)—the infinite dimensional group of continuous based loops inG. Using this Riemannian structure, we define and construct a “heat kernel”ν_T(g₀, ·) associated to the Laplace–Beltrami operator on (G). HereT>0,g₀∈(G), andν_T(g₀,·) is a certain probability measure on (G). For fixedg₀∈(G) andT>0, we use the measureν_T(g₀,·) and the Riemannian structure on (G) to construct a “classical” pre-Dirichlet form. The main theorem of this paper asserts that this pre-Dirichlet form admits a logarithmic Sobolev inequality.