On certain invariants of random digraphs and uniform hypergraphs (Record no. 48890)
[ view plain ]
000 -LEADER | |
---|---|
fixed length control field | 01717nam a2200265Ia 4500 |
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
fixed length control field | 160627s2014||||xx |||||||||||||| ||und|| |
080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
Universal Decimal Classification number | HBNI Th68 |
100 ## - MAIN ENTRY--AUTHOR NAME | |
Personal name | Kunal Dutta |
Relator term | author |
245 ## - TITLE STATEMENT | |
Title | On certain invariants of random digraphs and uniform hypergraphs |
260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
Year of publication | 2014 |
300 ## - PHYSICAL DESCRIPTION | |
Number of Pages | 123p. |
502 ## - DISSERTATION NOTE | |
Dissertation note | 2014 |
502 ## - DISSERTATION NOTE | |
Degree Type | Ph.D |
502 ## - DISSERTATION NOTE | |
Name of granting institution | HBNI |
520 3# - SUMMARY, ETC. | |
Summary, etc | 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. |
650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical Term | Computer Science |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | HBNI Th68 |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | Random Digraphs |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | Random Graph Theory |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | Uniform Hypergraphs |
720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
Thesis Advisor | C.R. Subramanian |
Relator term | Thesis advisor [ths] |
856 ## - ELECTRONIC LOCATION AND ACCESS | |
Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/352 |
942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
Koha item type | THESIS & DISSERTATION |
Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
---|---|---|---|---|---|---|---|---|
IMSc Library | HBNI Th68 | 70522 | http://www.imsc.res.in/xmlui/handle/123456789/352 | THESIS & DISSERTATION |