Building blocks for the variety of absolute retracts

Given a graph H with a labelled subgraph G, a retraction of H to G is a homomorphism r:H→G such that r(x)=x for all vertices x in G. We call G a retract of H. While deciding the existence of a retraction to a fixed graph G is NP-complete in general, necessary and sufficient conditions have been provided for certain classes of graphs in terms of holes, see for example Hell and Rival.For any integer k?2 we describe a collection of graphs that generate the variety AR_k of graphs G with the property that G is a retract of H whenever G is a subgraph of H and no hole in G of size at most k is filled by a vertex of H. We also prove that AR_k⊂NUF_k+1, where NUF_k+1 is the variety of graphs that admit a near unanimity function of arity k+1.     

Selection over classes of ordinals expanded by monadic predicates

A monadic formula ψ(Y) is a selector for a monadic formula φ(Y) in a structure M if ψ defines in M a unique subset P of the domain and this P also satisfies φ in M. If C is a class of structures and φ is a selector for ψ in every M∈C, we say that φ is a selector for φ over C.For a monadic formula φ(X,Y) and ordinals α≤ω₁ and δ<ω^ω, we decide whether there exists a monadic formula ψ(X,Y) such that for every P⊆αof order-type smaller thanδ, ψ(P,Y) selects φ(P,Y) in (α,<). If so, we construct such a ψ.We introduce a criterion for a class C of ordinals to have the property that every monadic formula φ has a selector over it. We deduce the existence of S⊆ω^ω such that in the structure (ω^ω,<,S) every formula has a selector.Given a monadic sentence π and a monadic formula φ(Y), we decide whether φ has a selector over the class of countable ordinals satisfying π, and if so, construct one for it.     

On iterates of fully closed absolutes

In this article we give a sufficient condition for a space X to have the fully closed absolute faX with the property fa(faX)=faX. An example of a compact space X such that the canonical mapping fa(α+1)X→fa(α)X (where α is a given ordinal) is not a homeomorphism is constructed. Also we give an example of a compact space X such that the canonical mapping faX→X is not a homeomorphism but for which there exists a homeomorphism faX→X.     

A Sard theorem for tame set-valued mappings

If F is a set-valued mapping from Rn into Rm with closed graph, then y∈Rm is a critical value of F if for some x with y∈F(x), F is not metrically regular at (x,y). We prove that the set of critical values of a set-valued mapping whose graph is a definable (tame) set in an o-minimal structure containing additions and multiplications is a set of dimension not greater than m−1 (respectively a σ-porous set). As a corollary of this result we get that the collection of asymptotically critical values of a set-valued mapping with a semialgebraic graph has dimension not greater than m−1. We also give an independent proof of the fact that a definable continuous real-valued function is constant on components of the set of its subdifferentiably critical points.     

Perfect dexagon triple systems with given subsystems

The graph consisting of the six triples (or triangles) {a,b,c}, {c,d,e}, {e,f,a}, {x,a,y}, {x,c,z}, {x,e,w}, where a,b,c,d,e,f,x,y,z and w are distinct, is called a dexagon triple. In this case the six edges {a,c}, {c,e}, {e,a}, {x,a}, {x,c}, and {x,e} form a copy of K₄ and are called the inside edges of the dexagon triple. A dexagon triple system of order v is a pair (X,D), where D is a collection of edge disjoint dexagon triples which partitions the edge set of 3K_v. A dexagon triple system is said to be perfect if the inside copies of K₄ form a block design. In this note, we investigate the existence of a dexagon triple system with a subsystem. We show that the necessary conditions for the existence of a dexagon triple system of order v with a sub-dexagon triple system of order u are also sufficient.     

The forcing hull and forcing geodetic numbers of graphs

For every pair of vertices u,v in a graph, a u-v geodesic is a shortest path from u to v. For a graph G, let I_G[u,v] denote the set of all vertices lying on a u-v geodesic. Let S⊆V(G) and I_G[S] denote the union of all I_G[u,v] for all u,v∈S. A subset S⊆V(G) is a convex set of G if I_G[S]=S. A convex hull [S]_G of S is a minimum convex set containing S. A subset S of V(G) is a hull set of G if [S]_G=V(G). The hull number h(G) of a graph G is the minimum cardinality of a hull set in G. A subset S of V(G) is a geodetic set if I_G[S]=V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F⊆V(G) is called a forcing hull (or geodetic) subset of G if there exists a unique minimum hull (or geodetic) set containing F. The cardinality of a minimum forcing hull subset in G is called the forcing hull number f_h(G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number f_g(G) of G. In the paper, we construct some 2-connected graph G with (f_h(G),f_g(G))=(0,0),(1,0), or (0,1), and prove that, for any nonnegative integers a, b, and c with a+b≥2, there exists a 2-connected graph G with (f_h(G),f_g(G),h(G),g(G))=(a,b,a+b+c,a+2b+c) or (a,2a+b,a+b+c,2a+2b+c). These results confirm a conjecture of Chartrand and Zhang proposed in [G. Chartrand, P. Zhang, The forcing hull number of a graph, J. Combin. Math. Combin. Comput. 36 (2001) 81-94].     

Weak regularity and consecutive topologizations and regularizations of pretopologies

L. Foged proved that a weakly regular topology on a countable set is regular. In terms of convergence theory, this means that the topological reflection Tξ of a regular pretopology ξ on a countable set is regular. It is proved that this still holds if ξ is a regular σ-compact pretopology. On the other hand, it is proved that for each n<ω there is a (regular) pretopology ρ (on a set of cardinality c) such that k(RT)ρ>n(RT)ρ for each k<n and n(RT)ρ is a Hausdorff compact topology, where R is the reflector to regular pretopologies. It is also shown that there exists a regular pretopology of Hausdorff RT-order ?ω₀. Moreover, all these pretopologies have the property that all the points except one are topological and regular.     

Existence and convergence of best proximity points

Consider a self map T defined on the union of two subsets A and B of a metric space and satisfying T(A)⊆B and T(B)⊆A. We give some contraction type existence results for a best proximity point, that is, a point x such that d(x,Tx)=dist(A,B). We also give an algorithm to find a best proximity point for the map T in the setting of a uniformly convex Banach space.     

Parameter dependence of stable manifolds under nonuniform hyperbolicity

For a nonautonomous linear equation v^′=A(t)v in a Banach space with a nonuniform exponential dichotomy, we show that the nonlinear equation v^′=A(t)v+f(t,v,λ) has stable invariant manifolds Vλ which are Lipschitz in the parameter λ provided that f is a sufficiently small Lipschitz perturbation. Since any linear equation with nonzero Lyapunov exponents has a nonuniform exponential dichotomy, the above assumption is very general. We emphasize that passing from a classical uniform exponential dichotomy to a general nonuniform exponential dichotomy requires a substantially new approach.     

Degree sum and connectivity conditions for dominating cycles

For a graph G, let σ_k(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ₂(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ₃(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ₃(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ₄(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Subpullback flat S-posets need not be subequalizer flat

If S is a monoid, a right S-act A _S is a set A, equipped with a “right S-action” A×S→A sending the pair (a,s)∈ A×S to as, that satisfies the conditions (i) a(st)=(as)t and (ii) a1=a for all a∈A and s,t∈S. If, in addition, S is equipped with a compatible partial order and A is a poset, such that the action is monotone (when A×S is equipped with the product order), then A _S is called a right S-poset. Left S-acts and S-posets are defined analogously. For a given S-act (resp. S-poset) a tensor product functor A _S ?? from left S-acts to sets (resp. left S-posets to posets) exists, and A _S is called pullback flat or equalizer flat (resp. subpullback flat or subequalizer flat) if this functor preserves pullbacks or equalizers (resp. subpullbacks or subequalizers). By analogy with the Lazard-Govorov Theorem for R-modules, B. Stenström proved in 1971 that an S-act is isomorphic to a directed colimit of finitely generated free S -acts if and only if it is both pullback flat and equalizer flat. Some 20 years later, the present author showed that, in fact, pullback flatness by itself is sufficient. (A new, more direct proof of that result is contained in the present article.) In 2005, Valdis Laan and the present author obtained a version of the Lazard-Govorov Theorem for S-posets, in which subpullbacks and subequalizers now assume the role previously played by pullbacks and equalizers. The question of whether subpullback flatness implies subequalizer flatness remained unsolved. The present paper provides a negative answer to this question.     

Some bounds on the p-domination number in trees

Let p be a positive integer and G=(V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times, and S is a p-dependent set of G if the subgraph induced by the vertices of S has maximum degree at most p-1. The minimum cardinality of a p-dominating set a of G is the p-domination number γ_p(G) and the maximum cardinality of a p-dependent set of G is the p-dependence number β_p(G). For every positive integer p?2, we show that for a bipartite graph G, γ_p(G) is bounded above by (|V|+|Y_p|)/2, where Y_p is the set of vertices of G of degree at most p-1, and for every tree T, γ_p(T) is bounded below by β_p-1(T). Moreover, we characterize the trees achieving equality in each bound.     

On a cyclic connectivity property of directed graphs

Let us call a digraph D cycle-connected if for every pair of vertices u,v∈V(D) there exists a cycle containing both u and v. In this paper we study the following open problem introduced by Ádám. Let D be a cycle-connected digraph. Does there exist a universal edge in D, i.e., an edge e∈E(D) such that for every w∈V(D) there exists a cycle C such that w∈V(C) and e∈E(C)?In his 2001 paper Hetyei conjectured that cycle-connectivity always implies the existence of a universal edge. In the present paper we prove the conjecture of Hetyei for bitournaments.     

A characterization of block graphs

A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let N_e(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uv∈E(G), if x∈N_e(u) and y∈N_e(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22].     

On the precise growth, covering, and distortion theorems for normalized biholomorphic mappings

In this paper, we consider a normalized biholomorphic mapping f(x) defined on the unit ball in a complex Banach space, where the origin 0 is a zero of order k+1 of f(x)−x. The precise growth and covering theorem for f(x) is obtained when f(x) is a starlike mapping or a starlike mapping of order α. Especially, the precise growth and covering theorem for f(x) is also established when f(x) is a quasi-convex mapping. Moreover, the precise distortion theorem for f(x) is given when f(x) is a convex mapping. Our result includes many known results.     

Convexity properties of gradient maps

We consider the action of a real reductive group G on a Kähler manifold Z which is the restriction of a holomorphic action of a complex reductive group H. We assume that the action of a maximal compact subgroup U of H is Hamiltonian and that G is compatible with a Cartan decomposition of H. We have an associated gradient map μp:Z→p where g=k⊕p is the Cartan decomposition of g. For a G-stable subset Y of Z we consider convexity properties of the intersection of μp(Y) with a closed Weyl chamber in a maximal abelian subspace a of p. Our main result is a Convexity Theorem for real semi-algebraic subsets Y of Z=P(V) where V is a unitary representation of U.     

Gelfand pairs on the Heisenberg group and Schwartz functions

Let Hn be the (2n+1)-dimensional Heisenberg group and K a compact group of automorphisms of Hn such that (K?Hn,K) is a Gelfand pair. We prove that the Gelfand transform is a topological isomorphism between the space of K-invariant Schwartz functions on Hn and the space of Schwartz function on a closed subset of Rs homeomorphic to the Gelfand spectrum of the Banach algebra of K-invariant integrable functions on Hn.     

Groups of quasi-invariance and the Pontryagin duality

A Polish group G is called a group of quasi-invariance or a QI-group, if there exist a locally compact group X and a probability measure μ on X such that (1) there exists a continuous monomorphism ? from G into X with dense image, and (2) for each g∈X either g∈?(G) and the shift μg is equivalent to μ or g∉?(G) and μg is orthogonal to μ. It is proved that ?(G) is a σ-compact subset of X. We show that there exists a Polish non-locally quasi-convex (and hence nonreflexive) QI-group such that its bidual is not a QI-group. It is proved also that the bidual group of a QI-group may be not a saturated subgroup of X. It is constructed a reflexive non-discrete group topology on the integers.     

Quasi-kernels and quasi-sinks in infinite graphs

Given a directed graph G=(V,E) an independent set A⊂V is called quasi-kernel (quasi-sink) iff for each point v there is a path of length at most 2 from some point of A to v (from v to some point of A). Every finite directed graph has a quasi-kernel. The plain generalization for infinite graphs fails, even for tournaments. We study the following conjecture: for any digraph G=(V,E) there is a a partition (V₀,V₁) of the vertex set such that the induced subgraph G[V₀] has a quasi-kernel and the induced subgraph G[V₁] has a quasi-sink.