Extended formulations in combinatorial optimization

This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski–Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes.     

Conformal geometry of foliations

In this article, we begin a systematic study of conformal properties of codimension-1 foliations. We first define and study local conformal invariants. A case of particular interest is that of harmonic foliations of the plane. Then we study existence of totally umbilical and “Dupin” foliations on compact 3-manifolds of constant curvature.      

Certain 4-manifolds with non-negative sectional curvature

In this paper, we study certain compact 4-manifolds with non-negative sectional curvature K. If s is the scalar curvature and W. is the self-dual part of Weyl tensor, then it will be shown that there is no metric g on S ^• × S ^• with both (i) K > 0 and (ii) ÷ s − W _• ⩾ 0. We also investigate other aspects of 4-manifolds with non-negative sectional curvature. One of our results implies a theorem of Hamilton: “If a simply-connected, closed 4-manifold M^• admits a metric g of non-negative curvature operator, then M^• is one of S^•, ℂP^• and S^•×S^•”. Our method is different from Hamilton’s and is much simpler. A new version of the second variational formula for minimal surfaces in 4-manifolds is proved.      

On the doubled tetrus

The “tetrus” is a member of a family of hyperbolic 3-manifolds with totally geodesic boundary, described by Paoluzzi–Zimmerman, which also contains W.P. Thurston’s “tripus.” Each member of this family has a branched cover to B ³ over a certain tangle T. This map on the tripus has degree three, and on the tetrus degree four. We describe a cover of the double of the tetrus, itself a double across a closed surface, which fibers over the circle.     

Disagreement point axioms and the egalitarian bargaining solution

We provide new characterizations of the egalitarian bargaining solution on the class of strictly comprehensive n-person bargaining problems. The main axioms used in all of our results are Nash’s IIA and disagreement point monotonicity—an axiom which requires a player’s payoff to strictly increase in his disagreement payoff. For n = 2 these axioms, together with other standard requirements, uniquely characterize the egalitarian solution. For n > 2 we provide two extensions of our 2-person result, each of which is obtained by imposing an additional axiom on the solution. Dropping the axiom of anonymity, strengthening disagreement point monotonicity by requiring player i’s payoff to be a strictly decreasing function of the disagreement payoff of every other player j ≠ i, and adding a “weak convexity” axiom regarding changes of the disagreement point, we obtain a characterization of the class of weighted egalitarian solutions. This “weak convexity” axiom requires that a movement of the disagreement point in the direction of the solution point should not change the solution point. We also discuss the so-called “transfer paradox” and relate it to this axiom.     

The Grand Riemann Hypothesis

These lectures are a continuation of Bombieri’s series “The classical Theory of Zeta and L-Functions” (in this volume). Naturally there is some overlap between his and our presentations. My aim is to formulate the Riemann Hypothesis “GRH” in its most general setting and to demonstrate its importance and power as well as to indicate some of the progress that has been made around these conjectures. A particular theme being that a number of the striking applications of the GRH have been proven unconditionally by establishing suitably strong approximations thereof.     

Classifying Descents According to Parity

In this paper we refine the well-known permutation statistic “descent” by fixing parity of (exactly) one of the descent’s numbers. We provide explicit formulas for the distribution of these (four) new statistics. We use certain differential operators to obtain the formulas. Moreover, we discuss connection of our new statistics to the Genocchi numbers. We also provide bijective proofs of some of our results. Received September 7, 2005     

Stein Neighborhood Bases of Embedded Strongly Pseudoconvex Domains and Approximation of Mappings

In this paper we construct a Stein neighborhood basis for any compact subvariety A with strongly pseudoconvex boundary bA and Stein interior A \ bA in a complex space X. This is an extension of a well known theorem of Siu. When A is a complex curve, our result coincides with the result proved by Drinovec-Drnovšek and Forstnerič. We shall adapt their proof to the higher dimensional case, using also some ideas of Demailly’s proof of Siu’s theorem. For embedded strongly pseudoconvex domain in a complex manifold we also find a basis of tubular Stein neighborhoods. These results are applied to the approximation problem for holomorphic mappings. Research supported by grants ARRS (3311-03-831049), Republic of Slovenia.     

Convolution equations and spaces of ultradifferentiable functions

We study spaces of “approximate solutions” to a given convolution equation. In particular we show how their quasianalyticity can be reduced to the study of a suitably constructed Cauchy problem for related spaces. We give a unicity theorem for this problem. This paper is dedicated to the author’s son, Alessandro. The author has been partially supported by Ministero P.I., and G.N.S.A.G.A. of Consiglio Nazionale delle Ricerche.     

A Probabilistic Approach to Carne’s Bound

Carne’s bound is a sharp inequality controlling the transition probabilities for a discrete reversible Markov chain (Section 1). Its ordinary proof uses spectral techniques which look as efficient as miraculous. Here we present a new proof, comparing a “drift” for ways “out” and “back”, to get the gaussian part of the bound (Section 2), and using a conditioning technique to get the flight factor (Section 4). Moreover we show how our proof is more “supple” than Carne’s one and may generalize (Section 3.2).      

Faraday’s Form and Maxwell’s Equations in the Heisenberg Group

In this note we present a geometric formulation of Maxwell’s equations in Carnot groups (connected simply connected nilpotent Lie groups with stratified Lie algebra) in the setting of the intrinsic complex of differential forms defined by M. Rumin. Restricting ourselves to the first Heisenberg group \mathbbH¹{\mathbb{H}^{1}}, we show that these equations are invariant under the action of suitably defined Lorentz transformations, and we prove the equivalence of these equations with differential equations “in coordinates”. Moreover, we analyze the notion of “vector potential”, and we show that it satisfies a new class of 4th order evolution differential equations.     

Almost <Emphasis Type="Italic">C</Emphasis>(λ)-manifolds

In this paper, we study almost C(λ)-manifolds. We obtain necessary and sufficient conditions for an almost contact metric manifold to be an almost C(λ)-manifold. We prove that contact analogs of A. Gray’s second and third curvature identities on almost C(λ)-manifolds hold, while a contact analog of A. Gray’s first identity holds if and only if the manifold is cosymplectic. It is proved that a conformally flat, almost C(λ)-manifold is a manifold of constant curvature λ.     

Singular Cauchy problem for the equation of flow of thin viscous films with nonlinear convection

For multidimensional equations of flow of thin capillary films with nonlinear diffusion and convection, we prove the existence of a strong nonnegative generalized solution of the Cauchy problem with initial function in the form of a nonnegative Radon measure with compact support. We determine the exact upper estimate (global in time) for the rate of propagation of the support of this solution. The cases where the degeneracy of the equation corresponds to the conditions of “strong” and “weak” slip are analyzed separately. In particular, in the case of “ weak” slip, we establish the exact estimate of decrease in the L ²-norm of the gradient of solution. It is well known that this estimate is not true for the initial functions with noncompact supports. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 2, pp. 250–271, February, 2006.     

Weakly Gibbsian representations for joint measures of quenched lattice spin models

Can the joint measures of quenched disordered lattice spin models (with finite range) on the product of spin-space and disorder-space be represented as (suitably generalized) Gibbs measures of an “annealed system”? - We prove that there is always a potential (depending on both spin and disorder variables) that converges absolutely on a set of full measure w.r.t. the joint measure (“weak Gibbsianness”). This “positive” result is surprising when contrasted with the results of a previous paper [K6], where we investigated the measure of the set of discontinuity points of the conditional expectations (investigation of “a.s. Gibbsianness”). In particular we gave natural “negative” examples where this set is even of measure one (including the random field Ising model). Further we discuss conditions giving the convergence of vacuum potentials and conditions for the decay of the joint potential in terms of the decay of the disorder average over certain quenched correlations. We apply them to various examples. From this one typically expects the existence of a potential that decays superpolynomially outside a set of measure zero. Our proof uses a martingale argument that allows to cut (an infinite-volume analogue of) the quenched free energy into local pieces, along with generalizations of Kozlov's constructions. Received: 11 November 1999 / Revised version: 18 April 2000 / Published online: 22 November 2000 RID="*" ID="*" Work supported by the DFG Schwerpunkt `Wechselwirkende stochastische Systeme hoher Komplexit?t'     

New examples of compact manifolds with holonomy Spin(7)

We find new examples of compact Spin(7)-manifolds using a construction of Joyce (J. Differ. Geom., 53:89–130, 1999; Compact manifolds with special holonomy. Oxford University Press, Oxford, 2000). The essential ingredient in Joyce’s construction is a Calabi–Yau 4-orbifold with particular singularities admitting an antiholomorphic involution, which fixes the singularities. We search the class of well-formed quasismooth hypersurfaces in weighted projective spaces for suitable Calabi–Yau 4-orbifolds.     

Two-weight estimates for singular and strongly singular integral operators

We give a Pontryagin-Thom type construction for Stein factorizations of fold maps of 3-manifolds into the plane. As an application, we compute the cobordism group of Stein factorizations of fold maps of oriented 3-manifolds into the plane and the oriented cobordism group of fold maps of 3-manifolds into the plane. It turns out that these two groups are isomorphic to Z ₂ ⊕ Z ₂. We have the analogous results about bordism groups as well.      

On the Number of Facets of Three-Dimensional Dirichlet Stereohedra III: Full Cubic Groups

We are interested in the maximum possible number of facets that Dirichlet stereohedra for three-dimensional crystallographic groups can have. In two previous papers, D. Bochiş and the second author studied the problem for noncubic groups. This paper deals with “full” cubic groups, while “quarter” cubic groups are left for a subsequent paper. Here, “full” and “quarter” refers to the recent classification of three-dimensional crystallographic groups by Conway, Delgado-Friedrichs, Huson and Thurston. This paper’s main result is that Dirichlet stereohedra for any of the 27 full groups cannot have more than 25 facets. We also find stereohedra with 17 facets for one of these groups. Research partially supported by the Spanish Ministry of Education and Science, grant number MTM2005-08618-C02-02.     

The structure of higher-dimensional Iwasawa modules under a far-fetched assumption

From the assumption that Leopoldt’s conjecture fails and some mild extra assumptions, we deduce the existence of multiple $$\mathbb {Z}_p$$-extensions whose Iwasawa modules are “large” in a precise sense. We are not aware of any constructions of such extensions that avoid our preposterously strong hypothesis.     

Local Topological Toughness and Local Factors

We localize and strengthen Katona’s idea of an edge-toughness to a local topological toughness. We disprove a conjecture of Katona concerning the conection between edge-toughness and factors. For the topological toughness we prove a theorem similar to Katona’s 2k-factor-conjecture, which turned out to be false for his edge-toughness. We prove, that besides this the topological toughness has nearly all known nice properties of Katona’s edge-toughness and therefore is worth to be considered. Research supported by the “Mathematics in Information Society” project carried out by Alfréd Rényi Institute of Mathematics - Hungarian Academy of Sciences, in the framework of the European Community’s “Confirming the International Role of Community Research” programme. Research supported by the Ministry of Education OTKA grant OTKA T 043520.     

On symplectic half-flat manifolds

We construct examples of symplectic half-flat manifolds on compact quotients of solvable Lie groups. We prove that the Calabi-Yau structures are not rigid in the class of symplectic half-flat structures. Moreover, we provide an example of a compact 6-dimensional symplectic half-flat manifold whose real part of the complex volume form is d-exact. Finally we discuss the 4-dimensional case. This work was supported by the Projects M.I.U.R. “Geometric Properties of Real and Complex Manifolds”, “Riemannian Metrics and Differentiable Manifolds” and by G.N.S.A.G.A. of I.N.d.A.M.