Distances in orientations of graphs

We prove that there is a function h(k) such that every undirected graph G admits an orientation H with the following property: If an edge uv belongs to a cycle of length k in G, then uv or vu belongs to a directed cycle of length at most h(k) in H. Next, we show that every undirected bridgeless graph of radius r admits an orientation of radius at most r² + r, and this bound is best possible. We consider the same problem with radius replaced by diameter. Finilly, we show that the problem of deciding whether an undirected graph admits an orientation of diameter (resp. radius) 2 belongs to a class of problems called NP-hard.     

The multicovering radius problem for some types of discrete structures

The covering radius problem is a question in coding theory concerned with finding the minimum radius r such that, given a code that is a subset of an underlying metric space, balls of radius r over its code words cover the entire metric space. Klapper (IEEE Trans. Inform. Theory 43:1372–1377, 1997) introduced a code parameter, called the multicovering radius, which is a generalization of the covering radius. In this paper, we introduce an analogue of the multicovering radius for permutation codes (Des. Codes Cryptogr. 41:79–86, cf. 2006) and for codes of perfect matchings (cf. 2012). We apply probabilistic tools to give some lower bounds on the multicovering radii of these codes. In the process of obtaining these results, we also correct an error in the proof of the lower bound of the covering radius that appeared in (Des. Codes Cryptogr. 41:79–86, cf. 2006). We conclude with a discussion of the multicovering radius problem in an even more general context, which offers room for further research.     

Periodicity and Circle Packings of the Hyperbolic Plane

We prove that given a fixed radius r, the set of isometry-invariant probability measures supported on 'periodic' radius r-circle packings of the hyperbolic plane is dense in the space of all isometry-invariant probability measures on the space of radius r-circle packings. By a periodic packing, we mean one with cofinite symmetry group. As a corollary, we prove the maximum density achieved by isometry-invariant probability measures on a space of radius r-packings of the hyperbolic plane is the supremum of densities of periodic packings. We also show that the maximum density function varies continuously with radius.     

Brownian Motion and the Dirichlet Problem at Infinity on Two-dimensional Cartan-Hadamard Manifolds

After recalling the Dirichlet problem at infinity on a Cartan-Hadamard manifold, we describe what is known under various curvature assumptions and the difference between the two-dimensional and the higher-dimensional cases. We discuss the probabilistic formulation of the problem in terms of the asymptotic behavior of the angular component of Brownian motion. We then introduce a new (and appealing) probabilistic approach that allows us to prove that the Dirichlet problem at infinity on a two-dimensional Cartan-Hadamard manifold is solvable under the curvature condition K?≤?(1?+?ε)/(r ² logr) outside of a compact set, for some ε?>?0, in polar coordinates around some pole. This condition on the curvature is sharp, and improves upon the previously known case of quadratic curvature decay. Finally, we briefly discuss the issues which arise in trying to extend this method to higher dimensions.     

Elliptic control problems with gradient constraints—variational discrete versus piecewise constant controls

We consider an elliptic optimal control problem with pointwise bounds on the gradient of the state. To guarantee the required regularity of the state we include the L ^r -norm of the control in our cost functional with r>d (d=2,3). We investigate variational discretization of the control problem (Hinze in Comput. Optim. Appl. 30:45–63, 2005) as well as piecewise constant approximations of the control. In both cases we use standard piecewise linear and continuous finite elements for the discretization of the state. Pointwise bounds on the gradient of the discrete state are enforced element-wise. Error bounds for control and state are obtained in two and three space dimensions depending on the value of r.     

Fast directional algorithms for the Helmholtz kernel

This paper presents a new directional multilevel algorithm for solving N-body or N-point problems with highly oscillatory kernels. We address the problem by first proving that the interaction between a ball of radius r and a well-separated region has an approximate low rank representation, as long as the well-separated region belongs to a cone with a spanning angle of O(1/r) and is at a distance which is at least O(r²) away from the ball. Based on this representation, our algorithm organizes the high frequency computation using a multidirectional and multiscale strategy. Our algorithm is proved to have an optimal O(NlogN) computational complexity for any given accuracy when the points are sampled from a two-dimensional surface.     

Rainbow Connection Number and Radius

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) ≤  r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K _1,n for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) ≤  rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 ? 1, where n is order of the graph (Caro et al. in Electron J Comb 15(1):Research paper 57, 13, 2008). It is known that computing rc(G) is NP-Hard (Chakraborty and fischer in J Comb Optim 1–18, 2009). Here, we present a (r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r.     

Minimal cubature formulas of degree 3 for a torus in ℝ<Superscript>3</Superscript>

We construct minimal cubature formulas of degree 3 for a torus in R³. The cases of a degenerate torus with radius r = 1 and a torus with arbitrary radius r > 1 are considered separately.     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.     

Optimal reconstruction of the solution of the Dirichlet problem from inaccurate input data

In this paper, we consider the optimal reconstruction of the solution of the Dirichlet problem in the d-dimensional ball on the sphere of radius r from inaccurately prescribed traces of the solution on the spheres of radii R ₁ and R ₂, where R ₁ < r < R ₂. We also study the optimal reconstruction of the solution of the Dirichlet problem in the d-dimensional ball from a finite collection of Fourier coefficients of the boundary function which are prescribed with an error in the mean-square and uniform metrics.     

Determinantal varieties over truncated polynomial rings

We study components and dimensions of higher-order determinantal varieties obtained by considering generic m×n (m?n) matrices over rings of the form F[t]/(t^k), and for some fixed r, setting the coefficients of powers of t of all r×r minors to zero. These varieties can be interpreted as spaces of (k−1)th order jets over the classical determinantal varieties; a special case of these varieties first appeared in a problem in commuting matrices. We show that when r=m, the varieties are irreducible, but when r<m, these varieties are reducible. We show that when r=2<m (any k), there are exactly ⌊k/2⌋+1 components, which we determine explicitly, and for general r<m, we show there are at least ⌊k/2⌋+1 components. We also determine the components explicitly for k=2 and 3 for all values of r (for k=3 for all but finitely many pairs of (m,n)).     

Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

Allocation strategies in hub networks

In this paper, we study allocation strategies and their effects on total routing costs in hub networks. Given a set of nodes with pairwise traffic demands, the p-hub median problem is the problem of choosing p nodes as hub locations and routing traffic through these hubs at minimum cost. This problem has two versions; in single allocation problems, each node can send and receive traffic through a single hub, whereas in multiple allocation problems, there is no such restriction and a node may send and receive its traffic through all p hubs. This results in high fixed costs and complicated networks. In this study, we introduce the r-allocation p-hub median problem, where each node can be connected to at most r hubs. This new problem generalizes the two versions of the p-hub median problem. We derive mixed-integer programming formulations for this problem and perform a computational study using well-known datasets. For these datasets, we conclude that single allocation solutions are considerably more expensive than multiple allocation solutions, but significant savings can be achieved by allowing nodes to be allocated to two or three hubs rather than one. We also present models for variations of this problem with service quality considerations, flow thresholds, and non-stop service.     

Non-homogeneous Tb Theorem and Random Dyadic Cubes on Metric Measure Spaces

We prove a Tb theorem on quasimetric spaces equipped with what we call an upper doubling measure. This is a property that encompasses both the doubling measures and those satisfying the upper power bound ??(B(x,r))??Cr ^d . Our spaces are only assumed to satisfy the geometric doubling property: every ball of radius r can be covered by at most N balls of radius r/2. A key ingredient is the construction of random systems of dyadic cubes in such spaces.     

On second-order nonlinearity and maximum algebraic immunity of some bent functions in \mathcal{PS}^{+}

The rth-order nonlinearity and algebraic immunity of Boolean function play a central role against several known attacks on stream and block ciphers. Since its maximum equals the covering radius of the rth-order Reed-Muller code, it also plays an important role in coding theory. The computation of exact value or high lower bound on the rth-order nonlinearity of a Boolean function is very complected/challenging problem, especially when r>1. In this article, we identify a subclass of \({\mathcal{D}}_{0}\) type bent functions constructed by modifying well known Dillon functions having sharper bound on their second-order nonlinearity. We further, identify a subclass of bent functions in \({\mathcal {PS}}^{+}\) class with maximum possible algebraic immunity. The result is proved by using the well known conjecture proposed by Tu and Deng (Des. Codes Cryptogr. 60(1):1–14, 2011). To obtain rth-order nonlinearity (r>2), that is, whole nonlinearity profile of the constructed bent functions is still an open problem.     

Volumetric bounds for intersections of congruent balls in Euclidean spaces

We investigate the intersections of balls of radius r, called r-ball bodies, in Euclidean d-space. An r-lense (resp., r-spindle) is the intersection of two balls of radius r (resp., balls of radius r containing a given pair of points). We prove that among r-ball bodies of a given volume, the r-lense (resp., r-spindle) has the smallest inradius (resp., largest circumradius). In general, we upper (resp., lower) bound the intrinsic volumes of r-ball bodies of a given inradius (resp., circumradius). This complements and extends some earlier results on volumetric estimates for r-ball bodies.

     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

A Characterization of Graphs Where the Independence Number Equals the Radius

In a classical 1986 paper by Erdös, Saks and Saós every graph of radius r has an induced path of order at least 2r ? 1. This result implies that the independence number of such graphs is at least r. In this paper, we use a result of S. Fajtlowicz about radius-critical graphs to characterize graphs where the independence number is equal to the radius, for all possible values of the radius except 2, 3, and 4. We briefly discuss these remaining cases as well.     

On entire functions with zero as a deficient value

We consider entire functions of finite order for which zero is a Nevanlinna deficient value. Estimates are determined for the ratio of the integrated moduli of the logarithmic derivative of the function on a circle of radius r to the Nevanlinna characteristic of the function at r.