Graph operations that are good for greedoids

S is a local maximum stable set of a graph G, and we write S∈Ψ(G), if the set S is a maximum stable set of the subgraph induced by S∪N(S), where N(S) is the neighborhood of S. In Levit and Mandrescu (2002) [5] we have proved that Ψ(G) is a greedoid for every forest G. The cases of bipartite graphs and triangle-free graphs were analyzed in Levit and Mandrescu (2003) [6] and Levit and Mandrescu (2007) [7] respectively.In this paper we give necessary and sufficient conditions for Ψ(G) to form a greedoid, where G is:

(a)

the disjoint union of a family of graphs;

(b)

the Zykov sum of a family of graphs;

(c)

the corona X°{H₁,H₂,…,H_n} obtained by joining each vertex x of a graph X to all the vertices of a graph H_x.

     

Topological graph dimension

In the invited chapter Discrete Spatial Models of the book Handbook of Spatial Logics, we have introduced the concept of dimension for graphs, which is inspired by Evako’s idea of dimension of graphs [A.V. Evako, R. Kopperman, Y.V. Mukhin, Dimensional properties of graphs and digital spaces, J. Math. Imaging Vision 6 (1996) 109-119]. Our definition is analogous to that of (small inductive) dimension in topology. Besides the expected properties of isomorphism-invariance and monotonicity with respect to subgraph inclusion, it has the following distinctive features:

•

Local aspect. That is, dimension at a vertex is basic, and the dimension of a graph is obtained as the sup over its vertices.

•

Dimension of a strong product G×H is dim(G)+dim(H) (for non-empty graphs G,H).

In this paper we present a short account of the basic theory, with several new applications and results.     

Norm continuity of weakly continuous mappings into Banach spaces

Let T be the class of Banach spaces E for which every weakly continuous mapping from an α-favorable space to E is norm continuous at the points of a dense subset. We show that:

•

T contains all weakly Lindelöf Banach spaces;

•

l^∞∉T, which brings clarity to a concern expressed by Haydon ([R. Haydon, Baire trees, bad norms and the Namioka property, Mathematika 42 (1995) 30-42], pp. 30-31) about the need of additional set-theoretical assumptions for this conclusion. Also, (l^∞/c₀)∉T.

•

T is stable under weak homeomorphisms;

•

E∈T iff every quasi-continuous mapping from a complete metric space to (E,weak) is densely norm continuous;

•

E∈T iff every quasi-continuous mapping from a complete metric space to (E,weak) is weakly continuous at some point.

     

On the OBDD size for graphs of bounded tree- and clique-width

We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function f_G of a graph G on n vertices. Our results are as follows:

-

for graphs of bounded tree-width there is an OBDD of size O(logn) for f_G that uses encodings of size O(logn) for the vertices;

-

for graphs of bounded clique-width there is an OBDD of size O(n) for f_G that uses encodings of size O(n) for the vertices;

-

for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices;

-

for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel [R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132-1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor.

     

Spectral characterization of some weighted rooted graphs with cliques

The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph G obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which

(1)

the edges connecting vertices at consecutive levels have the same weight,

(2)

each set of children, in one or more levels, defines a weighted clique, and

(3)

cliques at the same level are isomorphic.

These eigenvalues are the eigenvalues of symmetric tridiagonal matrices of order Moreover, we give results on the multiplicity of the eigenvalues, on the spectral radii and on the algebraic conectivity. Finally, we apply the results to the unweighted case and some particular graphs are studied.     

The Fréchet-Urysohn property of Pixley-Roy hyperspaces

Let F[X] be the Pixley-Roy hyperspace of a regular space X. In this paper, we prove the following theorem.

Theorem. For a space X, the following are equivalent:

(1)

F[X]is a k-space;

(2)

F[X]is sequential;

(3)

F[X]is Fréchet-Urysohn;

(4)

Every finite power of X is Fréchet-Urysohn for finite sets;

(5)

Every finite power ofF[X]is Fréchet-Urysohn for finite sets.

As an application, we improve a metrization theorem onF[X].     

An “almost” full embedding of the category of graphs into the category of groups

We construct a functor F:Graphs→Groups which is faithful and “almost” full, in the sense that every nontrivial group homomorphism FX→FY is a composition of an inner automorphism of FY and a homomorphism of the form Ff, for a unique map of graphs f:X→Y. When F is composed with the Eilenberg-Mac Lane space construction K(FX,1) we obtain an embedding of the category of graphs into the unpointed homotopy category which is full up to null-homotopic maps.We provide several applications of this construction to localizations (i.e. idempotent functors); we show that the questions:

(1)

Is every orthogonality class reflective?

(2)

Is every orthogonality class a small-orthogonality class?

have the same answers in the category of groups as in the category of graphs. In other words they depend on set theory: (1) is equivalent to weak Vopěnka's principle and (2) to Vopěnka's principle. Additionally, the second question, considered in the homotopy category, is also equivalent to Vopěnka's principle.     

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

     

Continuity of posets via Scott topology and sobrification

In this paper, posets which may not be dcpos are considered. The concept of embedded bases for posets is introduced. Characterizations of continuity of posets in terms of embedded bases and Scott topology are given. The main results are:

(1)

A poset is continuous iff it is an embedded basis for a dcpo up to an isomorphism;

(2)

A poset is continuous iff its Scott topology is completely distributive;

(3)

A topological T₀ space is a continuous poset equipped with the Scott topology in the specialization order iff its topology is completely distributive and coarser than or equal to the Scott topology;

(4)

A topological T₁ space is a discrete space iff its topology is completely distributive.

These results generalize the relevant results obtained by J.D. Lawson for dcpos.     

A canonical form for nonderogatory matrices under unitary similarity

A square matrix is nonderogatory if its Jordan blocks have distinct eigenvalues. We give canonical forms for

•

nonderogatory complex matrices up to unitary similarity, and

•

pairs of complex matrices up to similarity, in which one matrix has distinct eigenvalues.

The types of these canonical forms are given by undirected and, respectively, directed graphs with no undirected cycles.     

Intersection cohomology of the circle actions

A classical result says that a free action of the circle S¹ on a topological space X is geometrically classified by the orbit space B and by a cohomological class e∈H²(B,Z), the Euler class. When the action is not free we have a difficult open question:

(Π)

“Is the space X determined by the orbit space B and the Euler class?”

The main result of this work is a step towards the understanding of the above question in the category of unfolded pseudomanifolds. We prove that the orbit space B and the Euler class determine:

•

the intersection cohomology of X,

•

the real homotopy type of X.

     

On the minimal members of convex expectations

In this paper, we show that for a convex expectation E[⋅] defined on L¹(Ω,F,P), the following statements are equivalent:

(i)

E is a minimal member of the set of all convex expectations defined on L¹(Ω,F,P);

(ii)

E is linear;

(iii)

two-dimensional Jensen inequality for E holds.

In addition, we prove a sandwich theorem for convex expectation and concave expectation.     

On some contributions of John Horváth to the theory of distributions

Our main task is a presentation of J. Horváth's results concerning

•

singular and hypersingular integral operators,

•

the analytic continuation of distribution-valued meromorphic functions, and

•

a general definition of the convolution of distributions.

At some instances minor supplements to his results are given.     

Canonical matrices of bilinear and sesquilinear forms

Canonical matrices are given for

(i)

bilinear forms over an algebraically closed or real closed field;

(ii)

sesquilinear forms over an algebraically closed field and over real quaternions with any nonidentity involution; and

(iii)

sesquilinear forms over a field F of characteristic different from 2 with involution (possibly, the identity) up to classification of Hermitian forms over finite extensions of F; the canonical matrices are based on any given set of canonical matrices for similarity over F.

A method for reducing the problem of classifying systems of forms and linear mappings to the problem of classifying systems of linear mappings is used to construct the canonical matrices. This method has its origins in representation theory and was devised in [V.V. Sergeichuk, Classification problems for systems of forms and linear mappings, Math. USSR-Izv. 31 (1988) 481-501].     

The Mukai pairing—II: the Hochschild-Kostant-Rosenberg isomorphism

We continue the study of the Hochschild structure of a smooth space that we began in our previous paper, examining implications of the Hochschild-Kostant-Rosenberg theorem. The main contributions of the present paper are:

•

we introduce a generalization of the usual notions of Mukai vector and Mukai pairing on differential forms that applies to arbitrary manifolds;

•

we give a proof of the fact that the natural Chern character map K₀(X)→HH₀(X) becomes, after the HKR isomorphism, the usual one ; and

•

we present a conjecture that relates the Hochschild and harmonic structures of a smooth space, similar in spirit to the Tsygan formality conjecture.