A density result for random sparse oriented graphs and its relation to a conjecture of Woodall.
An algorithmic Friedman-Pippenger theorem on tree embeddings and applications.
On the resilience of long cycles in random graphs.
Arithmetic progressions of length three in subsets of a random set
Discrepancy and eigenvalues of Cayley graphs
We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This affirmatively answers a question of Chung and Graham (2002) for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.
A note on the Size-Ramsey number of long subdivisions of graphs
Let be the graph obtained from a given graph by subdividing each edge times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph , there exist graphs with edges that are Ramsey with respect to .
A note on the Size-Ramsey number of long subdivisions of graphs
Let be the graph obtained from a given graph by subdividing each edge times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in (SODA 2002) 321–328], we prove that, for any graph , there exist graphs with edges that are Ramsey with respect to .
Page 1