A colorful theorem on transversal lines to plane convex sets

We prove a colorful version of Hadwiger’s transversal line theorem: if a family of colored and numbered convex sets in the plane has the property that any three differently colored members have a transversal line that meet the sets consistently with the numbering, then there exists a color such that all the convex sets of that color have a transversal line. All authors are partially supported by CONACYT research grant 5040017.     

On embeddability and stresses of graphs

Gluck has proven that triangulated 2-spheres are generically 3-rigid. Equivalently, planar graphs are generically 3-stress free. We show that already the K ₅-minor freeness guarantees the stress freeness. More generally, we prove that every K _r+2-minor free graph is generically r-stress free for 1≤r≤4. (This assertion is false for r≥6.) Some further extensions are discussed. Supported by an I.S.F. grant.     

Proof of the bandwidth conjecture of Bollobás and Komlós

In this paper we prove the following conjecture by Bollobás and Komlós: For every γ > 0 and integers r ≥ 1 and Δ, there exists β > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r ? 1)/r + γ)n and H is an r-chromatic graph with n vertices, bandwidth at most β n and maximum degree at most Δ, then G contains a copy of H.     

Note making a <Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free graph bipartite

We show that every K ₄-free graph G with n vertices can be made bipartite by deleting at most n ²/9 edges. Moreover, the only extremal graph which requires deletion of that many edges is a complete 3-partite graph with parts of size n/3. This proves an old conjecture of P. Erdős. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

On the Yao-Yao partition theorem

The Yao-Yao partition theorem states that for any probability measure μ on having a density which is continuous and bounded away from 0, it is possible to partition into 2ⁿ regions of equal measure for μ in such a way that every affine hyperplane of avoids at least one of the regions. We give a constructive proof of this result and extend it to slightly more general measures. Received: 21 August 2008     

Highly oscillatory behavior of the activator in the Gierer and Meinhardt system

In this article we construct a new type of solutions for the Gierer and Meinhardt system

Some new monotonicity formulas and the singular set in the lower dimensional obstacle problem

We construct two new one-parameter families of monotonicity formulas to study the free boundary points in the lower dimensional obstacle problem. The first one is a family of Weiss type formulas geared for points of any given homogeneity and the second one is a family of Monneau type formulas suited for the study of singular points. We show the uniqueness and continuous dependence of the blowups at singular points of given homogeneity. This allows to prove a structural theorem for the singular set. Our approach works both for zero and smooth non-zero lower dimensional obstacles. The study in the latter case is based on a generalization of Almgren’s frequency formula, first established by Caffarelli, Salsa, and Silvestre. N. Garofalo is supported in part by NSF grant DMS-0701001. A. Petrosyan is supported in part by NSF grant DMS-0701015.     

On the rigidity of molecular graphs

The rigidity of squares of graphs in three-space has important applications to the study of flexibility in molecules. The Molecular Conjecture, posed in 1984 by T.-S. Tay and W. Whiteley, states that the square G ² of a graph G of minimum degree at least two is rigid if and only if G has six spanning trees which cover each edge of G at most five times. We give a lower bound on the degrees of freedom of G ² in terms of forest covers of G. This provides a self-contained proof that the existence of the above six spanning trees is a necessary condition for the rigidity of G ². In addition, we prove that the truth of the Molecular Conjecture would imply that our lower bound is tight, and would also imply that a conjecture of Jacobs on ‘independent’ squares is valid. This work was supported by an International Joint Project grant from the Royal Society. Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization and the Hungarian Scientific Research Fund grant no. T049671, T60802.     

The Leray separating operator in the theory of the Cauchy problem

The paper is devoted to the presentation of Leray’s approach to the Cauchy problem for strictly hyperbolic operators. In the first section we give the main definitions of strictly hyperbolic operators and separating operators corresponding to them. We present the plan of derivation of the a priori estimates necessary for the proof of solvability of the Cauchy problem. In the second section we generalize the Leray approach to some classes of PDO which are not hyperbolic.     

A Krasnosel’skii-type theorem for paths of bounded length

Let S be a nonempty closed, simply connected set in the plane, and let α τ; 0. If every three points of 5 see a common point of S via paths of length at most α, then for some point s0 of S, s0 sees each point of S via such a path. That is, S is starshaped via paths of length at most α. Supported in part by NSF grant DMS-9207019     

A global solution curve for a class of periodic problems, including the pendulum equation

Using continuation methods and bifurcation theory, we study the exact multiplicity of periodic solutions, and the global solution structure, for a class of periodically forced pendulum-like equations. Our results apply also to the first order equations. We also show that by choosing a forcing term, one can produce periodic solutions with any number of Fourier coefficients arbitrarily prescribed.     

On the \varpi_n-related elements in the stable homotopy groups of spheres

Let X = {x ₁, …, x _n } be a set of n points in the d-dimensional Euclidean space , with unit diameter. In this work we give the complete proof of a conjecture by Witsenhausen, stating that the maximum M(d, n) of in dimension d is attained if and only if the points are distributed as evenly as possible among the vertices of a regular d-dimensional simplex of edge-length 1. Received: 5 July 2007, Revised: 22 October 2007     

The complex Busemann-Petty problem for arbitrary measures

The complex Busemann-Petty problem asks whether origin symmetric convex bodies in with smaller central hyperplane sections necessarily have smaller volume. The answer is affirmative if and negative if . In this article we show that the answer remains the same if the volume is replaced by an “almost” arbitrary measure. This result is the complex analogue of Zvavitch’s generalization to arbitrary measures of the original real Busemann-Petty problem. Received: 6 May 2008     

Density of Lipschitz mappings in the class of Sobolev mappings between metric spaces

We prove that Lipschitz mappings are dense in the Newtonian–Sobolev classes N ^1,p (X, Y) of mappings from spaces X supporting p-Poincaré inequalities into a finite Lipschitz polyhedron Y if and only if Y is [p]-connected, π ₁(Y) = π ₂(Y) = · · · = π _[p](Y) = 0, where [p] is the largest integer less than or equal to p. This work was supported by the NSF grant DMS-0500966.     

A geometric analysis of Renegar’s condition number,and its interplay with conic curvature

For a conic linear system of the form Ax ∈K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Among these, Renegar’s condition number is arguably the most prominent for its relation to data perturbation, error bounds, problem geometry, and computational complexity of algorithms. Nonetheless, is a representation-dependent measure which is usually difficult to interpret and may lead to overly conservative bounds of computational complexity and/or geometric quantities associated with the set of feasible solutions. Herein we show that Renegar’s condition number is bounded from above and below by certain purely geometric quantities associated with A and K; furthermore our bounds highlight the role of the singular values of A and their relationship with the condition number. Moreover, by using the notion of conic curvature, we show how Renegar’s condition number can be used to provide both lower and upper bounds on the width of the set of feasible solutions. This complements the literature where only lower bounds have heretofore been developed.     

Searching for critical angles in a convex cone

The concept of antipodality relative to a closed convex cone has been explored in detail in a recent work of ours. The antipodality problem consists of finding a pair of unit vectors in K achieving the maximal angle of the cone. Our attention now is focused not just in the maximal angle, but in the angular spectrum of the cone. By definition, the angular spectrum of a cone is the set of angles satisfying the stationarity (or criticality) condition associated to the maximization problem involved in the determination of the maximal angle. In the case of a polyhedral cone, the angular spectrum turns out to be a finite set. Among other results, we obtain an upper bound for the cardinality of this set. We also discuss the link between the critical angles of a cone K and the critical angles of its dual cone. Dedicated to Boris Polyak on his 70th Birthday.     

Blow up of balls and coverings in metric spaces

We obtain some refinements and extensions of the Basic Covering Theorem in a metric space (X, ρ). The properties of the metric ρ are used to define an inclusion coefficient k in this theorem, and this is related to the supremum of numbers t such that ρ ^t is a metric in X. The inclusion coefficient k characterizes ultrametric spaces.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

Lower bound on the profile of degree pairs in cross-intersecting set systems

We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal pairs of (d′, d″) lie on or above the line (n − 1) x + (m − 1) y = 1. Constructions show that the pair (1 + ɛ / 2n − 2, 1 + ɛ / 2m − 2) is infeasible in general, for all m, n ≥ 2 and all ɛ > 0. Moreover, for m = 2, the pair (d′, d″) = (1 / n, 1 / 2) is feasible if and only if 2 ≤ n ≤ 4. The problem originates from Razborov and Vereshchagin’s work on decision tree complexity. Research supported in part by the Hungarian Research Fund under grant OTKA T-032969.     

The Singularities of the Distance Function Near Convex Boundary Points

In an open bounded set Ω, we consider the distance function from ∂Ω associated to a Riemannian metric with C ^1,1 coefficients. Assuming that Ω is convex near a boundary point x ₀, we show that the distance function is differentiable at x ₀ if and only if there exists the tangent space to ∂Ω at x ₀. Furthermore, if the distance function is not differentiable at x ₀ then there exists a Lipschitz continuous curve, with initial point at x ₀, such that the distance function is not differentiable along such a curve.