Hamilton decompositions of regular expanders: A proof of Kelly’s conjecture for large tournaments

A long-standing conjecture of Kelly states that every regular tournament on n$n$ vertices can be decomposed into (n−1)/2$(n-1)/2$ edge-disjoint Hamilton cycles. We prove this conjecture for large n$n$. In fact, we prove a far more general result, based on our recent concept of robust expansion and a new method for decomposing graphs. We show that every sufficiently large regular digraph G$G$ on n$n$ vertices whose degree is linear in n$n$ and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erd?s on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of Nash-Williams. We also apply our result to solve a problem on the domination ratio of the Asymmetric Travelling Salesman problem, which was raised e.g. by Glover and Punnen as well as Alon, Gutin and Krivelevich.     

Robust combinatorial optimization with variable cost uncertainty

We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates better Value-at-Risk objective functions, especially for vectors with few non-zero components. An example of budget function is constructed from the probabilistic bounds computed by Bertsimas and Sim. We provide an asymptotically tight bound for the cost reduction obtained with the new model. We turn then to the tractability of the resulting optimization problems. We show that when the budget function is affine, the resulting optimization problems can be solved by solving n+1$n+1$ deterministic problems. We propose combinatorial algorithms to handle problems with more general budget functions. We also adapt existing dynamic programming algorithms to solve faster the robust counterparts of optimization problems, which can be applied both to the traditional budgeted uncertainty model and to our new model. We evaluate numerically the reduction in the price of robustness obtained with the new model on the shortest path problem and on a survivable network design problem.     

Presenting higher stacks as simplicial schemes

We show that an n$n$-geometric stack may be regarded as a special kind of simplicial scheme, namely a Duskin n$n$-hypergroupoid in affine schemes, where surjectivity is defined in terms of covering maps, yielding Artin n$n$-stacks, Deligne–Mumford n$n$-stacks and n$n$-schemes as the notion of covering varies. This formulation adapts to all HAG contexts, so in particular works for derived n$n$-stacks (replacing rings with simplicial rings). We exploit this to describe quasi-coherent sheaves and complexes on these stacks, and to draw comparisons with Kontsevich’s dg-schemes. As an application, we show how the cotangent complex controls infinitesimal deformations of higher and derived stacks.     

Constructing uniform designs: A heuristic integer programming method

In this paper, the wrap-around _L2$L_2$-discrepancy (WD) of asymmetrical design is represented as a quadratic form, thus the problem of constructing a uniform design becomes a quadratic integer programming problem. By the theory of optimization, some theoretic properties are obtained. Algorithms for constructing uniform designs are then studied. When the number of runs n$n$ is smaller than the number of all level-combinations m$m$, the construction problem can be transferred to a zero–one quadratic integer programming problem, and an efficient algorithm based on the simulated annealing is proposed. When n≥m$n\ge m$, another algorithm is proposed. Empirical study shows that when n$n$ is large, the proposed algorithms can generate designs with lower WD compared to many existing methods. Moreover, these algorithms are suitable for constructing both symmetrical and asymmetrical designs.     

Submanifolds that are level sets of solutions to a second-order elliptic PDE

We consider the problem of characterizing which noncompact hypersurfaces in Rⁿ${\mathbb{R}}^n$ can be regular level sets of a harmonic function modulo a C^∞$C^{\infty }$ diffeomorphism, as well as certain generalizations to other PDEs. We prove a versatile sufficient condition that shows, in particular, that any nonsingular algebraic hypersurface whose connected components are all noncompact can be transformed onto a union of components of the zero set of a harmonic function via a diffeomorphism of Rⁿ${\mathbb{R}}^n$. The technique we use combines robust but not explicit local constructions with appropriate global approximation theorems. In view of applications to a problem posed by Berry and Dennis, intersections of level sets are also studied.     

A new method for computing Moore–Penrose inverse matrices

The Moore–Penrose inverse of an arbitrary matrix (including singular and rectangular) has many applications in statistics, prediction theory, control system analysis, curve fitting and numerical analysis. In this paper, an algorithm based on the conjugate Gram–Schmidt process and the Moore–Penrose inverse of partitioned matrices is proposed for computing the pseudoinverse of an m×n$m\times n$ real matrix A$A$ with m≥n$m\ge n$ and rank r≤n$r\le n$. Numerical experiments show that the resulting pseudoinverse matrix is reasonably accurate and its computation time is significantly less than that of pseudoinverses obtained by the other methods for large sparse matrices.     

High performance robust linear controller synthesis for an induction motor using a multi-objective hybrid control strategy

A robust induction motor control should provide the desired performance in the face of both plant model and controller model uncertainty. In a recent work, Bottura and co-workers, using the field orientation principle, introduced a representation of a nonlinear time-varying induction motor model that admits robust induction motor controller synthesis in the linear _H∞$H_{\infty }$ framework. The present work considers the use of the approach of Bottura et al. for attaining robust performance of the main operating modes–tracking and disturbance rejection–of an induction motor control system under implementation constraints on the control signal magnitude. This approach requires two distinct mode-specific controllers with gains that cannot be bridged without considerable performance degradation. To address this problem, a multi-objective hybrid control design methodology is developed that employs the corresponding mode-specific controller in each mode, and organizes a rapid and smooth steady-state switching, or transfer, between these controllers to permit sequencing of the operating modes, as necessary. Simulation shows that the technique proposed yields controllers with performance minimally affected by an imprecise modeling of an induction motor, as well as a reduced cost controller implementation throughout the entire induction motor operating sequence.     

Hardness of comparing two run-length encoded strings

In this paper, we consider a commonly used compression scheme called run-length encoding. We provide both lower and upper bounds for the problems of comparing two run-length encoded strings. Specifically, we prove the 3sum-hardness for both the wildcard matching problem and the k$k$-mismatch problem with run-length compressed inputs. Given two run-length encoded strings of m$m$ and n$n$ runs, such a result implies that it is very unlikely to devise an o(mn)$o\left(mn\right)$-time algorithm for either of them. We then present an inplace algorithm running in O(mnlogm)$O(mnlogm)$ time for their combined problem, i.e. k$k$-mismatch with wildcards. We further demonstrate that if the aim is to report the positions of all the occurrences, there exists a stronger barrier of Ω(mnlogm)$\Omega (mnlogm)$-time, matching the running time of our algorithm. Moreover, our algorithm can be easily generalized to a two-dimensional setting without impairing the time and space complexity.     

Robust utility maximization with limited downside risk in incomplete markets

In this article we consider the portfolio selection problem of an agent with robust preferences in the sense of Gilboa and Schmeidler [Itzhak Gilboa, David Schmeidler, Maxmin expected utility with non-unique prior, Journal of Mathematical Economics 18 (1989) 141–153] in an incomplete market. Downside risk is constrained by a robust version of utility-based shortfall risk. We derive an explicit representation of the optimal terminal wealth in terms of certain worst case measures which can be characterized as minimizers of a dual problem. This dual problem involves a three-dimensional analogue of f$f$-divergences which generalize the notion of relative entropy.     

Analysis of symmetric matrix valued functions I

For any symmetric function f:Rⁿ?Rⁿ$f:{\mathbb{R}}^n?{\mathbb{R}}^n$, one can define a corresponding function on the space of n×n$n\times n$ real symmetric matrices by applying f$f$ to the eigenvalues of the spectral decomposition. We show that this matrix valued function inherits from f$f$ the properties of continuity, Lipschitz continuity, strict continuity, directional differentiability, Frechet differentiability, continuous differentiability.     

Nonparametric estimation for pure jump Lévy processes based on high frequency data

In this paper, we study nonparametric estimation of the Lévy density for pure jump Lévy processes. We consider n$n$ discrete time observations with step Δ$\Delta$. The asymptotic framework is: n$n$ tends to infinity, Δ=_Δn$\Delta ={\Delta }_n$ tends to zero while n_Δn$n{\Delta }_n$ tends to infinity. First, we use a Fourier approach (“frequency domain”): this allows us to construct an adaptive nonparametric estimator and to provide a bound for the global L²${\mathbb{L}}^2$-risk. Second, we use a direct approach (“time domain”) which allows us to construct an estimator on a given compact interval. We provide a bound for L²${\mathbb{L}}^2$-risk restricted to the compact interval. We discuss rates of convergence and give examples and simulation results for processes fitting in our framework.     

Unsteady response of non-Newtonian blood flow through a stenosed artery in magnetic field

Current theoretical investigation of atherosclerotic arteries deals with mathematical models that represent non-Newtonian flow of blood through a stenosed artery in the presence of a transverse magnetic field. Here, the rheology of the flowing blood is characterised by a generalised Power law model. The distensibility of an arterial wall has been accounted for based on local fluid mechanics. A radial coordinate transformation is initiated to map cosine geometry of the stenosis into a rectangular grid. An appropriate finite difference scheme has been adopted to solve the unsteady non-Newtonian momentum equations in cylindrical coordinate system. Exploiting suitably prescribed conditions based on the assumption of an axial symmetry under laminar flow condition rendered the problem effectively to two dimensions. An extensive quantitative analysis has been performed based on numerical computations in order to estimate the effects of Hartmann number (M$M$), Power law index (n$n$), generalised Reynolds number (R_eG)$\left(R{e}_G\right)$, severity of the stenosis (δ)$\left(\delta \right)$ on various parameters such as flow velocity, flux and wall shear stress by means of their graphical representations so as to validate the applicability of the proposed mathematical model. The present results agree with some of the existing findings in the literature.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

Global convergence toward traveling fronts in nonlinear parabolic systems with a gradient structure

We consider nonlinear parabolic systems of the form ut=−∇V(u)+u_xx$u_t=-\mathrm{\nabla }V(u)+u_{xx}$, where u∈Rn$u\in {\mathbb{R}}^n$, n?1$n?1$, x∈R$x\in \mathbb{R}$, and the potential V   is coercive at infinity. For such systems, we prove a result of global convergence toward bistable fronts which states that invasion of a stable homogeneous equilibrium (a local minimum of the potential) necessarily occurs via a traveling front connecting to another (lower) equilibrium. This provides, for instance, a generalization of the global convergence result obtained by Fife and McLeod [P. Fife, J.B. McLeod, The approach of solutions of nonlinear diffusion equations to traveling front solutions, Arch. Rat. Mech. Anal. 65 (1977) 335–361] in the case n=1$n=1$. The proof is based purely on energy methods, it does not make use of comparison principles, which do not hold any more when n>1$n>1$.     

Incremental and encoding formulations for Mixed Integer Programming

The standard way to represent a choice between n$n$ alternatives in Mixed Integer Programming is through n$n$ binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this behavior. Through this framework, we generalize the incremental formulation for piecewise linear functions to any finite union of polyhedra with identical recession cones.     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.     

Homotopy method for solving variational inequalities with bounded box constraints

In this paper, using the Gabriel–Moré smoothing function of the median function, a smooth homotopy method for solving nonsmooth equation reformulation of bounded box constrained variational inequality problem VIP(l,u,F$l,u,F$) is given. Without any monotonicity condition on the defining map F$F$, for starting point chosen almost everywhere in Rⁿ$R^n$, existence and convergence of the homotopy pathway are proven. Nevertheless, it is also proven that, if the starting point is chosen to be an interior point of the box, the proposed homotopy method can also serve as an interior point method.     

Partial rigidity of degenerate CR embeddings into spheres

In this paper, we study degenerate CR embeddings f$f$ of a strictly pseudoconvex hypersurface M⊂Cⁿ⁺¹$M\subset {\mathbb{C}}^{n+1}$ into a sphere S$\mathbb{S}$ in a higher dimensional complex space C^N+1${\mathbb{C}}^{N+1}$. The degeneracy of the mapping f$f$ will be characterized in terms of the ranks of the CR second fundamental form and its covariant derivatives. In 2004, the author, together with X. Huang and D. Zaitsev, established a rigidity result for CR embeddings f$f$ into spheres in low codimensions. A key step in the proof of this result was to show that degenerate mappings are necessarily contained in a complex plane section of the target sphere (partial rigidity). In the 2004 paper, it was shown that if the total rank d$d$ of the second fundamental form and all of its covariant derivatives is <n$<n$ (here, n$n$ is the CR dimension of M$M$), then f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$. The converse of this statement is also true, as is easy to see. When the total rank d$d$ exceeds n$n$, it is no longer true, in general, that f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$, as can be seen by examples. In this paper, we carry out a systematic study of degenerate CR mappings into spheres. We show that when the ranks of the second fundamental form and its covariant derivatives exceed the CR dimension n$n$, then partial rigidity may still persist, but there is a “defect” k$k$ that arises from the ranks exceeding n$n$ such that f(M)$f\left(M\right)$ is only contained in a complex plane of dimension n+d+k+1$n+d+k+1$. Moreover, this defect occurs in general, as is illustrated by examples.