Constructive lower bounds for off-diagonal Ramsey numbers

We describe an explicit construction whicy, for some fixed absolute positive constant ε, produces, for every integers>1 and all sufficiently largem, a graph on at least vertices containing neither a clique of sizes nor an independent set of sizem. Part of this work was done at the Institute for Advanced Study, Princeton, NJ 08540, USA. Research supported in part 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. Research supported in part by a grant A1019901 of the Academy of Sciences of the Czech Republic and by a cooperative research grant INT-9600919/ME-103 from the NSF (USA) and the MŠMT (Czech Republic).     

On two Hamilton cycle problems in random graphs

We study two problems related to the existence of Hamilton cycles in random graphs. The first question relates to the number of edge disjoint Hamilton cycles that the random graph G _n,p contains. δ(G)/2 is an upper bound and we show that if p ≤ (1 + o(1)) ln n/n then this upper bound is tight whp. The second question relates to how many edges can be adversarially removed from G _n,p without destroying Hamiltonicity. We show that if p ≥ K ln n/n then there exists a constant α > 0 such that whp G − H is Hamiltonian for all choices of H as an n-vertex graph with maximum degree Δ(H) ≤ αK ln n. Research supported in part by NSF grant CCR-0200945. Research supported in part by USA-Israel BSF Grant 2002-133 and by grant 526/05 from the Israel Science Foundation.     

Embedding nearly-spanning bounded degree trees

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1 − ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 − ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above. Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. 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.     

Polynomial bounds for Large Bernoulli sections of ℓ 1 N

We present a quantitative form of the result of Bai and Yin from [2], and use to show that the section of ℓ ₁ ^(1+δ)n spanned byn random independent sign vectors is with high probability isomorphic to euclidean with isomorphism constant polynomial in δ⁻¹. Partially supported by BSF grant 2002-006. Supported by the National Science Foundation under agreement No. DMS-0111298. Supported in part by the Israel Science Academy.     

The concentration of the chromatic number of random graphs

We prove that for every constant >0 the chromatic number of the random graphG(n, p) withp=n ^–1/2– is asymptotically almost surely concentrated in two consecutive values. This implies that for any <1/2 and any integer valued functionr(n)O(n ) there exists a functionp(n) such that the chromatic number ofG(n,p(n)) is preciselyr(n) asymptotically almost surely.Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.Research supported in part by a Charles Clore Fellowship.     

A global volume lemma and applications

Letf ^t be aC ² Axiom A dynamical system on a compact manifold satisfying the transversality condition. We prove that ifB _x (ε,t)=[y: dist (f ^s x,f ^s y)≤ε for all 0≤s≤t], then volB _x (ε,t) has the order exp(∫ ₀ ^t φ (f ^s x)ds) in the continuous time case and exp (Σ _s ^t−1 φ (f ^s x)) in the discrete time case, whereφ is a Holder continuous extension from basic hyperbolic sets of the negative of the differential expansion coefficient in the unstable direction. An application to the theory of large deviations is given. Partially supported by US-Israel BSF. Partially supported by a Darpa grant.     

Prime top extensions of division algebra

Every division algebra of degreep ^t has a prime-to-p extension which is a crossed product, ifft ≤ 2. Research of the first author supported in part by the NSA/MSP Grant MDA90-H4001 while the author was on Sabbatical at Yale University Second author is grateful for support order NSF grant DMS-8901778     

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.     

Measure-valued Markov branching processes conditioned on non-extinction

We consider a particular class of measure-valued Markov branching processes that are constructed as “superprocesses” over some underlying Markov process. Such a processX dies out almost surely, so we introduce various conditioning schemes which keepX alive at large times. Under suitable hypotheses, which include the convergence of the semigroup for the underlying process to some limiting probability measureν, we show that the conditional distribution oft ⁻¹ X _t converges to that ofZν ast → ∞, whereZ is some strictly positive, real random variable. Research supported in part by NSF grant DMS 8701212. Research supported in part by an NSERC operating grant.     

Modified Busemann-Petty problem on sections of convex bodies

The Busemann-Petty problem asks whether convex origin-symmetric bodies in ℝ ⁿ with smaller central hyperplane sections necessarily have smallern-dimensional volume. It is known that the answer is affirmative ifn≤4 and negative ifn≥5. In this article we replace the assumptions of the original Busemann-Petty problem by certain conditions on the volumes of central hyperplane sections so that the answer becomes affirmative in all dimensions. The first-named author was supported in part by the NSF grant DMS-0136022 and by a grant from the University of Missouri Research Board.     

The maximum number of Hamiltonian paths in tournaments

Solving an old conjecture of Szele we show that the maximum number of directed Hamiltonian paths in a tournament onn vertices is at mostc · n ^3/2 · n!/2 ^n–1, wherec is a positive constant independent ofn.Research supported in part by a U.S.A.-Israel BSF grant and by a Bergmann Memorial Grant.     

Codes And Xor Graph Products

What is the maximum possible number, f₃(n), of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g³(n), of vectors in {0,1,2}ⁿ such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a graph G. Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of G (normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity, while the other grows linearly. As a special case, it follows that f₃(n) = Θ(2ⁿ) whereas g₃(n)=Θ(n). * Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. † Research partially supported by a Charles Clore Foundation Fellowship.     

Almost linear upper bounds on the length of general davenport—schinzel sequences

Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We obtain almost linear upper bounds on the length λ_s(n) of Davenport—Schinzel sequences composed ofn symbols in which no alternating subsequence is of length greater thans+1. These bounds are of the formO(nα(n)^O(α(n)5-3)), and they generalize and extend the tight bound Θ(nα(n)) obtained by Hart and Sharir for the special cases=3 (α(n) is the functional inverse of Ackermann’s function), and also improve the upper boundO(n log*n) due to Szemerédi. Work on this paper has been supported in part by a grant from the U.S. — Israeli Binational Science Foundation.     

Upper bounds for the diameter and height of graphs of convex polyhedra

Let Δ(d, n) be the maximum diameter of the graph of ad-dimensional polyhedronP withn-facets. It was conjectured by Hirsch in 1957 that Δ(d, n) depends linearly onn andd. However, all known upper bounds for Δ(d, n) were exponential ind. We prove a quasi-polynomial bound Δ(d, n)≤n ^{2 logd+3}. LetP be ad-dimensional polyhedron withn facets, let ϕ be a linear objective function which is bounded onP and letv be a vertex ofP. We prove that in the graph ofP there exists a monotone path leading fromv to a vertex with maximal ϕ-value whose length is at most . This research was supported in part by a BSF grant, by a GIF grant, and by ONR-N00014-91-C0026.     

On acyclic colorings of graphs on surfaces

A properk-coloring of a graph is acyclic if every 2-chromatic subgraph is acyclic. Borodin showed that every planar graph has an acyclic 5-coloring. This paper shows that the acyclic chromatic number of the projective plane is at most 7. The acyclic chromatic number of an arbitrary surface with Euler characteristic η=−γ is at mostO(γ^4/7). This is nearly tight; for every γ>0 there are graphs embeddable on surfaces of Euler characteristic −γ whose acyclic chromatic number is at least Ω(γ^4/7/(logγ)^1/7). Therefore, the conjecture of Borodin that the acyclic chromatic number of any surface but the plane is the same as its chromatic number is false for all surfaces with large γ (and may very well be false for all surfaces). This author's research was supported in part by a United States Israeli BSF grant. This author's research was supported by the Ministry of Research and Technology of Slovenia, Research Project P1-0210-101-92. This author's research was supported by the Office of Naval Research, grant number N00014-92-J-1965.     

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.     

Branched two-sheeted covers

In this paper we explore the connection between Weierstrass points of subspaces of the holomorphic differentials and the geometry of the canonical curve inPC ^g−1. In particular, we consider non-hyperelliptic Riemann surfaces with involution and the Weierstrass points of the −1 eigenspace of the holomorphic differentials. The case of coverings of a torus is considered in detail. Research of the first author supported in part by the Paul and Gabriella Rosenbaum Foundation, the Landau Center for Research in Mathematical Analysis (supported by Minerva Foundation-Germany) and a US-Israel BSF grant. Research by the second author supported in part by NSF Grant DMS 9003361 and a Lady Davis Visiting Professorship at the Hebrew University.     

Onk-sets in arrangements of curves and surfaces

We extend the notion ofk-sets and (≤k)-sets (see [3], [12], and [19]) to arrangements of curves and surfaces. In the case of curves in the plane, we assume that each curve is simple and separates the plane. Ak-point is an intersection point of a pair of the curves which is covered by exactlyk interiors of (or half-planes bounded by) other curves; thek-set is the set of allk-points in such an arrangement, and the (≤k)-set is the union of allj-sets, forj≤k. Adapting the probabilistic analysis technique of Clarkson and Shor [13], we obtain bounds that relate the maximum size of the (≤k)-set to the maximum size of a 0-set of a sample of the curves. Using known bounds on the size of such 0-sets we obtain asympotically tight bounds for the maximum size of the (≤k)-set in the following special cases: (i) If each pair of curves intersect at most twice, the maximum size is Θ(nkα(nk)). (ii) If the curves are unbounded arcs and each pair of them intersect at most three times, then the maximum size is Θ(nkα(n/k)). (iii) If the curves arex-monotone arcs and each pair of them intersect in at most some fixed numbers of points, then the maximum size of the (≤k)-set is Θ(k ²λ _s (nk)), where λ _s (m) is the maximum length of (m,s)-Davenport-Schinzel sequences. We also obtain generalizations of these results to certain classes of surfaces in three and higher dimensions. Finally, we present various applications of these results to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more. An interesting application yields andO(n logn) bound on the expected number of vertically visible features in an arrangement ofn horizontal discs when they are stacked on top of each other in random order. This in turn leads to an efficient randomized preprocessing ofn discs in the plane so as to allow fast stabbing queries, in which we want to report all discs containing a query point. Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development-and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Analysis of some new partition statistics

We study several statistics for integer partitions: for a random partition of an integer n we consider the average size of the smallest gap (missing part size), the multiplicity of the largest part, and the largest repeated part size. Furthermore, we estimate the number of gap-free partitions of n. 2000 Mathematics Subject Classification Primary—05A17; Secondary—11P82 Dedicated to Helmut Prodinger on the occasion of his 50th birthday P.J. Grabner is supported by the START-project Y96-MAT of the Austrian Science Fund. This material is based upon work supported by the National Research Foundation under grant number 2053740.     

The distribution of the root degree of a random permutation

Given a permutation ω of {1, …, n}, let R(ω) be the root degree of ω, i.e. the smallest (prime) integer r such that there is a permutation σ with ω = σ ^r . We show that, for ω chosen uniformly at random, R(ω) = (lnlnn − 3lnlnln n + O ^p (1))⁻¹ lnn, and find the limiting distribution of the remainder term. Research supported in part by NSF grants CCR-0225610, DMS-0505550 and ARO grant W911NF-06-1-0076. Research supported by NSF grant DMS-0406024.