Forest embeddings in regular graphs of large girth

This paper deals with the enumeration of distinct embeddings (both induced and partial) of arbitrary graphs in regular graphs of large girth. A simple explicit recurrence formula is presented for the number of embeddings of an arbitrary forest F in an arbitrary regular graph G of sufficiently large girth. This formula (and hence the number of embeddings) depends only on the order and degree of regularity of G, and the degree sequence and component structure (multiset of component orders) of F. A concept called c-subgraph regularity is introduced which generalizes the familiar notion of regularity in graphs. (Informally, a graph is c-subgraph regular if its vertices cannot be distinguished on the basis of embeddings of graphs of order less than or equal to c.) A central result of this paper is that if G is regular and has girth g, then G is (g ? 1)-subgraph regular.     

Regularity for the evolution of p-harmonic maps

This paper presents our study of regularity for p-harmonic map heat flows. We devise a monotonicity-type formula of scaled energy and establish a criterion for a uniform regularity estimate for regular p-harmonic map heat flows. As application we show the small data global in the time existence of regular p-harmonic map heat flow.     

Weakly regular rings with ACC on annihilators and maximality of strongly prime ideals of weakly regular rings

Ramamurthi proved that weak regularity is equivalent to regularity and biregularity for left Artinian rings. We observe this result under a generalized condition. For a ring R satisfying the ACC on right annihilators, we actually prove that if R is left weakly regular then R is biregular, and that R is left weakly regular if and only if R is a direct sum of a finite number of simple rings. Next we study maximality of strongly prime ideals, showing that a reduced ring R is weakly regular if and only if R is left weakly regular if and only if R is left weakly π-regular if and only if every strongly prime ideal of R is maximal.     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.     

Delone Sets in ℝ<Superscript>3</Superscript> with 2<Emphasis Type="Italic">R</Emphasis>-Regularity Conditions

A regular system is the orbit of a point with respect to a crystallographic group. The central problem of the local theory of regular systems is to determine the value of the regularity radius, which is the least number such that every Delone set of type (r,R) with identical neighborhoods/clusters of this radius is regular. In this paper, conditions are described under which the regularity of a Delone set in three-dimensional Euclidean space follows from the pairwise congruence of small clusters of radius 2R. Combined with the analysis of one particular case, this result also implies the proof of the “10R-theorem,” which states that if the clusters of radius 10R in a Delone set are congruent, then this set is regular.     

Construction of {\mathcal L}^{{p}}-strong Feller Processes via Dirichlet Forms and Applications to Elliptic Diffusions

We provide a general construction scheme for $\mathcal L^p$ -strong Feller processes on locally compact separable metric spaces. Starting from a regular Dirichlet form and specified regularity assumptions, we construct an associated semigroup and resolvent of kernels having the $\mathcal L^p$ -strong Feller property. They allow us to construct a process which solves the corresponding martingale problem for all starting points from a known set, namely the set where the regularity assumptions hold. We apply this result to construct elliptic diffusions having locally Lipschitz matrix coefficients and singular drifts on general open sets with absorption at the boundary. In this application elliptic regularity results imply the desired regularity assumptions.     

Regular combinatorial maps

The classical approach to maps is by cell decomposition of a surface. A combinatorial map is a graph-theoretic generalization of a map on a surface. Besides maps on orientable and non-orientable surfaces, combinatorial maps include tessellations, hypermaps, higher dimensional analogues of maps, and certain toroidal complexes of Coxeter, Shephard, and Grünbaum. In a previous paper the incidence structure, diagram, and underlying topological space of a combinatorial map were investigated. This paper treats highly symmetric combinatorial maps. With regularity defined in terms of the automorphism group, necessary and sufficient conditions for a combinatorial map to be regular are given both graph- and group-theoretically. A classification of regular combinatorial maps on closed simply connected manifolds generalizes the well-known classification of metrically regular polytopes. On any closed manifold with nonzero Euler characteristic there are at most finitely many regular combinatorial maps. However, it is shown that, for nearly any diagram D, there are infinitely many regular combinatorial maps with diagram D. A necessary and sufficient condition for the regularity of rank 3 combinatorial maps is given in terms of Coxeter groups. This condition reveals the difficulty in classifying the regular maps on surfaces. In light of this difficulty an algorithm for generating a large class of regular combinatorial maps that are obtained as cyclic coverings of a given regular combinatorial map is given.     

A Lyusternik–Graves theorem for the proximal point method

We consider a generalized version of the proximal point algorithm for solving the perturbed inclusion y∈T(x), where y is a perturbation element near 0 and T is a set-valued mapping acting from a Banach space X to a Banach space Y which is metrically regular around some point $({\bar{x}},0)$ in its graph. We study the behavior of the convergent iterates generated by the algorithm and we prove that they inherit the regularity properties of T, and vice versa. We analyze the cases when the mapping T is metrically regular and strongly regular.     

Embedding maximal cliques of sets in maximal cliques of bigger sets

Characterizations are obtained of the maximal (k + s)-cliques that contain a given maximal k-clique as a substructure: (1) when s = 1; (2) for arbitrary s when no line of the clique contains exactly one point of the subclique. These characterizations are used to obtain maximal cliques which have fewer lines (for given k) than previously known examples.     

Reguläre Inzidenzkomplexe II

The concept of regular incidence complexes generalizes the notion of regular polyhedra in a combinatorial and grouptheoretical sense. A regular (incidence) complex K is a special type of partially ordered structure with regularity defined by the flag-transitivity of its group A(K) of automorphisms. The structure of a regular complex K can be characterized by certain sets of generators and ‘relations’ of its group. The barycentric subdivision of K leads to a simplicial complex, from which K can be rebuilt by fitting together faces. Moreover, we characterize the groups that act flag-transitively on regular complexes. Thus we have a correspondence between regular complexes on the one hand and certain groups on the other hand. Especially, this principle is used to give a geometric representation for an important class of regular complexes, the so-called regular incidence polytopes. There are certain universal incidence polytopes associated to Coxeter groups with linear diagram, from which each regular incidence polytope can be deduced by identifying faces. These incidence polytopes admit a geometric representation in the real space by convex cones.     

Jimmie D. Lawson on the occasion of his 75th birthday

In this paper we consider the Schwarz radical of linear algebraic semigroups as defined in semigroup theory. We give some new characterizations of the complete regularity, regularity and solvability of irreducible linear algebraic monoids in terms of Schwarz radical data. Moreover, we give a generalization about the results of the kernel to the results of completely regular \(\mathscr {J}\)-classes.     

Reguläre Inzidenzkomplexe III

The concept of regular incidence complexes generalizes the notion of regular polyhedra in a combinatorial and grouptheoretical sense. A regular (incidence) complex K of dimension d (or briefly a d-complex) is a special type of partially ordered set with regularity defined by the flag-transitivity of its group A(K) of automorphisms. The paper deals with the conjecture of Danzer, that every finite and non-degenerate regular d-complex K can be realized as a facet (that is a d-face) of a finite and non-degenerate regular (d+1)-complex L. At this non-degeneracy means the lattice property of the complex. Starting from a transformation of Danzer's problem into an embedding problem for the group of K we settle the conjecture for almost all complexes K by a suitable extension of A(K).     

On the failure of spectral synthesis for compact semisimple Lie groups

Let G be a compact connected semisimple Lie group with Lie algebra $\text{g}$. We show that the conjugacy class of a regular element of G is not a set of synthesis for the Fourier algebra of G. Similarly, the Ad(G)-orbit of a regular element of $\text{g}$ is not a set of synthesis for the algebra of Fourier transforms on $\text{g}$. In proving this latter result we demonstrate a regularity property of Ad-invariant Fourier transforms, analogous to the differentiability of radial Fourier transforms.     

An inertial proximal scheme for nonmonotone mappings

We present an inertial proximal method for solving an inclusion involving a nonmonotone set-valued mapping enjoying some regularity properties. More precisely, we investigate the local convergence of an implicit scheme for solving inclusions of the type T(x)∋0 where T is a set-valued mapping acting from a Banach space into itself. We consider subsequently the case when T is strongly metrically subregular, metrically regular and strongly regular around a solution to the inclusion. Finally, we study the convergence of our algorithm under variational perturbations.     

Decay and regularity in the inverse scattering problem

The regularity and decay properties for the potential q(x) in the Schrödinger equation ?ψ″ + qψ = k²ψ on the line are characterized in terms of the decay and regularity of the reflection coefficients R_± and their Fourier transforms.     

Magic square spectra

To study the eigenvalues of low order singular and non-singular magic squares we begin with some aspects of general square matrices. Additional properties follow for general semimagic squares (same row and column sums), with further properties for general magic squares (semimagic with same diagonal sums). Parameterizations of general magic squares for low orders are examined, including factorization of the linesum eigenvalue from the characteristic polynomial.For nth order natural magic squares with matrix elements 1,…,n² we find examples of some remarkably singular cases. All cases of the regular (or associative, or symmetric) type (antipodal pair sum of 1+n²) with n-1 zero eigenvalues have been found in the only complete sets of these squares (in fourth and fifth order). Both the Jordan form and singular value decomposition (SVD) have been useful in this study which examines examples up to 8th order.In fourth order these give examples illustrating a theorem by Mattingly that even order regular magic squares have a zero eigenvalue with odd algebraic multiplicity, m. We find 8 cases with m=3 which have a non-diagonal Jordan form. The regular group of 48 squares is completed by 40 squares with m=1, which are diagonable. A surprise finding is that the eigenvalues of 16 fourth order pandiagonal magic squares alternate between m=1, diagonable, and m=3, non-diagonable, on rotation by π/2. Two 8th order natural magic squares, one regular and the other pandiagonal, are also examined, found to have m=5, and to be diagonable.Mattingly also proved that odd order regular magic squares have a zero eigenvalue with even multiplicity, m=0,2,4,... Analyzing results for natural fifth order magic squares from exact backtracking calculations we find 652 with m=2, and four with m=4. There are also 20, 604 singular seventh order natural ultramagic (simultaneously regular and pandiagonal) squares with m=2, demonstrating that the co-existence of regularity and pandiagonality permits singularity. The singular odd order examples studied are all non-diagonable.     

Bounds for rectilinear crossing numbers

A rectilinear drawing of a graph is one where each edge is drawn as a straight-line segment, and the rectilinear crossing number of a graph is the minimum number of crossings over all rectilinear drawings. We describe, for every integer k ≥ 4, a class of graphs of crossing number k, but unbounded rectilinear crossing number. This is best possible since the rectilinear crossing number is equal to the crossing number whenever the latter is at most 3. Further, if we consider drawings where each edge is drawn as a polygonal line segment with at most one break point, then the resulting crossing number is at most quadratic in the regular crossing number. © 1993 John Wiley & Sons, Inc.     

Regularity of Segal algebras

Let A be a Banach algebra. The second dual A** can be equipped with two multiplications, each of which is a natural extension of the original multiplication in A. The algebra A is said to be Arens regular if these two multiplications coincide. We give necessary (and, for some classes of algebras, sufficient) conditions for the regularity of a Segal algebra. We also obtain necessary and sufficient conditions for the weak complete continuity of a Segal algebra.