Convex Sets in the Plane with Three of Every Four Meeting

Dedicated to the memory of Paul Erdős Suppose we have a finite collection of closed convex sets in the plane, (which without loss of generality we can take to be polygons). Suppose further that among any four of them, some three have non-empty intersection. We show that 13 points are sufficient to meet every one of the convex sets. Received October 27, 1999/Revised April 11, 2000 RID="*" ID="*" Supported by grant OTKA-T-029074. RID="†" ID="†" Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F-22234.     

Ramsey-type Theorems with Forbidden Subgraphs

Dedicated to the memory of Paul Erdős   A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments. In order to prove the equivalence, we establish several Ramsey type results for tournaments. Received August 22, 1999 RID="*" ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. RID="†" ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914. RID="‡" ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203.     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.     

Separating Cycles in Doubly Toroidal Embeddings

 We show that every 4-representative graph embedding in the double torus contains a noncontractible cycle that separates the surface into two pieces. As a special case, every triangulation of the double torus in which every noncontractible cycle has length at least 4 has a noncontractible cycle that separates the surface into two pieces. Received: May 22, 2001 Final version received: August 22, 2002 RID="*" ID="*" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070613 RID="†" ID="†" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070430     

Vertex Covers by Edge Disjoint Cliques

Dedicated to the memory of Paul Erdős Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying 1.  , for all i = 1, ..., r, 2.  , 3.  , for all , and 4.  each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs. Received October 31, 1999 RID="*" ID="*" Supported in part by NSF grant DMS-9627408. RID="†" ID="†" Supported in part by NSF grant CCR-9530974. RID="‡" ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation. RID="§" ID="§" Supported in part by NSF grant DMS-9970622.     

The Circular Flow Number of a 6-Edge Connected Graph is Less Than Four

We show that every 6-edge connected graph admits a circulation whose range lies in the interval [1,3). Received March 29, 2000 RID="*" ID="*" Supported by NATO-CNR Fellowship; this work was done while the author was visiting the Dept. of Mathematics and Statistics at Simon Fraser University, Canada. RID="†" ID="†" Supported by a National Sciences and Engineering Research Council Research Grant     

Evasion and prediction

 Say that a function π:n ^<ω →n (henceforth called a predictor) k-constantly predicts a real xn ^ω if for almost all intervals I of length k, there is iI such that x(i)=π(x↾i). We study the k-constant prediction number v _n ^const (k), that is, the size of the least family of predictors needed to k-constantly predict all reals, for different values of n and k, and investigate their relationship. Received: 27 June 2001 / Revised version: 10 September 2001 / Published online: 10 October 2002 RID="*" ID="*" Supported by Grant–in–Aid for Scientific Research (C)(2)12640124, Japan Society for the Promotion of Science RID="†" ID="†" Supported by The Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. Publication 762     

How Many Ways Can One Draw A Graph?

Using results from extremal graph theory, we determine the asymptotic number of string graphs with n vertices, i.e., graphs that can be obtained as the intersection graph of a system of continuous arcs in the plane. The number becomes much smaller, for any fixed d, if we restrict our attention to systems of arcs, any two of which cross at most d times. As an application, we estimate the number of different drawings of the complete graph K_n with n vertices under various side conditions. Dedicated to Miklós Simonovits on his sixtieth birthday * Supported by NSF grant CR-00-98246, PSC-CUNY Research Award 62450-0031 and OTKA-T-032452. † Supported by OTKA-T-032452 and OTKA-T-038397.     

A primal all-integer algorithm based on irreducible solutions

 This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method. Received: April 23, 2001 / Accepted: May 2002 Published online: March 21, 2003 RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="#" ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202. Mathematics Subject Classification (1991): 90C10     

Diophantine Approximations and Integer Points of Cones

The purpose of this note is to present a relation between directed best approximations of a rational vector and the elements of the minimal Hilbert basis of certain rational pointed cones. Furthermore, we show that for a special class of these cones the integer Carathéodory property holds true. Received May 6, 1998 RID="*" ID="*" Supported by a "Leibniz Preis" of the German Science Foundation (DFG) awarded to M. Gr?tschel. RID="†" ID="†" Supported by a "Gerhard-Hess-Forschungsf?rderpreis" of the German Science Foundation (DFG).     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.     

The Cost of the Missing Bit: Communication Complexity with Help

Dedicated to the Memory of Paul Erdős We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b - 1 bits of information from an all-powerful benevolent Helper who can see all the input. Extending results of Babai, Nisan, and Szegedy (1992) to this model, we construct families of explicit functions for which bits of communication are required to find the "missing bit", where n is the length of each player's input and k is the number of players. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities (in the CFL sense) for players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable from BNS). The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer jumping function. Received November 12, 1998 RID="*" ID="*" Supported in part by NSA grant MSPR-96G-184. RID="†" ID="†" Supported in part by an NSF Graduate Fellowship.     

Degree complexity for a modified pigeonhole principle

 We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in [7]. M P H P is defined over n pigeons and log n holes, and more than one pigeon can go into a hole (according to some rules). Using a technique of Razborov [9] and simplified by Impagliazzo, Pudlák and Sgall [8], we prove that any Polynomial Calculus refutation of a set of polynomials encoding the M P H P, requires degree Ω(log n). We also prove a simple Lemma giving a simulation of Resolution by Polynomial Calculus. Using this lemma, and a Resolution upper bound by Goerdt [7], we obtain that the degree lower bound is tight. Our lower bound establishes the optimality of the tree-like Resolution simulation by the Polynomial Calculus given in [6]. Received: 29 March 2001 / Published online: 2 September 2002 RID="⋆" ID="⋆" A prelimianry version appeared as part of the paper A Study of Proof Search Algorithms for Resolution and Polynomial Calculus published in the Proceedings of the 40-th IEEE Conference on Foundations of Computer Science, 1999 RID="†" ID="†" Partly supported by Project CICYT, TIC 98-0410-C02-01 and Promoción General del Conocimiento PB98-0937-C04-03. RID="††" ID="††" Part of this work was done while the author was a member of the School of Mathematics at Institute for Advanced Study supported by a NSF grant n. 9987845     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

A non-well-founded primitive recursive tree provably well-founded for co-r.e. sets

 We construct by diagonalization a non-well-founded primitive recursive tree, which is well-founded for co-r.e. sets, provable in Σ₁ ⁰. It follows that the supremum of order-types of primitive recursive well-orderings, whose well-foundedness on co-r.e. sets is provable in Σ₁ ⁰, equals the limit of all recursive ordinals ω₁ ^ck . RID="ID=" <E5>Mathematics Subject Classification (2000):&ensp;03B30</E5>, 03F15 RID="ID=" Supported by the Deutschen Akademie der Naturforscher Leopoldina grant #BMBF-LPD 9801-7 with funds from the Bundesministerium f&uuml;r Bildung, Wissenschaft, Forschung und Technologie. RID="ID=" I would like to thank A. SETZER for his hospitality during my stay in Uppsala in December 1998 &ndash; these investigations are inspired by a discussion with him; S. BUSS for his hospitality during my stay at UCSD and for valuable remarks on a previous version of this paper; and M. M&Ouml;LLERFELD for remarks on a previous title. Received: 27 July 2000 / Published online: 25 February 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):&ensp;03B30</E5>, 03F15 RID=" ID=" Supported by the Deutschen Akademie der Naturforscher Leopoldina grant #BMBF-LPD 9801-7 with funds from the Bundesministerium f&uuml;r Bildung, Wissenschaft, Forschung und Technologie. RID=" ID=" I would like to thank A. SETZER for his hospitality during my stay in Uppsala in December 1998 &ndash; these investigations are inspired by a discussion with him; S. BUSS for his hospitality during my stay at UCSD and for valuable remarks on a previous version of this paper; and M. M&Ouml;LLERFELD for remarks on a previous title.     

Combinatorial and Arithmetical Properties of Linear Numeration Systems

Dedicated to the memory of Paul Erdős We extend a result of J. Alexander and D. Zagier on the Garsia entropy of the Erdős measure. Our investigation heavily relies on methods from combinatorics on words. Furthermore, we introduce a new singular measure related to the Farey tree. Received October 7, 1999 RID="†" ID="†" This author is supported by the START-project Y96-MAT of the Austrian Science Fund RID="‡" ID="‡" This author is supported by the Austrian Science Fund (FWF) grant P14200-MAT RID="*" ID="*" This author is supported by the Austrian Science Fund (FWF) grant S8307-MAT     

Asymptotic separation for independent trajectories of Markov processes

We say that n independent trajectories ξ₁(t),…,ξ _n (t) of a stochastic process ξ(t)on a metric space are asymptotically separated if, for some ɛ > 0, the distance between ξ _i (t _i ) and ξ _j (t _j ) is at least ɛ, for some indices i, j and for all large enough t ₁,…,t _n , with probability 1. We prove sufficient conitions for asymptotic separationin terms of the Green function and the transition function, for a wide class of Markov processes. In particular,if ξ is the diffusion on a Riemannian manifold generated by the Laplace operator Δ, and the heat kernel p(t, x, y) satisfies the inequality p(t, x, x) ≤ Ct ^−ν/2 then n trajectories of ξ are asymptotically separated provided . Moreover, if for some α∈(0, 2)then n trajectories of ξ^(α) are asymptotically separated, where ξ^(α) is the α-process generated by −(−Δ)^α/2. Received: 10 June 1999 / Revised version: 20 April 2000 / Published online: 14 December 2000 RID="*" ID="*" Supported by the EPSRC Research Fellowship B/94/AF/1782 RID="**" ID="**" Partially supported by the EPSRC Visiting Fellowship GR/M61573     

Submanifolds with constant Möbius scalar curvature in <Emphasis Type="Italic">S</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

 Let M ^m be a m-dimensional submanifold in the n-dimensional unit sphere S ⁿ without umbilic point. Two basic invariants of M ^m under the M?bius transformation group of S ⁿ are a 1-form Φ called M?bius form and a symmetric (0,2) tensor A called Blaschke tensor. In this paper, we prove the following rigidity theorem: Let M ^m be a m-dimensional (m≥3) submanifold with vanishing M?bius form and with constant M?bius scalar curvature R in S ⁿ , denote the trace-free Blaschke tensor by . If , then either ||?||≡0 and M ^m is M?bius equivalent to a minimal submanifold with constant scalar curvature in S ⁿ ; or and M ^m is M?bius equivalent to in for some c≥0 and . Received: 15 May 2002 / Revised version: 3 February 2003 Published online: 19 May 2003 RID="*" ID="*" Partially supported by grants of CSC, NSFC and Outstanding Youth Foundation of Henan, China. RID="†" ID="†" Partially supported by the Alexander Humboldt von Stiftung and Zhongdian grant of NSFC. Mathematics Subject Classification (2000): Primary 53A30; Secondary 53B25