Extremal results in sparse pseudorandom graphs

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.     

Embedding graphs with bounded degree in sparse pseudorandom graphs

In this paper, we show the equivalence of somequasi-random properties for sparse graphs, that is, graphsG with edge densityp=|E(G)|/( ₂ ⁿ )=o(1), whereo(1)→0 asn=|V(G)|→∞. Our main result (Theorem 16) is the following embedding result. For a graphJ, writeN _J(x) for the neighborhood of the vertexx inJ, and letδ(J) andΔ(J) be the minimum and the maximum degree inJ. LetH be atriangle-free graph and setd _H=max{δ(J):J⊆H}. Moreover, putD _H=min{2d _H,Δ(H)}. LetC>1 be a fixed constant and supposep=p(n)≫n ⁻¹ D _H. We show that ifG is such that

A spectral condition for odd cycles in graphs

Let G be a graph of sufficiently large order n, and let the largest eigenvalue μ(G) of its adjacency matrix satisfies . Then G contains a cycle of length t for every t?n/320This condition is sharp: the complete bipartite graph T₂(n) with parts of size ⌊n/2⌋ and ⌈n/2⌉ contains no odd cycles and its largest eigenvalue is equal to .This condition is stable: if μ(G) is close to and G fails to contain a cycle of length t for some t?n/321, then G resembles T₂(n).     

Homomorphisms of graphs into odd cycles

We give a class of graphs G for which there exists a homomorphism (= adjacency preserving map) from V(G) to V(C), where C is the shortest odd cycle in G, thereby extending a result of Albertson, Catlin, and Gibbons. Our class of graphs is characterized by the following property: For each odd subdivision G′ of G there exists a homomorphic map from V(G′) to V(C), where C′ is the shortest odd cycle of G′.     

Vertex colorings of graphs without short odd cycles

Motivated by the work of Ne?et?il and Rödl on “Partitions of vertices” we are interested in obtaining some quantitative extensions of their result. In particular, given a natural number r and a graph G of order m with odd girth g, we show the existence of a graph H with odd girth at least g and order that is polynomial in m such that every r‐coloring of the vertices of H yields a monochromatic and induced copy of G. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 255‐264, 2011     

Approximate min–max relations for odd cycles in planar graphs

We study the ratio between the minimum size of an odd cycle vertex transversal and the maximum size of a collection of vertex-disjoint odd cycles in a planar graph. We show that this ratio is at most 10. For the corresponding edge version of this problem, Král and Voss recently proved that this ratio is at most 2; we also give a short proof of their result. This work was supported by FNRS, NSERC (PGS Master award, Canada Research Chair in Graph Theory, award 288334-04) and FQRNT (award 2005-NC-98649).     

On hamiltonian cycles in the prism over the odd graphs

The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph O_k is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that O_k is hamiltonian for all k>2. We show that the prism over O_k is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011     

Short odd cycles in 4‐chromatic graphs

It is shown that any 4‐chromatic graph on n vertices contains an odd cycle of length smaller than √8n. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 145–147, 1999     

Topologically 4-chromatic graphs and signatures of odd cycles

We investigate group-theoretic “signatures” of odd cycles of a graph, and their connections to topological obstructions to 3-colourability. In the case of signatures derived from free groups, we prove that the existence of an odd cycle with trivial signature is equivalent to having the coindex of the hom-complex at least 2 (which implies that the chromatic number is at least 4). In the case of signatures derived from elementary abelian 2-groups we prove that the existence of an odd cycle with trivial signature is a sufficient condition for having the index of the hom-complex at least 2 (which again implies that the chromatic number is at least 4).     

Some results on odd factors of graphs

A {1, 3, …,2n ? 1}-factor of a graph G is defined to be a spanning subgraph of G, each degree of whose vertices is one of {1, 3, …, 2n ? 1}, where n is a positive integer. In this paper, we give a sufficient condition for a graph to have a {1, 3, …, 2n ? 1}-factor.     

Some large deviation results for sparse random graphs

Summary. We obtain a large deviation principle (LDP) for the relative size of the largest connected component in a random graph with small edge probability. The rate function, which is not convex in general, is determined explicitly using a new technique. The proof yields an asymptotic formula for the probability that the random graph is connected. We also present an LDP and related result for the number of isolated vertices. Here we make use of a simple but apparently unknown characterisation, which is obtained by embedding the random graph in a random directed graph. The results demonstrate that, at this scaling, the properties `connected' and `contains no isolated vertices' are not asymptotically equivalent. (At the threshold probability they are asymptotically equivalent.) Received: 14 November 1996 / In revised form: 15 August 1997     

Finding any given 2‐factor in sparse pseudorandom graphs efficiently

Given an $n$‐vertex pseudorandom graph $G$ and an $n$‐vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$, that is, an embedding $\phi :V\left(H\right)\to V\left(G\right)$ so that $\phi \left(u\right)\phi \left(v\right)\in E\left(G\right)$ for all $uv\in E\left(H\right)$. Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in $G$. Here, we provide a deterministic polynomial time algorithm that finds a given $H$ in any suitably pseudorandom graph $G$. The pseudorandom graphs we consider are $\left(p,\lambda \right)$‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, $\mathrm{\Omega }\left(pn\right)$. A $\left(p,\lambda \right)$‐bijumbled graph is characterised through the discrepancy property: $|e\left(A,B\right)?p|A||B||<\lambda \sqrt{|A||B|}$ for any two sets of vertices $A$ and $B$. Our condition $\lambda =O(p^{2}n/\log n)$ on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications.     

Small odd cycles in 4‐chromatic graphs*

It is shown that every 4‐chromatic graph on n vertices contains an odd cycle of length less than . This improves the previous bound given by Nilli [J Graph Theory 3 ( 3 ), 145–147]. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 115–117, 2001