Room 327

On Certain Invariants of Random Digraphs and Uniform Hypergraphs

Kunal Dutta

Max-Planck Institute fur Informatik, Saarbrucken, Germany

In this thesis, we study four problems on random directed and
undirected graphs,
as well as arbitrary hypergraphs using a probabilistic approach.
The first two problems deal with
finding the maximum size of an induced acyclic
tournament and acyclic subgraph respectively, in random directed graphs.
The third one deals with finding the maximum size of an induced path,
cycle or tree, in a random graph, while the last one is about a new
lower bound on the independence number of certain uniform hypergraphs.

For the problems on random directed graphs, we give various upper
and lower bounds on the
concentration of the invariants studied, as well as average-case
analysis of some algorithms to find largest possible substructures
corresponding to these invariants.
We use a random digraph model similar
to the well-known Erd\H{o}s-R\'{e}nyi model for random graphs.

We further give bounds on the concentration of the size
of the largest induced paths, cycles and trees in random graphs, in the
Erd\H{o}s-R\'{e}nyi model. Finally,
we give lower bounds on the independence number of \emph{arbitrary}
hypergraphs, using random permutations.