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.

     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

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.

     

Left and right uniform structures on functionally balanced groups

Let G be a Hausdorff topological group. It is shown that there is a class C of subspaces of G, containing all (but not only) precompact subsets of G, for which the following result holds:Suppose that for every real-valued discontinuous function on G there is a set A∈C such that the restriction mapping f|A has no continuous extension to G; then the following are equivalent:

(i)

the left and right uniform structures of G are equivalent,

(ii)

every left uniformly continuous bounded real-valued function on G is right uniformly continuous,

(iii)

for every countable set A⊂G and every neighborhood V of the unit e of G, there is a neighborhood U of e in G such that AU⊂VA.

As a consequence, it is proved that items (i), (ii) and (iii) are equivalent for every inframetrizable group. These results generalize earlier ones established by Itzkowitz, Rothman, Strassberg and Wu, by Milnes and by Pestov for locally compact groups, by Protasov for almost metrizable groups, and by Troallic for groups that are quasi-k-spaces.     

From local to global similarity of matrix groups

Let G and H be groups of complex n×n matrices. We say that G is an H-like group if every matrix in G is similar to a matrix from H. For several groups H we consider two questions:

(A)

Is every H-like group (simultaneously) similar to a subgroup of H?

(B)

Is H the only H-like group containing H? Among other results we prove that the symmetric group S_n is the only S_n-like group containing S_n.

     

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.

     

A well-quasi-order for tournaments

A digraph H is immersed in a digraph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. For graphs the same relation (using paths instead of directed paths) is a well-quasi-order; that is, in every infinite set of graphs some one of them is immersed in some other. The same is not true for digraphs in general; but we show it is true for tournaments (a tournament is a directed complete graph).     

Local controllability and non-controllability for a 1D wave equation with bilinear control

We consider a linear wave equation, on the interval (0,1), with bilinear control and Neumann boundary conditions. We study the controllability of this nonlinear control system, locally around a constant reference trajectory. We prove that the following results hold generically.

•

For every T>2, this system is locally controllable in H³×H², in time T, with controls in L²((0,T),R).

•

For T=2, this system is locally controllable up to codimension one in H³×H², in time T, with controls in L²((0,T),R): the reachable set is (locally) a non-flat submanifold of H³×H² with codimension one.

•

For every T<2, this system is not locally controllable, more precisely, the reachable set, with controls in L²((0,T),R), is contained in a non-flat submanifold of H³×H², with infinite codimension.

The proof of these results relies on the inverse mapping theorem and second order expansions.     

Unprovability threshold for the planar graph minor theorem

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture (*): ‘there is a number a>0 such that for all k≥3, and all n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant (27.2269≤γ<30.061). Let P(c) be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G₁,G₂,…,G_N are unlabelled planar graphs with |G_i|<K+c⋅log₂i then for some i<j≤N, G_i is isomorphic to a minor of G_j”. Then

1.

for every , P(c) is provable in IΔ₀+exp;

2.

for every , P(c) is unprovable in .

We also give proofs of some upper and lower bounds for unprovability thresholds in the general case of the finite graph minor theorem.     

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).     

Distributing vertices along a Hamiltonian cycle in Dirac graphs

A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance is defined as the number of edges in a shortest path of G joining u and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are ω,n₀>0 such that if G is a Dirac graph on n≥n₀ vertices, d is an arbitrary integer with 3≤d≤ωn/2 and S is an arbitrary subset of the vertices of G with 2≤|S|=k≤ωn/d, then for every sequence d_i of integers with 3≤d_i≤d,1≤i≤k−1, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, a₁,a₂,…,a_k, such that the vertices of S are visited in this order on C and we have

     

Edge-disjoint spanners in tori

A spanning subgraph S=(V,E^′) of a connected graph G=(V,E) is an (x+c)-spanner if for any pair of vertices u and v, d_S(u,v)≤d_G(u,v)+c where d_G and d_S are the usual distance functions in G and S, respectively. The parameter c is called the delay of the spanner. We study edge-disjoint spanners in graphs in multi-dimensional tori. We show that each two-dimensional torus has a set of two edge-disjoint spanners of delay approximately the size of the smaller dimension. Moreover, we show that this delay is close to the best possible. In three-dimensional tori, we find a set of three edge-disjoint spanners with delay approximately the sum of the sizes of the two smaller dimensions when all dimensions are of even size. Surprisingly, we also find a set of two edge-disjoint spanners in three-dimensional tori of constant delay. In d-dimensional tori, we show that for any k≤d/5, there is a set of k edge-disjoint spanners with delay depending only on k and the size of the smaller k dimensions.     

Hamilton decompositions of graphs with primitive complements

A k-factor of a graph is a k-regular spanning subgraph. A Hamilton cycle is a connected 2-factor. A graph G is said to be primitive if it contains no k-factor with 1≤k<Δ(G). A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each of which induces a Hamilton cycle. In this paper, by using the amalgamation technique, we find necessary and sufficient conditions for the existence of a 2x-regular graph G on n vertices which:

1.

has a Hamilton decomposition, and

2.

has a complement in K_n that is primitive.

This extends the conditions studied by Hoffman, Rodger, and Rosa [D.G. Hoffman, C.A. Rodger, A. Rosa, Maximal sets of 2-factors and Hamiltonian cycles, J. Combin. Theory Ser. B 57 (1) (1993) 69-76] who considered maximal sets of Hamilton cycles and 2-factors. It also sheds light on construction approaches to the Hamilton-Waterloo problem.     

CLP-compactness for topological spaces and groups

We study CLP-compact spaces (every cover consisting of clopen sets has a finite subcover) and CLP-compact topological groups. In particular, we extend a theorem on CLP-compactness of products from [J. Steprāns, A. Šostak, Restricted compactness properties and their preservation under products, Topology Appl. 101 (3) (2000) 213-229] and we offer various criteria for CLP-compactness for spaces and topological groups, that work particularly well for precompact groups. This allows us to show that arbitrary products of CLP-compact pseudocompact groups are CLP-compact. For every natural n we construct:

(i)

a totally disconnected, n-dimensional, pseudocompact CLP-compact group; and

(ii)

a hereditarily disconnected, n-dimensional, totally minimal, CLP-compact group that can be chosen to be either separable metrizable or pseudocompact (a Hausdorff group G is totally minimal when all continuous surjective homomorphisms G→H, with a Hausdorff group H, are open).