000			01717nam a2200265Ia 4500
008			160627s2014||||xx |||||||||||||| ||und||
080			_aHBNI Th68
100			_aKunal Dutta _eauthor
245			_aOn certain invariants of random digraphs and uniform hypergraphs
260			_c2014
300			_a123p.
502			_a2014
502			_bPh.D
502			_cHBNI
520	3		_aThis 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.
650	1	4	_aComputer Science
653	1	0	_aHBNI Th68
653	1	0	_aRandom Digraphs
653	1	0	_aRandom Graph Theory
653	1	0	_aUniform Hypergraphs
720	1		_aC.R. Subramanian _eThesis advisor [ths]
856			_uhttp://www.imsc.res.in/xmlui/handle/123456789/352
942			_2THESIS185 _cTHESIS
999			_c48890 _d48890