On certain invariants of random digraphs and uniform hypergraphs[HBNI Th68]

DSpace/Manakin Repository

On certain invariants of random digraphs and uniform hypergraphs[HBNI Th68]

Show simple item record

dc.contributor.author Kunal Dutta
dc.date.accessioned 2014-06-18T09:08:35Z
dc.date.available 2014-06-18T09:08:35Z
dc.date.issued 2014-06-18T09:08:35Z
dc.date.submitted 2014
dc.identifier.uri http://hdl.handle.net/123456789/352
dc.description.abstract 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. en_US
dc.subject Random Digraphs en_US
dc.subject Uniform Hypergraphs en_US
dc.subject Random Graph Theory en_US
dc.subject HBNI Th68 en_US
dc.title On certain invariants of random digraphs and uniform hypergraphs[HBNI Th68] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor C.R. Subramanian
dc.description.pages 123p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
HBNI Th 68.pdf 1.160Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account