OnK 4-free subgraphs of random graphs

For 0<1 and graphsG andH, writeGH if any -proportion of the edges ofG spans at least one copy ofH inG. As customary, writeK ^r for the complete graph onr vertices. We show that for every fixed real >0 there exists a constantC=C() such that almost every random graphG _n,p withp=p(n)Cn ^–2/5 satisfiesG _{n,p 2/3+} K ⁴. The proof makes use of a variant of Szemerédi's regularity lemma for sparse graphs and is based on a certain superexponential estimate for the number of pseudo-random tripartite graphs whose triangles are not too well distributed. Related results and a general conjecture concerningH-free subgraphs of random graphs in the spirit of the Erds-Stone theorem are discussed.The first author was partially supported by FAPESP (Proc. 93/0603-1) and by CNPq (Proc. 300334/93-1 and ProTeM-CC-II Project ProComb). Part of this work was done while the second author was visiting the University of São Paulo, supported by FAPESP (Proc. 94/4276-8). The third author was partially supported by the NSF grant DMS-9401559.     

Maximal chains of isomorphic subgraphs of countable ultrahomogeneous graphs

For a countable ultrahomogeneous graph G=〈G,ρ〉$\mathbb{G}=〈G,\rho 〉$ let P(G)$\mathbb{P}(\mathbb{G})$ denote the collection of sets A⊂G$A\subset G$ such that 〈A,ρ∩[A]²〉≅G$〈A,\rho \cap {[A]}^2〉\cong \mathbb{G}$. The order types of maximal chains in the poset 〈P(G)∪{∅},⊂〉$〈\mathbb{P}(\mathbb{G})\cup \{\varnothing \},\subset 〉$ are characterized as:     

Unavoidable subgraphs of colored graphs

A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let S_k be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K_k/2's or simply one K_k/2. Bollobás conjectured that for all k and ε>0, there exists an n(k,ε) such that if n?n(k,ε) then every two-edge-coloring of K_n, in which the density of each color is at least ε, contains a member of this family. We solve this conjecture and present a series of results bounding n(k,ε) for different ranges of ε. In particular, if ε is sufficiently close to , the gap between our upper and lower bounds for n(k,ε) is smaller than those for the classical Ramsey number R(k,k).     

Regular subgraphs of dense graphs

Every graph onn vertices, with at leastc _k n logn edges contains ak-regular subgraph. This answers a question of Erdős and Sauer.     

On automorphisms of infinite graphs with forbidden subgraphs

LexX be anm-connected infinite graph without subgraphs homeomorphic toKm, n, for somen, and let α be an automorphism ofX with at least one cycle of infinite length. We characterize the structure of α and use this characterization to extend a known result about orientation-preserving automorphisms of finite plane graphs to infinite plane graphs. In the last section we investigate the action of α on the ends ofX and show that α fixes at most two ends (Theorem 3.2).     

Quasi-random graphs

We introduce a large equivalence class of graph properties, all of which are shared by so-called random graphs. Unlike random graphs, however, it is often relatively easy to verify that a particular family of graphs possesses some property in this class.The authors wish to express their appreciation to N. Pippenger for several useful comments on an early draft of this paper.     

Edge-colored complete graphs with precisely colored subgraphs

Letf(s, t; k) be the largest value ofm such that it is possible tok-color the edges of the complete graphK _m so that everyK _s ⊆K _m has exactlyt colors occuring on its edges. The main object of this paper is to describe the behavior of the functionf(s,t;k), usually thinking ofs andt fixed, and lettingk become large. Dedicated to Paul Erdős on his seventieth birthday     

The asymptotic number of graphs not containing a fixed color-critical subgraph

For a finite graphG letForb(H) denote the class of all finite graphs which do not containH as a (weak) subgraph. In this paper we characterize the class of those graphsH which have the property that almost all graphs inForb(H) are -colorable. We show that this class corresponds exactly to the class of graphs whose extremal graph is the Turán-graphT _n ().An earlier result of Simonovits (Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions,Discrete Math. 7 (1974), 349–376) shows that these are exactly the (+1)-chromatic graphs which contain a color-critical edge.     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

Contractions of graphs with no spanning eulerian subgraphs

Letp2 be a fixed integer, and letG be a connected graph onn vertices. If(G)2, ifd(u)+d(v)>2n/p–2 holds wheneveruvE(G), and ifn is sufficiently large compared top, then eitherG has a spanning eulerian subgraph, orG is contractible to a graphG ₁ of order less thenp and with no spanning eulerian subgraph. The casep=2 was proved by Lesniak-Foster and Williamson. The casep=5 was conjectured by Benhocine, Clark, Köhler, and Veldman, when they proved virtually the casep=3. The inequality is best-possible.     

Spectral properties of the Laplacian on bond-percolation graphs

Bond-percolation graphs are random subgraphs of the d-dimensional integer lattice generated by a standard bond-percolation process. The associated graph Laplacians, subject to Dirichlet or Neumann conditions at cluster boundaries, represent bounded, self-adjoint, ergodic random operators with off-diagonal disorder. They possess almost surely the non-random spectrum [0, 4d] and a self-averaging integrated density of states. The integrated density of states is shown to exhibit Lifshits tails at both spectral edges in the non-percolating phase. While the characteristic exponent of the Lifshits tail for the Dirichlet (Neumann) Laplacian at the lower (upper) spectral edge equals d/2, and thus depends on the spatial dimension, this is not the case at the upper (lower) spectral edge,where the exponent equals 1/2.     

Some remarks on (k−1)-critical subgraphs ofk-critical graphs

A graphG is said to bek-critical if it has chromatic numberk, but every proper subgraph ofG has a (k–1)-coloring. Gallai asked whether every largek-critical graph contains many (k–1)-critical subgraphs. We provide some information concerning this question and some related questions.     

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.     

Edge disjoint spanning trees in random graphs

We show that almost everyG _m-out containsm edge disjoint spanning trees.     

The number of spanning trees of plane graphs with reflective symmetry

A plane graph is called symmetric if it is invariant under the reflection across some straight line (called symmetry axis). Let G be a symmetric plane graph. We prove that if there is no edge in G intersected by its symmetry axis then the number of spanning trees of G can be expressed in terms of the product of the number of spanning trees of two smaller graphs, each of which has about half the number of vertices of G.     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

Cancellation properties of products of graphs

This note extends results of Fernández, Leighton, and López-Presa on the uniqueness of rth roots for disconnected graphs with respect to the Cartesian product to other products and shows that their methods also imply new cancelation laws.     

How not to characterize planar-emulable graphs

We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph)—a problem raised already in Fellows? thesis (1985) and conceptually related to the better known planar cover conjecture by Negami (1986). For over two decades, the planar emulator problem lived poorly in a shadow of Negami?s conjecture—which is still open—as the two were considered equivalent. But, at the end of 2008, a surprising construction by Rieck and Yamashita falsified the natural “planar emulator conjecture”, and thus opened a whole new research field. We present further results and constructions which show how far the planar-emulability concept is from planar-coverability, and that the traditional idea of likening it to projective embeddability is actually very out-of-place. We also present several positive partial characterizations of planar-emulable graphs.