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.     

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.     

Packing directed circuits

We prove a conjecture of Younger, that for every integern0 there exists an integert0 such that for every digraphG, eitherG hasn vertex-disjoint directed circuits, orG can be made acyclic by deleting at mostt vertices.Research partially supported by DONET ECHM contract CHRXCT930090.Research partially supported by DIMACS, by NSF grant DMS-9401981 and by ONR grant N00014-92-J-1965, and partially performed under a consulting agreement with Bellcore.Research partially supported by DIMACS, by Université de Paris VI, by NSF grant DMS-9303761 and by ONR grant N00014-93-1-0325, and partially performed under a consulting agreement with Bellcore.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

An optimal lower bound on the number of variables for graph identification

In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308.     

On The Structure Of Triangle-Free Graphs Of Large Minimum Degree

It is shown that for every ε>0 there exists a constant L such that every triangle-free graph on n vertices with minimum degree at least (1/3+ε)n is homomorphic to a triangle-free graph on at most L vertices. * Research partially supported by KBN grant 2 P03A 016 23.     

A New Lower Bound For A Ramsey-Type Problem

Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph on s vertices. The main aim of this paper is to provide a new lower bound on the size of the maximum subset of G without a copy of complete graph K_r. Our results substantially improve previous bounds of Krivelevich and Bollobás and Hind. * Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting Microsoft Research.     

Generating Random Regular Graphs

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d = O(n^1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd²). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author. The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs. * Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.     

Quasi-planar graphs have a linear number of edges

A graph is calledquasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph withn vertices isO(n).Work on this paper by Pankaj K. Agarwal, Boris Aronov and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work on this paper by Pankaj K. Agarwal has also been supported by NSF Grant CCR-93-01259, by an Army Research Office MURI grant DAAH04-96-1-0013, by an NYI award, and by matching funds from Xerox Corporation. Work on this paper by Boris Aronov has also been supported by NSF Grant CCR-92-11541 and by a Sloan Research Fellowship. Work on this paper by János Pach, Richard Pollack, and Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-94-24398. Work by János Pach was also supported by Grant OTKA-4269 and by a CUNY Research Award. Work by Richard Pollack was also supported by NSF Grants CCR-94-02640 and DMS-94-00293. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Part of the work on this paper was done during the participation of the first four authors in the Special Semester on Computational and Combinatorial Geometry organized by the Mathematical Research Institute of Tel Aviv University, Spring 1995.     

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     

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.     

How to draw a planar graph on a grid

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n–4 byn–2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fáry embedding of every planar graph of sizen, has cardinality at leastn+(1–o(1))n which settles a problem of Mohar.Supported in part by P. R. C. Mathematiques et Informatique.Supported in part by HSF grant 1814.Part of the work on this paper was done while this author was on sabbatical leave at école Normal Supérieure and école des Hautes études en Sciences Sociales; supported in part by NSF grant DMS-850 1947.     

Drawing 4-Pfaffian graphs on the torus

We say that a graph G is k-Pfaffian if the generating function of its perfect matchings can be expressed as a linear combination of Pfaffians of k matrices corresponding to orientations of G. We prove that 3-Pfaffian graphs are 1-Pfaffian, 5-Pfaffian graphs are 4-Pfaffian and that a graph is 4-Pfaffian if and only if it can be drawn on the torus (possibly with crossings) so that every perfect matching intersects itself an even number of times. We state conjectures and prove partial results for k>5. The author was supported in part by NSF under Grant No. DMS-0200595 and DMS-0701033.     

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.     

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.     

The asymptotic number of acyclic digraphs. I

We obtain an asymptotic formula forA _n,q , the number of digraphs withn labeled vertices,q edges and no cycles. The derivation consists of two separate parts. In the first we analyze the generating function forA _n,q so as to obtain a central limit theorem for an associated probability distribution. In the second part we show combinatorially thatA _n,q is a smooth function ofq. By combining these results, we obtain the desired asymptotic formula. Research supported by NSF under grant MCS-8300414. Research supported by NSERC under grant A4067. Research supported by NSF under grant MCS-8302282. Research supported by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowship Scheme, while this author was at the University of Newcastle, Australia.     

The Turán Number Of The Fano Plane

  Let PG₂(2) be the Fano plane, i. e., the unique hypergraph with 7 triples on 7 vertices in which every pair of vertices is contained in a unique triple. In this paper we prove that for sufficiently large n, the maximum number of edges in a 3-uniform hypergraph on n vertices not containing a Fano plane is

Triangle Factors In Sparse Pseudo-Random Graphs

The goal of the paper is to initiate research towards a general, Blow-up Lemma type embedding statement for pseudo-random graphs with sublinear degrees. In particular, we show that if the second eigenvalue of a d-regular graph G on 3n vertices is at most cd ³/n ² log n, for some sufficiently small constant c > 0, then G contains a triangle factor. We also show that a fractional triangle factor already exists if < 0.1d ²/n. The latter result is seen to be best possible up to a constant factor, for various values of the degree d = d(n).* Supported by a USA-Israeli BSF grant, by a grant from the Israel Science Foundation and by a Bergmann Memorial Award. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich.     

On-line coloring of perfect graphs

Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog^(2k–3) n/log^(2k–4) n) colors. Vishwanathan showed that at least (log ^k–1 n/k ^k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn ^10k/loglogn colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

The Number Of Orientations Having No Fixed Tournament

Let T be a fixed tournament on k vertices. Let D(n,T ) denote the maximum number of orientations of an n-vertex graph that have no copy of T. We prove that for all sufficiently (very) large n, where t_k−1(n) is the maximum possible number of edges of a graphon n vertices with no K_k, (determined by Turán’s Theorem). The proof is based on a directed version of Szemerédi’s regularity lemma together with some additional ideas and tools from Extremal Graph Theory, and provides an example of a precise result proved by applying this lemma. For the two possible tournaments with three vertices we obtain separate proofs that avoid the use of the regularity lemma and therefore show that in these cases already holds for (relatively) small values of n. * 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.