Research interests

  • Extremal Graph Theory
  • Probabilistic Methods in Combinatorics
  • Combinatorial Algorithms

Research records


Encyclopedia articles related to my research


Some open problems

  • Long path in Eulerian directed graphs.
    Is it true that any simple Eulerian digraph with n vertices and m arcs has a simple path of length Ω(m/n)?
    See the following paper for more information.
  • Packing regular tournaments with small cycles.
    Is it true that any regular tournament with n vertices has (1-o(1))n^2/8 arc-disjoint cycles of length 4?
    Is it true that any regular tournament with n vertices has (1-o(1))n^2/9 arc-disjoint cycles of length 3?
    See the following paper for more information.
  • Detecting small complete hypergraphs.
    For k > r > 2 let K(k,r) denote the complete r-uniform hypergraph with k vertices. Is there an algorithm that, given an r-uniform hypergraph H with n vertices, decides whether K(k,r) is a sub-hypergraph of H in o(nk-ε) time? The answer is well-known for r=2 (graphs) but already the first nontrivial hypergraph case of r=3 and k=4 is open.
    See the following paper for more information.
  • Packing transitive triples in a tournament.
    Conjecture: Every tournament with n vertices contains a set of at least n(n-1)/6 - n/3 edge-disjoint transitive tournaments on three vertices. This has been verified for all n < 9. The conjecture appears here.
  • Monotone paths in planar graphs.
    For a simple undirected graph G, let f(G) be the minimum over all edge orderings of the maximum length of a monotone path. It is known that if G is planar then f(G) 9. There are constructions of planar graphs with f(G)=6. Any improvement upon these upper and lower bounds would be nice.
    See the following paper for more information.