TY  - BOOK
AU  - Kunal Dutta
TI  - On certain invariants of random digraphs and uniform hypergraphs
PY  - 2014///
KW  - Computer Science
KW  - HBNI Th68
KW  - Random Digraphs
KW  - Random Graph Theory
KW  - Uniform Hypergraphs
N1  - 2014
N2  - This thesis studies four problems on graphs using the Probabilistic Method. The first two  are  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 an improved lower bound on the independence number of certain uniform hypergraphs.  The last problem considers the independence number of Kr-free graphs and linear k-uniform hypergraphs in terms of the degree sequence, and obtain new lower bounds for them. This answers some old questions raised by Caro and Tuza [21]. The present proof technique is an extension of a method of Caro and Wei [20, 72], and also the author gives a new short proof of the main result of [21] using this approach. As byproducts, this study also obtain some non-trivial identities involving binomial coefficients, which may be of independent interest
UR  - http://www.imsc.res.in/xmlui/handle/123456789/352
ER  -