Guarding galleries where every point sees a large area

We prove a conjecture of Kavraki, Latombe, Motwani and Raghavan that ifX is a compact simply connected set in the plane of Lebesgue measure 1, such that any pointx∈X sees a part ofX of measure at least ɛ, then one can choose a setG of at mostconst1/ɛ log 1/ɛ points inX such that any point ofX is seen by some point ofG. More generally, if for anyk points inX there is a point seeing at least 3 of them, then all points ofX can be seen from at mostO(k ³ logk) points. Research supported by grants from the Sloan Foundation, the Israeli Academy of Sciences and Humanities, and by G.I.F. Research supported by Czech Republic Grant GAČR 201/94/2167 and Charles University grants No. 351 and 361. Part of the work was done while the author was visiting The Hebrew University of Jerusalem.     

Subgraphs of a hypercube containing no small even cycles

We investigate several Ramsey-Turán type problems for subgraphs of a hypercube. We obtain upper and lower bounds for the maximum number of edges in a subgraph of a hypercube containing no four-cycles or more generally, no 2k-cycles C_2k. These extermal results imply, for example, the following Ramsey theorems for hypercubes: A hypercube can always be edge-partitioned into four subgraphs, each of which contains no six-cycle. However, for any integer t, if the n-cube is edge-partitioned into t sub-graphs, then one of the subgraphs must contain an edight-cycle, provided only than n is sufficiently large (depending only on t).     

Halvings on small point sets

A halving is a t-design which has the same parameters as its complementary design. Together these two designs form a large set LS[2](t, k, v). There are several recursion theorems for large sets, such that a single new halving results in several new infinite families of halvings. We present new halvings with the parameters 7-(24, 10, 340), 6-(22, 9, 280), 5-(21, 10, 2184), and 5-(21, 9, 910). Recursive constructions by S. Ajoodani-Namini and G. B. Khosrovshahi [Discrete Math 135 (1994), 29–37; J. Combin. Theory A 76 (1996), 139–144] then yield that an LS[2](t, k, v) exists if and only if the parameter set is admissible for t = 6, k = 7, 8, 9, and for t ≤ 5, k ≤ 15. Thus, Hartman's conjecture is true in these cases. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 233–241, 1999     

There are no small odd perfect numbers

We prove that every odd perfect number N has at least 420 distinct prime divisors, and that N is greater than 1,9 × 10²⁵⁵⁰.     

Counting numerical sets with no small atoms

A numerical set S with Frobenius number g is a set of integers with min(S)=0 and max(Z−S)=g, and its atom monoid is . Let γg be the ratio of the number of numerical sets S having A(S)={0}∪(g,∞) divided by the total number of numerical sets with Frobenius number g. We show that the sequence {γg} is decreasing and converges to a number γ_∞≈.4844 (with accuracy to within .0050). We also examine the singularities of the generating function for {γg}. Parallel results are obtained for the ratio of the number of symmetric numerical sets S with A(S)={0}∪(g,∞) by the number of symmetric numerical sets with Frobenius number g. These results yield information regarding the asymptotic behavior of the number of finite additive 2-bases.     

Branch point area methods in conformal mapping

The classical estimate of Bieberbach that ?a ₂?≤2 for a given univalent function ?(z)=z+a ₂ z ²+… in the classS leads to the best possible pointwise estimates of the ratio ?"(z)/?'(z) for ?∈S, first obtained by K?be and Bieberbach. For the corresponding class Σ of univalent functions in the exterior disk, Goluzin found in 1943 by variational methods the corresponding best possible pointwise estimates of ?"(z)/?'(z) for ψ∈Σ. It was perhaps surprising that this time, the expressions involve elliptic integrals. Here, we obtain an area-type theorem which has Goluzin's pointwise estimate as a corollary. This shows that Goluzin's estimate, like the K?be-Bieberbach estimate, is firmly rooted in areabased methods. The appearance of elliptic integrals finds a natural explanation: they arise because a certain associated covering surface of the Riemann sphere is a torus.     

The fixed point property for small sets

There exist exactly eleven (up to isomorphism and duality) ordered sets of size 10 with the fixed point property and containing no irreducible elements.The great part of the work presented here has been done when the author was visiting Ivan Rival at the University of Ottawa, Department of Computer Science.     

The matching problem has no small symmetric SDP

Yannakakis (Proceedings of the STOC, pp 223–228, 1988; J Comput Syst Sci 43(3):441–466, 1991. doi: 10.1016/0022-0000(91)90024-Y) showed that the matching problem does not have a small symmetric linear program. Rothvoß (Proceedings of the STOC, pp 263–272, 2014) recently proved that any, not necessarily symmetric, linear program also has exponential size. In light of this, it is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the asymmetric metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size \(n^{k}\). The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.     

Minimizers of the Willmore functional with a small area constraint

We show the existence of a smooth spherical surface minimizing the Willmore functional subject to an area constraint in a compact Riemannian three-manifold, provided the area is small enough. Moreover, we partially classify complete surfaces of Willmore type with positive mean curvature in Riemannian three-manifolds.