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
randomlike properties are equivalent (see the works of Thomason and
Chung, Graham and Wilson.)
One of the ways to measure randomness of a dregular
graph G is the socalled
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), 391412.

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

BartMoe games, JumbleG and Discrepancy
(with D. Hefetz, M. Krivelevich),
European Journal of Combinatorics, 28,
(2007), 11311143.
A generalization of the JumbleGpaper 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
"TicTacToe Theory".

The game of JumbleG,
(with A. Frieze, M. Krivelevich, O. Pikhurko),
Combinatorics, Probability and Computing,
14 (2005) 783793.
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 edgedisjoint
Hamiltonian cycles.

A generalization of Turán's theorem,
(with B. Sudakov and V.H. Vu),
Journal of Graph Theory,
49 (2005), 187195.
Asymptotically,
Turán's Theorem states that one needs to delete at least
1/(t1)fraction of the edges of the complete graph on n
vertices in order to get rid of all tcliques. 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) 403426.
The famous BlowUp 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 normgraphs,
Information Processing Letters,
86 no. 2. (2003) 7174.
In this note the spectrum of an old love (the projective normgraphs,
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 normgraphs are as pseudorandom as it gets.
Last modified: Sun Jun 30 22:52:46 CEST 2013