Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].     

Improper colouring of (random) unit disk graphs

For any graph G, the k-improper chromatic numberχ^k(G) is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate χ^k for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1-3) (1999) 123-137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187-212], and McDiarmid and Müller [On the chromatic number of random geometric graphs, submitted for publication].     

A search for higher-dimensional arc planes

The concept of arc planes introduced byH. Groh (see [3]) has been extended to higher dimensions in [9]. By definition, a stable plane with point space ?^2l is an arc plane if all vector space translations are automorphisms. The lines are either affine subspaces or graphs of non-affine functions. We examine these functions, especially their domains, and obtain information restricting the search for examples. Roughly speaking, one should start with a translation plane and substitute some lines with the graphs of suitable functions.     

The limited Rademacher functions and Bernoulli convolutions associated with Pisot numbers

In this paper, we give a systematical study of the local structures and fractal indices of the limited Rademacher functions and Bernoulli convolutions associated with Pisot numbers. For a given Pisot number in the interval (1,2), we construct a finite family of non-negative matrices (maybe non-square), such that the corresponding fractal indices can be re-expressed as some limits in terms of products of these non-negative matrices. We are especially interested in the case that the associated Pisot number is a simple Pisot number, i.e., the unique positive root of the polynomial x^k-x^k-1-…-x-1 (k=2,3,…). In this case, the corresponding products of matrices can be decomposed into the products of scalars, based on which the precise formulas of fractal indices, as well as the multifractal formalism, are obtained.     

Circular representation problem on hypergraphs

A hypergraph J=(X,E) is said to be circular representable, if its vertices can be placed on a circle, in such way that every edge of H induces an interval. This concept is a translation into the vocabulary of hypergraphs of the circular one's property for the (0, 1) matrices [6] studied by Tucker [9, 10]. We give here a characterization of the hypergraphs which are circular representable. We study when the associated representation is unique, and we characterize the possible transformations of a representation into another, a kind of problem which has already been treated from the algorithmic point of view by Booth and Lueker [1] or Duchet [2] in the case of the interval representable hypergraphs.Finally, we establish a connection between circular graphs and circular representable hypergraphs of the type of the Fulkerson-Gross connection between interval graphs and matrices having the consecutive one's property [5], in some special cases.     

Spectral analysis of the affine graph over the finite ring

We apply two methods to the block diagonalization of the adjacency matrix of the Cayley graph defined on the affine group. The affine group will be defined over the finite ring Z/pⁿZ. The method of irreducible representations will allow us to find nontrivial eigenvalue bounds for two different graphs. One of these bounds will result in a family of Ramanujan graphs. The method of covering graphs will be used to block diagonalize the affine graphs using a Galois group of graph automorphisms. In addition, we will demonstrate the method of covering graphs on a generalized version of the graphs of Lubotzky et al. [A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261-277].     

Comment on “Based on interval type-2 adaptive fuzzy H∞ tracking controller for SISO time-delay nonlinear systems”

In this comment, we point out the inappropriateness of Theorem 1 in the article [Tsung-Chih Lin, Mehdi Roopaei. Based on interval type-2 adaptive fuzzy H^∞ tracking controller for SISO time-delay nonlinear systems. Commun Nonlinear Sci Numer Simulat 2010;15:4065–75]. For solving this problem, some formular mistakes are corrected and novel parameter adaptive laws of interval type-2 fuzzy neural network system are given.     

Graphs indecomposable with respect to the X-join

In his paper [3], Sabidussi defined the X-join of a family of graphs. This concept has also appeared in the work of Foulis and Randall on empirical logic [1,2]. In this paper, we investigate those graphs which do not have a nontrivial representation as the X-join of some family of graphs.     

Construction of a linear Pfaff system with <Emphasis Type="Italic">m</Emphasis>-dimensional time and with given characteristic set and lower characteristic set

For any positive integers n ≥ 1 and m ≥ 2, we give a constructive proof of the existence of linear n-dimensional Pfaff systems with m-dimensional time and with infinitely differentiable coefficient matrices such that the characteristic and lower characteristic sets of these systems are given sets that are the graphs of a concave continuous function and a convex continuous function, respectively, defined and monotone decreasing on simply connected closed bounded convex domains of the space ?^m?1.     

Chaos and fractals in fish school motion

The once abstract notions of fractal patterns and processes now appear naturally and inevitably in various chaotic dynamical systems. The examples range from Brownian motion [1], [2], [3], [4], [5] to the dynamics of social relations [6]. In this paper, after introducing a certain hybrid mathematical model of the plankton–fish school interplay, we study the fractal properties of the model fish school walks. We show that the complex planktivorous fish school motion is dependent on the fish predation rate. A decrease in the rate is followed by a transition from low-persistent to high-persistent fish school walks, i.e., from a motion with frequent to a motion with few changes of direction. The low-persistent motion shows fractal properties for all time scales, whereas the high-persistent motion has pronounced multifractal properties for large-scale displacements.     

Space–time symmetry,chaos and E infinity theory

We have studied the space–time symmetry of many-body systems, such as nucleon and quark systems, on the basis of chaos, viscous and E infinity theory. The mechanism of the space–time symmetry violation is attributed to the instability of chaotic orbit. The magnitude of space–time symmetry violation depends on the viscosity of many-body systems. We have shown that space–time symmetry is conserved in case of smaller viscosity (ν≲φ¹²=10⁻³ [m²/s]: strong interaction and electro-magnetic interaction) and violated in case of larger viscosity (ν≳φ⁰=1 [m²/s]: weak interaction). We have also obtained the simple relation between the viscosity (ν) of hadrons and the strength (α) of interactions; να=(1/10)φ²⁰∼(1/10)φ²⁴≃10⁻⁶∼10⁻⁷ [m²/s], where the symbol φ denotes the golden ratio. These values (ν and α) are shown to be reduced to the dimension of SO(n)[n=4+φ³].     

Algebraic multigrid methods for Laplacians of graphs

Classical algebraic multigrid theory relies on the fact that the system matrix is positive definite. We extend this theory to cover the positive semidefinite case as well, by formulating semiconvergence results for these singular systems. For the class of irreducible diagonal dominant singular M-matrices we show that the requirements of the developed theory hold and that the coarse level systems are still of the same class, if the C/F-splitting is good enough. An important example for matrices that are irreducible diagonal dominant M-matrices are Laplacians of graphs. Recent shape optimizing methods for graph partitioning require to solve singular linear systems involving these Laplacians. We present convergence results as well as experimental results for numerous graphs arising from finite element discretizations with up to 10⁶ vertices.     

Clustering of spectra and fractals of regular graphs

We exhibit a characteristic structure of the class of all regular graphs of degree d that stems from the spectra of their adjacency matrices. The structure has a fractal threadlike appearance. Points with coordinates given by the mean and variance of the exponentials of graph eigenvalues cluster around a line segment that we call a filar. Zooming-in reveals that this cluster splits into smaller segments (filars) labeled by the number of triangles in graphs. Further zooming-in shows that the smaller filars split into subfilars labeled by the number of quadrangles in graphs, etc. We call this fractal structure, discovered in a numerical experiment, a multifilar structure. We also provide a mathematical explanation of this phenomenon based on the Ihara-Selberg trace formula, and compute the coordinates and slopes of all filars in terms of Bessel functions of the first kind.     

Estimating the ultimate bound and positively invariant set for the Lorenz system and a unified chaotic system

To estimate the ultimate bound and positively invariant set for a dynamic system is an important but quite challenging task in general. In this paper, we attempt to investigate the ultimate bound and positively invariant set for two specific systems, the Lorenz system and a unified chaotic system. We derive an ellipsoidal estimate of the ultimate bound and positively invariant set for the Lorenz system, for all the positive values of its parameters a, b and c, and obtain the minimum value of volume for the ellipsoid. Comparing with the best results in the current literature [D. Li, J. Lu, X. Wu, G. Chen, Estimating the bounds for the Lorenz family of chaotic systems, Chaos Solitons Fractals 23 (2005) 529-534; X. Liao, On the global basin of attraction and positively invariant set for the Lorenz chaotic system and its application in chaos control and synchronization, Sci. China Ser. E 34 (2004) 1404-1419], our new results fill up the gap of the estimate for the cases of 0<a<1 and 0<b<2 [X. Liao, On the global basin of attraction and positively invariant set for the Lorenz chaotic system and its application in chaos control and synchronization, Sci. China Ser. E 34 (2004) 1404-1419]. Furthermore, the estimation derived here contains the results given in [D. Li, J. Lu, X. Wu, G. Chen, Estimating the bounds for the Lorenz family of chaotic systems, Chaos Solitons Fractals 23 (2005) 529-534] and [X. Liao, On the global basin of attraction and positively invariant set for the Lorenz chaotic system and its application in chaos control and synchronization, Sci. China Ser. E 34 (2004) 1404-1419] as special cases. Along the same line, we also provide estimates of cylindrical and ellipsoidal bounds for a unified chaotic system, for its parameter range , and obtain the minimum value of volume for the ellipsoid. The estimate is more accurate than and also extends the result of [D. Li, J. Lu, X. Wu, G. Chen, Estimating the bounds for the Lorenz family of chaotic systems, Chaos Solitons Fractals 23 (2005) 529-534] and [X. Liao, On the global basin of attraction and positively invariant set for the Lorenz chaotic system and its application in chaos control and synchronization, Sci. China Ser. E 34 (2004) 1404-1419].     

Flow Graphs: Analysis with Near Sets

This paper introduces a framework for flow graphs induced by perceptual systems as well as analysis of such graphs using near set theory. A distinctive feature of such graphs are layers; therefore we shall generally call them flow graphs with layers. In a specific context of perceptual systems, these graphs will referred be to as perceptual flow graphs. A method for determining nearness of flow graphs with layers (perceptual graphs) is given in terms of a practical application to digital image analysis.     

Projective connections in CR geometry

Holomorphic invariants of an analytic real hypersurface in ⁿ⁺¹ can be computed by several methods, coefficients of the Moser normal form [4], pseudo-con-formal curvature and its covariant derivatives [4], and projective curvature and its covariant derivatives [3]. The relation between these constructions is given in terms of reduction of the complex projective structure to a real form and exponentiation of complex vectorfields to give complex coordinate systems and corresponding Moser normal forms. Although the results hold for hypersurfaces with non-degenerate Levi-form, explicit formulas will be given only for the positive definite case.A. P. Sloan Fellow partially supported by N. S. F.     

Equivalences and the complete hierarchy of intersection graphs of paths in a tree

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted by [h,s,t]. It is well known that the class of chordal graphs corresponds to the class [3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-[3, 3, 1] graphs defined below.In this paper, we investigate the class of [h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1] graphs are also known as path graphs [F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211-227] or VPT graphs [M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151-159], and [h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t] by three main parameters: h, t and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, [h,2,t] and orthodox-[h,2,t] graphs for varied values of h and t.     

Matrix Maps of Quasi-Convex Null Sequences

In [7] Stieglitz and Tietz identify the space q ^α of all quasi-convex convergent sequences as a BK-space. They characterize all infinite matrices which map q ^α into an arbitrary FK-space. In [6] they do so for matrices which map a particular class of sequence spaces into q ^α . In [10] Zygmund introduces q ² in connexion with convergence factors of Fourier series. Dawson considers in [3] and [4] matrix maps of the space q ₀ ^α of all quasi-convex null sequences. In Section 2 we characterize all matrices which map q ₀ ^α into an arbitrary FK-space. Prior to that, a particular matrix map on q ₀ ^α gives us the BK-topology on q ₀ ^α . As an application we characterize in Section 3 the matrices which map q ₀ ^α into the FK-spaces considered by Stieglitz and Tietz in [8]. Based on [6], we determine the matrices which map these spaces into q ₀ ^α . Using methods similar to those in [7] our results in Section 2 depend on Theorems 2.1 and 4.1 in [5] due to Jakimovski and Livne. Theorem 2.1 gives for suitable pairs of sequence spaces necessary and sufficient conditions for an infinite matrix to map one space into the second one. In Theorem 4.1 a special sequence which is useful in applications of quasi-convexity is constructed. We close our paper with two remarks concerning three results in [8].     

Koszul duality in deformation quantization and Tamarkin's approach to Kontsevich formality

Let α be a quadratic Poisson bivector on a vector space V. Then one can also consider α as a quadratic Poisson bivector on the vector space V^∗[1]. Fixed a universal deformation quantization (prediction of some complex weights to all Kontsevich graphs [12]), we have deformation quantization of the both algebras S(V^∗) and Λ(V). These are graded quadratic algebras, and therefore Koszul algebras. We prove that for some universal deformation quantization, independent on α, these two algebras are Koszul dual. We characterize some deformation quantizations for which this theorem is true in the framework of the Tamarkin's theory [19].     

Once more on periodic products of groups and on a problem of A. I. Mal’tsev

A new operation of product of groups, the n-periodic product of groups for odd exponent n ≥ 665, was proposed by the author in 1976 in the paper [1]. This operation is described on the basis of the Novikov-Adyan theory introduced in the monograph [2] of the author. It differs from the classic operations of direct and free products of groups, but has all of the natural properties of these operations, including the so-called hereditary property for subgroups. Thus, the well-known problem of A. I. Mal’tsev on the existence of such new operations was solved. Unfortunately, in the paper [1], the case where the initial groups contain involutions, was not analyzed in detail. It is shown that, in the case where the initial groups contain involutions, this small gap is easily removed by an additional restriction on the choice of defining relations for the periodic product. It suffices to simply exclude products of two involutions of previous ranks from the inductive process of defining new relations for any given rank α. It is suggested that the adequacy of the given restriction follows easily from the proof of the key Lemma II.5.21 in the monograph [2]. We also mention that, with this additional restriction, all the properties of the periodic product given in [1] remain true with obvious corrections of their formulation. Moreover, under this restriction, one can consider n-periodic products for any period n ≥ 665, including even periods.