Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

For a set \(W\) of vertices of a connected graph \(G=(V(G),E(G))\) , a Steiner W-tree is a connected subgraph \(T\) of \(G\) such that \(W\subseteq V(T)\) and \(|E(T)|\) is minimum. Vertices in \(W\) are called terminals. In this work, we design an algorithm for the enumeration of all Steiner \(W\) -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner \(W\) -tree in polynomial time, our algorithm enumerates the remaining trees with \(O(n)\) delay (where \(n=|V(G)|\) ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given \(W\) and a vertex \(x\in V(G)\setminus W\) , is \(x\) in a Steiner \(W'\) -tree for some \(\emptyset \ne W' \subseteq W\) ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when \(W\) has arbitrary size. In addition, we prove that deciding whether \(x\) is in some Steiner \(W\) -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.     

Isomorphic Steiner symmetrization of p-convex sets

In this paper we show that given a \(p\) -convex set \(K \subset \mathbb{R }^n\) , there exist \(5n\) Steiner symmetrizations that transform it into an isomorphic Euclidean ball. That is, if \(|K| = |D_n| = \kappa _n\) , we may symmetrize it, using \(5n\) Steiner symmetrizations, into a set \(K'\) such that \(c_p D_n \subset K' \subset C_p D_n\) , where \(c_p\) and \(C_p\) are constants dependent on \(p\) only.     

Existence and regularity results for the Steiner problem

Given a complete metric space X and a compact set ${C\subset X}$ , the famous Steiner (or minimal connection) problem is that of finding a set S of minimum length (one-dimensional Hausdorff measure ${\mathcal H^1)}$ ) among the class of sets $$\mathcal{S}t(C) \,:=\{S\subset X\colon S \cup C \,{\rm is connected}\}.$$ In this paper we provide conditions on existence of minimizers and study topological regularity results for solutions of this problem. We also study the relationships between several similar variants of the Steiner problem. At last, we provide some applications to locally minimal sets.     

A new existence proof for Steiner quadruple systems

A Steiner quadruple system of order v is an ordered pair ${(X, \mathcal{B})}$ , where X is a set of cardinality v, and ${\mathcal{B}}$ is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in a unique block. Such designs exist if and only if ${v \equiv 2,4\, (\bmod\, 6)}$ . The first and second proofs of this result were given by Hanani in 1960 and in 1963, respectively. All the existing proofs are rather cumbersome, even though simplified proofs have been given by Lenz in 1985 and by Hartman in 1994. To study Steiner quadruple systems, Hanani introduced the concept of H-designs in 1963. The purpose of this paper is to provide an alternative existence proof for Steiner quadruple systems via H-designs of type 2 ⁿ . In 1990, Mills showed that for n > 3, n ≠ 5, an H-design of type g ⁿ exists if and only if ng is even and g(n ? 1)(n ? 2) is divisible by 3, where the main context is the complicated existence proof for H-designs of type 2 ⁿ . However, Mill’s proof was based on the existence result of Steiner quadruple systems. In this paper, by using the theory of candelabra systems and H-frames, we give a new existence proof for H-designs of type 2 ⁿ independent of the existence result of Steiner quadruple systems. As a consequence, we also provide a new existence proof for Steiner quadruple systems.     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.     

Euclidean Steiner trees optimal with respect to swapping 4-point subtrees

The Steiner tree problem in Euclidean space $E^3$ asks for a minimum length network $T$ , called a Euclidean Steiner Minimum Tree (ESMT), spanning a given set of points. This problem is NP-hard and the hardness is inherently due to the number of feasible topologies (underlying graph structure of $T$ ) which increases exponentially as the number of given points increases. Planarity is a very strong condition that gives a big difference between the ESMT problem in the Euclidean plane $E^2$ and in Euclidean $d$ -space $E^d (d\ge 3)$ : the ESMT problem in the plane is practically solvable whereas the ESMT problem in $d$ -space is really intractable. The simplest tree rearrangement technique is to repeatedly replace a subtree spanning four nodes in $T$ with another subtree spanning the same four nodes. This technique is referred to as the Swapping 4-point Topology/ Tree technique in this paper. An indicator (or quasi-indicator) of $T$ plays a similar role in the optimization of the length $L(T)$ of $T$ in the discrete topology space (the underlying graph structure of $T$ ) to the derivative of a differentiable function which indicates a fastest direction of descent. $T$ will be called S4pT-optimal if it is optimal with respect to swapping 4-point subtrees. In this paper we first make a complete analysis of 4-point trees in Euclidean space exploring all possible types of 4-point trees and their properties. We review some known indicators of 4-point ESMTs in $E^2$ , and give some simple geometric proofs of these indicators. Then, we translate these indicators to $E^3$ , producing eight quasi-indicators in $E^3$ using computational experiments, the best quasi-indicator $\rho _\mathrm{osr}$ is sifted with an effectiveness for randomly generated 4-point sets as high as 98.62 %. Finally we show how $\rho _\mathrm{osr}$ is used to find an S4pT-optimal ESMT on 14 probability vectors in $4d$ -space with a detailed example.     

Fourier analysis of subgroup conjugacy invariant functions on finite groups

Given a finite group $G$ and a subgroup $H\le G$ , we develop a Fourier analysis for $H$ -conjugacy invariant functions on $G$ , without the assumption that $H$ is a multiplicity-free subgroup of $G$ . We also study the Fourier transform for functions in the center of the algebra of $H$ -conjugacy invariant functions on $G$ . We show that a recent calculation of Cesi is indeed a Fourier transform of a function in the center of the algebra of functions on the symmetric group that are conjugacy invariant with respect to a Young subgroup.     

Bent functions embedded into the recursive framework of {\mathbb{Z}} -bent functions

Suppose that n is even. Let ${\mathbb{F}_2}$ denote the two-element field and ${\mathbb{Z}}$ the set of integers. Bent functions can be defined as ± 1-valued functions on ${\mathbb{F}_2^n}$ with ± 1-valued Fourier transform. More generally we call a mapping f on ${\mathbb{F}_2^n}$ a ${\mathbb{Z}}$ -bent function if both f and its Fourier transform ${\widehat{f}}$ are integer-valued. ${\mathbb{Z}}$ -bent functions f are separated into different levels, depending on the size of the maximal absolute value attained by f and ${\widehat{f}}$ . It is shown how ${\mathbb{Z}}$ -bent functions of lower level can be built up recursively by gluing together ${\mathbb{Z}}$ -bent functions of higher level. This recursion comes down at level zero, containing the usual bent functions. In the present paper we start to study bent functions in the framework of ${\mathbb{Z}}$ -bent functions and give some guidelines for further research.     

Steiner Triple Systems,Pinched Surfaces,and Complete Multigraphs

We consider complete multigraphs \({K_n^m}\) on n vertices with every pair joined by m edges. We embed these graphs to triangulate \({S_n^k}\) , a pinched surface with n pinch points each having k sheets. These embeddings have a vertex at each pinch point and any two sheets at a pinch point have the same number of edges. Moreover, we want to 2m-color the faces such that each color class is a Steiner triple system. These embeddings generalize in two ways biembeddings of Steiner triple systems, the case m =  1, k =  1 of simple graphs in surfaces without pinch points.     

Absence of wandering domains for some real entire functions with bounded singular sets

Let $f$ be a real entire function whose set $S(f)$ of singular values is real and bounded. We show that, if $f$ satisfies a certain function-theoretic condition (the “sector condition”), then $f$ has no wandering domains. Our result includes all maps of the form $z\mapsto \lambda \frac{\sinh (z)}{z} + a$ with $\lambda >0$ and $a\in \mathbb{R }$ . We also show the absence of wandering domains for certain non-real entire functions for which $S(f)$ is bounded and $f^n|_{S(f)}\rightarrow \infty $ uniformly. As a special case of our theorem, we give a short, elementary and non-technical proof that the Julia set of the exponential map $f(z)=e^z$ is the entire complex plane. Furthermore, we apply similar methods to extend a result of Bergweiler, concerning Baker domains of entire functions and their relation to the postsingular set, to the case of meromorphic functions.     

A sharp Blaschke–Santaló inequality for \alpha -concave functions

We define a new transform on \(\alpha \) -concave functions, which we call the \(\sharp \) -transform. Using this new transform, we prove a sharp Blaschke–Santaló inequality for \(\alpha \) -concave functions, and characterize the equality case. This extends the known functional Blaschke–Santaló inequality of Artstein-Avidan, Klartag and Milman, and strengthens a result of Bobkov. Finally, we prove that the \(\sharp \) -transform is a duality transform when restricted to its image. However, this transform is neither surjective nor injective on the entire class of \(\alpha \) -concave functions.     

Spherical functions associated with the three-dimensional sphere

In this paper, we determine all irreducible spherical functions \(\Phi \) of any \(K \) -type associated with the pair \((G,K)=(\mathrm{SO }(4),\mathrm{SO }(3))\) . This is accomplished by associating with \(\Phi \) a vector-valued function \(H=H(u)\) of a real variable \(u\) , which is analytic at \(u=0\) and whose components are solutions of two coupled systems of ordinary differential equations. By an appropriate conjugation involving Hahn polynomials, we uncouple one of the systems. Then, this is taken to an uncoupled system of hypergeometric equations, leading to a vector-valued solution \(P=P(u)\) , whose entries are Gegenbauer’s polynomials. Afterward, we identify those simultaneous solutions and use the representation theory of \(\mathrm{SO }(4)\) to characterize all irreducible spherical functions. The functions \(P=P(u)\) corresponding to the irreducible spherical functions of a fixed \(K\) -type \(\pi _\ell \) are appropriately packaged into a sequence of matrix-valued polynomials \((P_w)_{w\ge 0}\) of size \((\ell +1)\times (\ell +1)\) . Finally, we prove that \(\widetilde{P}_w={P_0}^{-1}P_w\) is a sequence of matrix orthogonal polynomials with respect to a weight matrix \(W\) . Moreover, we show that \(W\) admits a second-order symmetric hypergeometric operator \(\widetilde{D}\) and a first-order symmetric differential operator \(\widetilde{E}\) .     

Topological genericity of nowhere differentiable functions in the disc algebra

In this paper we introduce a class of functions contained in the disc algebra \({\mathcal{A}(D)}\) . We study functions \({f \in \mathcal{A}(D)}\) which have the property that the continuous periodic function \({u = {\rm Re}f|_{\mathbb{T}}}\) , where \({\mathbb{T}}\) is the unit circle, is nowhere differentiable. We prove that this class is non-empty and instead, generically, every function \({f \in \mathcal{A}(D)}\) has the above property. Afterwards, we strengthen this result by proving that, generically, for every function \({f \in \mathcal{A}(D)}\) , both continuous periodic functions \({u = {\rm Re}f|_\mathbb{T}}\) and \({\tilde{u} = {\rm Im}f|_\mathbb{T}}\) are nowhere differentiable. We avoid any use of the Weierstrass function and we mainly use Baire’s Category Theorem.     

Some Integral Representations and Singular Integral over Plane in Clifford Analysis

In this paper, Cauchy type integral and singular integral over hyper-complex plane \({\prod}\) are considered. By using a special Möbius transform, an equivalent relation between \({\widehat{H}^\mu}\) class functions over \({\prod}\) and \({H^\mu}\) class functions over the unit sphere is shown. For \({\widehat{H}^\mu}\) class functions over \({\prod}\) , we prove the existence of Cauchy type integral and singular integral over \({\prod}\) . Cauchy integral formulas as well as Poisson integral formulas for monogenic functions in upper-half and lower-half space are given respectively. By using Möbius transform again, the relation between the Cauchy type integrals and the singular integrals over \({\prod}\) and unit sphere is built.     

Forbidden configurations and Steiner designs

Let ${\mathcal{F}}$ be a (0, 1) matrix. A (0, 1) matrix ${\mathcal{M}}$ is said to have ${\mathcal{F}}$ as a configuration if there is a submatrix of ${\mathcal{M}}$ which is a row and column permutation of ${\mathcal{F}}$ . We say that a matrix ${\mathcal{M}}$ is simple if it has no repeated columns. For a given ${v \in \mathbb{N}}$ , we shall denote by forb ${(v, \mathcal{F})}$ the maximum number of columns in a simple (0, 1) matrix with v rows for which ${\mathcal{F}}$ does not occur as a configuration. We say that a matrix ${\mathcal{M}}$ is maximal for ${\mathcal{F}}$ if ${\mathcal{M}}$ has forb ${(v, \mathcal{F})}$ columns. In this paper we show that for certain natural choices of ${\mathcal{F}}$ , forb ${(v, \mathcal{F})\leq\frac{\binom{v}{t}}{t+1}}$ . In particular this gives an extremal characterization for Steiner t-designs as maximal (0, 1) matrices in terms of certain forbidden configurations.     

Harmonic functions of general graph Laplacians

We study harmonic functions on general weighted graphs which allow for a compatible intrinsic metric. We prove an \(L^{p}\) Liouville type theorem which is a quantitative integral \(L^{p}\) estimate of harmonic functions analogous to Karp’s theorem for Riemannian manifolds. As corollaries we obtain Yau’s \(L^{p}\) -Liouville type theorem on graphs, identify the domain of the generator of the semigroup on \(L^{p}\) and get a criterion for recurrence. As a side product, we show an analogue of Yau’s \(L^{p}\) Caccioppoli inequality. Furthermore, we derive various Liouville type results for harmonic functions on graphs and harmonic maps from graphs into Hadamard spaces.     

Frequent Hypercyclicity of Random Entire Functions for the Differentiation Operator

We study the random entire functions defined as power series \(f(z) = \sum _{n=0}^\infty (X_n/n!) z^n\) with independent and identically distributed coefficients \((X_n)\) and show that, under very weak assumptions, they are frequently hypercyclic for the differentiation operator \(D: H({\mathbb {C}}) \rightarrow H({\mathbb {C}}),\,f \mapsto Df = f'\) . This gives a very simple probabilistic construction of \(D\) -frequently hypercyclic functions in \(H({\mathbb {C}})\) . Moreover we show that, under more restrictive assumptions on the distribution of the \((X_n)\) , these random entire functions have a growth rate that differs from the slowest growth rate possible for \(D\) -frequently hypercyclic entire functions at most by a factor of a power of a logarithm.     

Semicontinuous limits of nets of continuous functions

In this paper we present a topology on the space of real-valued functions defined on a functionally Hausdorff space $X$ that is finer than the topology of pointwise convergence and for which (1) the closure of the set of continuous functions $\mathcal{C }(X)$ is the set of upper semicontinuous functions on $X$ , and (2) the pointwise convergence of a net in $\mathcal{C }(X)$ to an upper semicontinuous limit automatically ensures convergence in this finer topology.     

The k-error linear complexity distribution for 2^n-periodic binary sequences

The linear complexity and the \(k\) -error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By using the sieve method of combinatorics, we investigate the \(k\) -error linear complexity distribution of \(2^n\) -periodic binary sequences in this paper based on Games–Chan algorithm. First, for \(k=2,3\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences (with linear complexity less than \(2^n\) ) are characterized. Second, for \(k=3,4\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences with linear complexity \(2^n\) are presented. Third, as a consequence of these results, the counting functions for the number of \(2^n\) -periodic binary sequences with the \(k\) -error linear complexity for \(k = 2\) and \(3\) are obtained.     

Gevrey local solvability in locally integrable structures

We consider a locally integrable real-analytic structure, and we investigate the local solvability in the category of Gevrey functions and ultradistributions of the complex \(\mathrm{d}^{\prime }\) naturally induced by the de Rham complex. We prove that the so-called condition \(Y(q)\) on the signature of the Levi form, for local solvability of \(\mathrm{d}^{\prime }u=f\) , is still necessary even if we take \(f\) in the classes of Gevrey functions and look for solutions \(u\) in the corresponding spaces of ultradistributions.