Rudin's Dowker space, strong base-normality and base-strong-zero-dimensionality

It is well known that every pair of disjoint closed subsets F₀,F₁ of a normal T₁-space X admits a star-finite open cover U of X such that, for every U∈U, either or holds. We define a T₁-space X to be strongly base-normal if there is a base B for X with |B|=w(X) satisfying that every pair of disjoint closed subsets F₀,F₁ of X admits a star-finite cover B^′ of X by members of B such that, for every B∈B^′, either or holds. We prove that there is a base-normal space which is not strongly base-normal. Moreover, we show that Rudin's Dowker space is strongly base-(collectionwise)normal. Strong zero-dimensionality on base-normal spaces are also studied.     

On the spanning fan-connectivity of graphs

Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C_k(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k^∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ^∗(G), is the maximum integer k such that G is w^∗-connected for 1≤w≤k if G is 1^∗-connected.Let x be a vertex in G and let U={y₁,y₂,…,y_k} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, F_k(x,U), is a set of internally-disjoint paths {P₁,P₂,…,P_k} such that P_i is a path connecting x to y_i for 1≤i≤k and . A graph G is k^∗-fan-connected (or -connected) if there exists a spanning F_k(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ^∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k^∗-pipeline-connected.     

On closed invariant sets in local dynamics

We investigate the dynamical behaviour of a holomorphic map on an f-invariant subset C of U, where . We study two cases: when U is an open, connected and polynomially convex subset of Ck and C?U, closed in U, and when ∂U has a p.s.h. barrier at each of its points and C is not relatively compact in U. In the second part of the paper, we prove a Birkhoff's type theorem for holomorphic maps in several complex variables, i.e. given an injective holomorphic map f, defined in a neighborhood of , with U star-shaped and f(U) a Runge domain, we prove the existence of a unique, forward invariant, maximal, compact and connected subset of which touches ∂U.     

Vertex-transitive self-complementary uniform hypergraphs of prime order

For an integer n and a prime p, let . In this paper, we present a construction for vertex-transitive self-complementary k-uniform hypergraphs of order n for each integer n such that for every prime p, where ?=max{k₍₂₎,(k−1)₍₂₎}, and consequently we prove that the necessary conditions on the order of vertex-transitive self-complementary uniform hypergraphs of rank k=2^? or k=2^?+1 due to Potoňick and Šajna are sufficient. In addition, we use Burnside’s characterization of transitive groups of prime degree to characterize the structure of vertex-transitive self-complementary k-hypergraphs which have prime order p in the case where k=2^? or k=2^?+1 and , and we present an algorithm to generate all of these structures. We obtain a bound on the number of distinct vertex-transitive self-complementary graphs of prime order , up to isomorphism.     

Exposed sets in potential theory

Let U be a relatively compact open subset of a harmonic space, and H(U) be the function space of all continuous functions on which are harmonic on U. We give a complete characterization of the H(U)-exposed subsets of . This extends the results of [J. Lukeš, T. Mocek, M. Smr?ka, J. Spurný, Choquet like sets in function spaces, Bull. Sci. Math. 127 (2003) 397-437].     

A greedy approximation algorithm for the group Steiner problem

In the group Steiner problem we are given an edge-weighted graph G=(V,E,w) and m subsets of vertices . Each subset g_i is called a group and the vertices in ?_ig_i are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group.We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant ε>0, our algorithm gives an approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of in the approximation ratio, where |V| is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(max_i|g_i|)·logm) provided by the LP based approaches.     

Quartic, octic residues and Lucas sequences

Let be a prime and a,b∈Z with a²+b²≠p. Suppose p=x²+(a²+b²)y² for some integers x and y. In the paper we develop the calculation technique of quartic Jacobi symbols and use it to determine . As applications we obtain the congruences for modulo p and the criteria for (if ), where {Un} is the Lucas sequence given by U₀=0, U₁=1 and Un+1=bUn+k²Un−1(n?1). We also pose many conjectures concerning , or .     

Approximation algorithms for the minimum rainbow subgraph problem

We consider the minimum rainbow subgraph problem (MRS): given a graph G, whose edges are coloured with p colours. Find a subgraph F⊆G of G of minimum order and with p edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for Δ≥2.     

An edge-reduction algorithm for the vertex cover problem

An approximation algorithm for the vertex cover problem is proposed with performance ratio on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S₁ such that where S^∗ is an optimal cover and ξ is an error bound identified.     

On the quadratic character of quadratic units

Let be a prime. Let a,b∈Z with p?a(a²+b²). In the paper we mainly determine by assuming p=c²+d² or p=Ax²+2Bxy+Cy² with AC−B²=a²+b². As an application we obtain simple criteria for εD to be a quadratic residue , where D>1 is a squarefree integer such that D is a quadratic residue of p, εD is the fundamental unit of the quadratic field with negative norm. We also establish the congruences for and obtain a general criterion for p|U(p−1)/4, where {Un} is the Lucas sequence defined by U₀=0, U₁=1 and Un+1=bUn+k²Un−1(n?1).     

Truncated microsupport and holomorphic solutions of D-modules

We study the truncated microsupport SS_k of sheaves on a real manifold. Applying our results to the case of , the complex of holomorphic solutions of a coherent -module , we show that SS_k(F) is completely determined by the characteristic variety of . As an application, we obtain an extension theorem for the sections of H^j(F), j<d, defined on an open subset whose boundary is non-characteristic outside of a complex analytic subvariety of codimension d. We also give a characterization of the perversity for -constructible sheaves in terms of their truncated microsupports.     

Weakly sequentially continuous differentiable mappings

It is well known that a (linear) operator between Banach spaces is completely continuous if and only if its adjoint takes bounded subsets of Y^* into uniformly completely continuous subsets, often called (L)-subsets, of X^*. We give similar results for differentiable mappings. More precisely, if UX is an open convex subset, let be a differentiable mapping whose derivative is uniformly continuous on U-bounded subsets. We prove that f takes weak Cauchy U-bounded sequences into convergent sequences if and only if f^′ takes Rosenthal U-bounded subsets of U into uniformly completely continuous subsets of . As a consequence, we extend a result of P. Hájek and answer a question raised by R. Deville and E. Matheron. We derive differentiable characterizations of Banach spaces not containing ℓ₁ and of Banach spaces without the Schur property containing a copy of ℓ₁. Analogous results are given for differentiable mappings taking weakly convergent U-bounded sequences into convergent sequences. Finally, we show that if X has the hereditary Dunford–Pettis property, then every differentiable function as above is locally weakly sequentially continuous.     

On localization properties of Fourier transforms of hyperfunctions

In [A.G. Smirnov, Fourier transformation of Sato's hyperfunctions, Adv. Math. 196 (2005) 310-345] the author introduced a new generalized function space U(Rk) which can be naturally interpreted as the Fourier transform of the space of Sato's hyperfunctions on Rk. It was shown that all Gelfand-Shilov spaces (α>1) of analytic functionals are canonically embedded in U(Rk). While the usual definition of support of a generalized function is inapplicable to elements of and U(Rk), their localization properties can be consistently described using the concept of carrier cone introduced by Soloviev [M.A. Soloviev, Towards a generalized distribution formalism for gauge quantum fields, Lett. Math. Phys. 33 (1995) 49-59; M.A. Soloviev, An extension of distribution theory and of the Paley-Wiener-Schwartz theorem related to quantum gauge theory, Comm. Math. Phys. 184 (1997) 579-596]. In this paper, the relation between carrier cones of elements of and U(Rk) is studied. It is proved that an analytic functional is carried by a cone K⊂Rk if and only if its canonical image in U(Rk) is carried by K.     

Forbidden configurations and repeated induction

For a given k×? matrix F, we say a matrix A has no configurationF if no k×? submatrix of A is a row and column permutation of F. We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. We define as the maximum number of columns in an m-rowed simple matrix which has no configuration F. A fundamental result of Sauer, Perles and Shelah, and Vapnik and Chervonenkis determines exactly, where K_k denotes the k×2^k simple matrix. We extend this in several ways. For two matrices G,H on the same number of rows, let [G∣H] denote the concatenation of G and H. Our first two sets of results are exact bounds that find some matrices B,C where and . Our final result provides asymptotic boundary cases; namely matrices F for which is O(m^p) yet for any choice of column α not in F, we have is Ω(m^p+1). This is evidence for a conjecture of Anstee and Sali. The proof techniques in this paper are dominated by repeated use of the standard induction employed in forbidden configurations. Analysis of base cases tends to dominate the arguments. For a k-rowed (0,1)-matrix F, we also consider a function which is the minimum number of columns in an m-rowed simple matrix for which each k-set of rows contains F as a configuration.     

The approximation property for spaces of holomorphic functions on infinite dimensional spaces II

Let H(U) denote the vector space of all complex-valued holomorphic functions on an open subset U of a Banach space E. Let τω and τδ respectively denote the compact-ported topology and the bornological topology on H(U). We show that if E is a Banach space with a shrinking Schauder basis, and with the property that every continuous polynomial on E is weakly continuous on bounded sets, then (H(U),τω) and (H(U),τδ) have the approximation property for every open subset U of E. The classical space c₀, the original Tsirelson space T^∗ and the Tsirelson^∗-James space are examples of Banach spaces which satisfy the hypotheses of our main result. Our results are actually valid for Riemann domains.     

On finding a large number of 3D points with a small diameter

Given a set S of n points in R³, we wish to decide whether S has a subset of size at least k with Euclidean diameter at most r. It is unknown whether this decision problem is NP-hard. The two closely related optimization problems, (i) finding a largest subset of diameter at most r, and (ii) finding a subset of the smallest diameter of size at least k, were recently considered by Afshani and Chan. For maximizing the size, they presented several polynomial-time algorithms with constant approximation factors, the best of which has a factor of . For maximizing the diameter, they presented a polynomial-time approximation scheme. In this paper, we present improved approximation algorithms for both optimization problems. For maximizing the size, we present two algorithms: the first one improves the approximation factor to 2.5 and the running time by an O(n) factor; the second one improves the approximation factor to 2 and the running time by an O(n²) factor. For minimizing the diameter, we improve the running time of the PTAS from O(nlogn+2^O(1/ε3)n) to O(nlogn+2^{O(1/(ε1.5logε))}n).