Pseudorandom Graphs

On the informal level, a graph is called pseudorandom if it resembles truly random graphs in some sense. What exactly this "some sense" is could be up for debate, but as it turns out a number of meaningful random-like properties are equivalent (see the works of Thomason and Chung, Graham and Wilson.)
One of the ways to measure randomness of a d-regular graph G is the so-called eigenvalue gap, i.e. how small the second eigenvalue of the adjacency matrix of G is compared to d. This is the approach considered in some of the following papers.
A very useful approach in proving graph theoretic statements for random graphs is to isolate appropriate pseudorandom properties which (1) hold for the random graph in question and (2) imply the graph theoretic statement in question.

• On covering expander graphs with Hamilton cycles (with R. Glebov, M. Krivelevich), Random Structures and Algorithms, to appear.


• Sharp threshold for the appearance of certain spanning trees in random graphs (with D. Hefetz, M. Krivelevich), Random Structures and Algorithms 41(2012), 391-412.


• Hamilton cycles in highly connected and expanding graphs (with D. Hefetz, M. Krivelevich), Combinatorica ,29 (2009), 547-568.


• Bart-Moe games, JumbleG and Discrepancy (with D. Hefetz, M. Krivelevich), European Journal of Combinatorics, 28, (2007), 1131-1143.
  A generalization of the JumbleG-paper to the (p:1) biased game: we give a strategy for Maker to build a pseudorandom graph of density p/(p+1). The player's names are motivated by the Simpsons. They represent the fact that the first player plays as BreakerandAvoider and the second player as MakerorEnforcer. The similar question in the (1:q) game poses an unexpected challange. This was resolved by Beck in his soon(?) to be published book "Tic-Tac-Toe Theory".


• The game of JumbleG, (with A. Frieze, M. Krivelevich, O. Pikhurko), Combinatorics, Probability and Computing, 14 (2005) 783-793.
  We consider Maker/Breaker games played on the edges of the complete graph. We give a strategy for Maker to create a pseudorandom graph of density 1/2. Applying known results for pseudorandom graphs, this also gives a strategy for Maker in several other games studied earlier; for example Maker is able to build (1+o(1))n/4 edge-disjoint Hamiltonian cycles.
  


• A generalization of Turán's theorem, (with B. Sudakov and V.H. Vu), Journal of Graph Theory, 49 (2005), 187-195.
  Asymptotically, Turán's Theorem states that one needs to delete at least 1/(t-1)-fraction of the edges of the complete graph on n vertices in order to get rid of all t-cliques. We generalize this statement for graphs which are much sparser than the complete graph, in fact their degree could be as low as n^1-ε_t, provided they are pseudorandom. Our theorem is tight for triangles.


• Triangle factors in sparse pseudorandom graphs, (with M. Krivelevich, B. Sudakov), Combinatorica, 24 no.3. (2004) 403-426.
  The famous Blow-Up Lemma guarantees the existence of bounded degree spanning subgraphs in dense pseudorandom graphs. We study an important special case of this statement for sparse pseudorandom graphs. How sparse pseudorandom graphs are still guaranteed to contain a triangle factor? We obtain that under strong pseudorandom conditions this degree could be as low as n^4/5 polylog n. On the other hand degree n^2/3 is not enough.


• On the spectrum of projective norm-graphs, Information Processing Letters, 86 no. 2. (2003) 71-74.
  In this note the spectrum of an old love (the projective norm-graphs, see the Algebra in Combinatorics link) is calculated precisely, by observing that all eigenvalues are (possibly signed) Gaussian sums. The second eigenvalue is as small as it can be (asymptotically the square root of the degree), so the projective norm-graphs are as pseudorandom as it gets.