Quick Max-flow Algorithm

Determining of a maximal network flow is a classic problem in discrete optimization with many applications. In this paper, a new algorithm based on the Dinic’s method is presented. Algorithms of the Dinic’s method work evidently faster than theoretical bounds for a randomized network. This paper presents a parameterized and easy to implement family of algorithms of finding a saturating flow in a layered network. Although their common complexity is poor O(V ² L) where L is the number of layers, three particular members are proved to be O(V ²). Furthermore, there is a particularly interesting “balanced” member of the family for which a calculated upper bound on complexity is still O(V ² L) but there is known no example of a layered network that needs more than O(E + V ^(3/2)) time to resolve. All the considered members work really quickly for randomized examples of a layered network. Starting from the above family, three algorithms which find maximal flow in a network in O(V ³) worst case time have been constructed, while the respective “balanced” algorithm is theoretically O(V ⁴). All the algorithms do not extend O(V ²) time in experimental, i.e. randomized, cases.      

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

Analysis of space–time discontinuous Galerkin method for nonlinear convection–diffusion problems

The paper presents the theory of the discontinuous Galerkin finite element method for the space–time discretization of a nonstationary convection–diffusion initial-boundary value problem with nonlinear convection and linear diffusion. The problem is not singularly perturbed with dominating convection. The discontinuous Galerkin method is applied separately in space and time using, in general, different space grids on different time levels and different polynomial degrees p and q in space and time dicretization. In the space discretization the nonsymmetric, symmetric and incomplete interior and boundary penalty (NIPG, SIPG, IIPG) approximation of diffusion terms is used. The paper is concerned with the proof of error estimates in “L ²(L ²)”- and “DG”-norm formed by the “L ²(H ¹)”-seminorm and penalty terms. A special technique based on the use of the Gauss–Radau interpolation and numerical integration has been used for the derivation of an abstract error estimate. In the “DG”-norm the error estimates are optimal with respect to the size of the space grid. They are optimal with respect to the time step, if the Dirichlet boundary condition has behaviour in time as a polynomial of degree ≤ q.     

The Moduli Space of Curves, Double Hurwitz Numbers, and Faber��s Intersection Number Conjecture

We define the dimension 2g − 1 Faber-Hurwitz Chow/homology classes on the moduli space of curves, parametrizing curves expressible as branched covers of \mathbbP₁{{\mathbb{P}_1}} with given ramification over ∞ and sufficiently many fixed ramification points elsewhere. Degeneration of the target and judicious localization expresses such classes in terms of localization trees weighted by “top intersections” of tautological classes and genus 0 double Hurwitz numbers. This identity of generating series can be inverted, yielding a “combinatorialization” of top intersections of Y{\Psi} -classes. As genus 0 double Hurwitz numbers with at most 3 parts over ∞ are well understood, we obtain Faber’s Intersection Number Conjecture for up to 3 parts, and an approach to the Conjecture in general (bypassing the Virasoro Conjecture). We also recover other geometric results in a unified manner, including Looijenga’s theorem, the socle theorem for curves with rational tails, and the hyperelliptic locus in terms of κ _g–2.     

A KAM phenomenon for singular holomorphic vector fields

Let X be a germ of holomorphic vector field at the origin of Cⁿ and vanishing there. We assume that X is a good perturbation of a “nondegenerate” singular completely integrable system. The latter is associated to a family of linear diagonal vector fields which is assumed to have nontrivial polynomial first integrals (they are generated by the so called “resonant monomials”). We show that X admits many invariant analytic subsets in a neighborhood of the origin. These are biholomorphic to the intersection of a polydisc with an analytic set of the form “resonant monomials = constants”. Such a biholomorphism conjugates the restriction of X to one of its invariant varieties to the restriction of a linear diagonal vector field to a toric variety. Moreover, we show that the set of “frequencies” defining the invariant sets is of positive measure.     

On Rich Lines in Grids

In this paper we show that if one has a grid A×B, where A and B are sets of n real numbers, then there can be only very few “rich” lines in certain quite small families. Indeed, we show that if the family has lines taking on n ^ε distinct slopes, and where each line is parallel to n ^ε others (so, at least n ^2ε lines in total), then at least one of these lines must fail to be “rich”. This result immediately implies non-trivial sumproduct inequalities; though, our proof makes use of the Szemeredi-Trotter inequality, which Elekes used in his argument for lower bounds on |C+C|+|C.C|.     

New cubature formulae and hyperinterpolation in three variables

A new algebraic cubature formula of degree 2n+1 for the product Chebyshev measure in the d-cube with ≈n ^d /2 ^d−1 nodes is established. The new formula is then applied to polynomial hyperinterpolation of degree n in three variables, in which coefficients of the product Chebyshev orthonormal basis are computed by a fast algorithm based on the 3-dimensional FFT. Moreover, integration of the hyperinterpolant provides a new Clenshaw-Curtis type cubature formula in the 3-cube. Work supported by the National Science Foundation under Grant DMS-0604056, by the “ex-60%” funds of the Universities of Padova and Verona, and by the INdAM-GNCS.     

A helly-number fork-almost-neighborly sets

It is possible to prove the following “Helly-type” thorem fork-almost-neighborly sets. Theorem.A ⊆R ^d is k-almost-neighborly if and only if every 2d+1 member subset of A is k-almost-neighborly. Moreover, if A ⊆bdry conv A, then A is k-almost-neighborly if and only if every 2d member subset of A is k-almost-neighborly. Each bound is best possible.     

The van Kampen obstruction and its relatives

We review a cochain-free treatment of the classical van Kampen obstruction ϑ to embeddability of an n-polyhedron in ℝ²ⁿ and consider several analogs and generalizations of ϑ, including an extraordinary lift of ϑ, which has been studied by J.-P. Dax in the manifold case. The following results are obtained: (1) The mod 2 reduction of ϑ is incomplete, which answers a question of Sarkaria. (2) An odd-dimensional analog of ϑ is a complete obstruction to linkless embeddability (=“intrinsic unlinking”) of a given n-polyhedron in ℝ²ⁿ⁺¹. (3) A “blown-up” one-parameter version of ϑ is a universal type 1 invariant of singular knots, i.e., knots in ℝ³ with a finite number of rigid transverse double points. We use it to decide in simple homological terms when a given integer-valued type 1 invariant of singular knots admits an integral arrow diagram (= Polyak-Viro) formula. (4) Settling a problem of Yashchenko in the metastable range, we find that every PL manifold N nonembeddable in a given ℝ ^m , m ≥ $ \frac{{3(n + 1)}} {2} $ \frac{{3(n + 1)}} {2} , contains a subset X such that no map N → ℝ ^m sends X and N \ X to disjoint sets. (5) We elaborate on McCrory’s analysis of the Zeeman spectral sequence to geometrically characterize “k-co-connected and locally k-co-connected” polyhedra, which we embed in ℝ2 ^n−k for k < $ \frac{{n - 3}} {2} $ \frac{{n - 3}} {2} , thus extending the Penrose-Whitehead-Zeeman theorem.     

On Small World Semiplanes with Generalised Schubert Cells

The well known “real-life examples” of small world graphs, including the graph of binary relation: “two persons on the earth know each other” contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised polygons, which are small world algebraic graphs i.e. graphs with the diameter d≤clog  _k−1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these conditions with the degree ≥k and the diameter ≥d for each pair k≥3 and d≥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised largest Schubert cells, is isomorphic to the well-known Wenger’s graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q ⁿ , where integer n≥2 and q is prime power, q≥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small cycles to Cryptography and Coding Theory.     

Super-Brownian motion with reflecting historical paths

We consider super-Brownian motion whose historical paths reflect from each other, unlike those of the usual historical super-Brownian motion. We prove tightness for the family of distributions corresponding to a sequence of discrete approximations but we leave the problem of uniqueness of the limit open. We prove a few results about path behavior for processes under any limit distribution. In particular, we show that for any γ > 0, a “typical” increment of a reflecting historical path over a small time interval Δt is not greater than (Δt)^3/4−γ. Received: 16 March 2000 / Revised version: 26 February 2001 / Published online: 9 October 2001     

Chern-Simons invariant and conformal embedding of a 3-manifold

This note studies the Chern-Simons invariant of a closed oriented Riemannian 3-manifold M. The first achievement is to establish the formula CS（e） - CS（e） = degA, where e and e are two （global） frames of M, and A ： M → SO（3） is the ＂difference＂ map. An interesting phenomenon is that the ＂jumps＂ of the Chern-Simons integrals for various frames of many 3-manifolds are at least two, instead of one. The second purpose is to give an explicit representation of CS（e＋） and CS（e_）, where e＋ and e_ are the ＂left＂ and ＂right＂ quaternionic frames on M3 induced from an immersion M^3 → E^4, respectively. Consequently we find many metrics on S^3 （Berger spheres） so that they can not be conformally embedded in E^4.     

Unchained polygons and the N-body problem

We study both theoretically and numerically the Lyapunov families which bifurcate in the vertical direction from a horizontal relative equilibrium in ℝ³. As explained in [1], very symmetric relative equilibria thus give rise to some recently studied classes of periodic solutions. We discuss the possibility of continuing these families globally as action minimizers in a rotating frame where they become periodic solutions with particular symmetries. A first step is to give estimates on intervals of the frame rotation frequency over which the relative equilibrium is the sole absolute action minimizer: this is done by generalizing to an arbitrary relative equilibrium the method used in [2] by V. Batutello and S. Terracini. In the second part, we focus on the relative equilibrium of the equal-mass regular N-gon. The proof of the local existence of the vertical Lyapunov families relies on the fact that the restriction to the corresponding directions of the quadratic part of the energy is positive definite. We compute the symmetry groups G _r/s (N, k, η) of the vertical Lyapunov families observed in appropriate rotating frames, and use them for continuing the families globally. The paradigmatic examples are the “Eight” families for an odd number of bodies and the “Hip- Hop” families for an even number. The first ones generalize Marchal’s P ₁₂ family for 3 bodies, which starts with the equilateral triangle and ends with the Eight [1, 3–6]; the second ones generalize the Hip-Hop family for 4 bodies, which starts from the square and ends with the Hip-Hop [1, 7, 8]. We argue that it is precisely for these two families that global minimization may be used. In the other cases, obstructions to the method come from isomorphisms between the symmetries of different families; this is the case for the so-called “chain” choreographies (see [6]), where only a local minimization property is true (except for N = 3). Another interesting feature of these chains is the deciding role played by the parity, in particular through the value of the angular momentum. For the Lyapunov families bifurcating from the regular N-gon whith N ≤ 6 we check in an appendix that locally the torsion is not zero, which justifies taking the rotation of the frame as a parameter. To the memory of J. Moser, with admiration     

Self-concordant barriers for hyperbolic means

The geometric mean and the function (det(·)) ^1/m (on the m-by-m positive definite matrices) are examples of “hyperbolic means”: functions of the form p ^1/m , where p is a hyperbolic polynomial of degree m. (A homogeneous polynomial p is “hyperbolic” with respect to a vector d if the polynomial t↦p(x+td) has only real roots for every vector x.) Any hyperbolic mean is positively homogeneous and concave (on a suitable domain): we present a self-concordant barrier for its hypograph, with barrier parameter O(m ²). Our approach is direct, and shows, for example, that the function −mlog(det(·)−1) is an m ²-self-concordant barrier on a natural domain. Such barriers suggest novel interior point approaches to convex programs involving hyperbolic means. Received: December 2, 1999 / Accepted: February 2001?Published online September 3, 2001     

Norm order and geometric properties of holomorphic mappings in\mathbb{C}^n

We introduce a new notion of the order of a linear invariant family of locally biholomorphic mappings on then-ball. This order, which we call the norm order, is defined in terms of the norm rather than the trace of the “second Taylor coefficient operator” of mappings in a family. Sharp bounds on ‖Df(z)‖ and ‖f(z)‖, a general covering theorem for arbitrary LIFs and results about convexity, starlikeness, injectivity and other geometric properties of mappings given in terms of the norm order illustrate the useful nature of this notion. The norm order has a much broader range of influence on the geometric properties of mappings than does the “trace” order that the present authors and many others have used in recent years.     

Excursion decompositions for SLE and Watts' crossing formula

It is known that Schramm-Loewner Evolutions (SLEs) have a.s. frontier points if κ>4 and a.s. cutpoints if 4<κ<8. If κ>4, an appropriate version of SLE(κ) has a renewal property: it starts afresh after visiting its frontier. Thus one can give an excursion decomposition for this particular SLE(κ) “away from its frontier”. For 4<κ<8, there is a two-sided analogue of this situation: a particular version of SLE(κ) has a renewal property w.r.t its cutpoints; one studies excursion decompositions of this SLE “away from its cutpoints”. For κ=6, this overlaps Virág's results on “Brownian beads”. As a by-product of this construction, one proves Watts' formula, which describes the probability of a double crossing in a rectangle for critical plane percolation.     

Optimal buffer size for a stochastic processing network in heavy traffic

We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b ^*>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b ^*>0. A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.     

Phase Transitions in Gravitational Allocation

Given a Poisson point process of unit masses (“stars”) in dimension d ≥ 3, Newtonian gravity partitions space into domains of attraction (cells) of equal volume. In earlier work, we showed the diameters of these cells have exponential tails. Here we analyze the quantitative geometry of the cells and show that their large deviations occur at the stretched-exponential scale. More precisely, the probability that mass exp(−R ^γ ) in a cell travels distance R decays like exp(-R^f_d(g)){\left(-R^{f_d(\gamma)}\right)} where we identify the functions f _d (·) exactly. These functions are piecewise smooth and the discontinuities of f^￠_d{f^{\prime}_d} represent phase transitions. In dimension d = 3, the large deviation is due to a “distant attracting galaxy” but a phase transition occurs when f ₃(γ) = 1 (at that point, the fluctuations due to individual stars dominate). When d ≥ 5, the large deviation is due to a thin tube (a “wormhole”) along which the star density increases monotonically, until the point f _d (γ) = 1 (where again fluctuations due to individual stars dominate). In dimension 4 we find a double phase transition, where the transition between low-dimensional behavior (attracting galaxy) and highdimensional behavior (wormhole) occurs at γ = 4/3.