The dissertation consists of two parts. In the first part several asymptotic properties of random intersection graphs are studied. They include birth thresholds for small complete subgraphs in the binomial random intersection graph, the clique number in sparse random intersection graphs and the chromatic index of random uniform hypergraphs. Several new methods and theoretically and practically relevant algorithms are proposed. Some results are illustrated with data from real-world networks. The second part deals with asymptotic enumeration and properties of graphs from minor-closed classes in the case when the excluded minors are disjoint. The class of graphs without k+1 (vertex-)disjoint cycles and more general classes of graphs without k+1 disjoint excluded minors (satisfying a condition related to fans) are considered. Typical graphs in such classes are shown to have a simple “k apex vertex” structure. Other asymptotic properties (connectivity, number of components, chromatic number, vertex degrees) are also determined. Finally, it is shown that typical graphs without k+1 disjoint minors K4 have a more complicated “2k+1 apex vertex” structure, and properties of such graphs are investigated. Part of the results is proved in greater generality. A variety of methods from computer science, graph theory, combinatorics and the theory of generating functions are applied. / Disertacijoje yra dvi pagrindinės dalys. Pirmojoje dalyje gaunami keli nauji rezultatai uždaviniams, susijusiems su atsitiktiniais sankirtų grafais. Nagrinėjamas pilnojo pografio gimimo slenkstis binominiame atsitiktiniame sankirtų grafe, didžiausios klikos eilė atsitiktiniame retame sankirtų grafe ir chromatinio indekso eilė atsitiktiniame reguliariajame hipergrafe. Sprendimams pasiūloma keletas naujų metodų, taip pat pateikiami teoriškai ir praktiškai svarbūs algoritmai. Kai kurie rezultatai iliustruojami duomenimis iš realių tinklų. Antrojoje dalyje pristatomi rezultatai grafų su uždraustaisiais minorais tematikoje, nagrinėjamas atvejis kai uždraustieji minorai yra nejungūs. Čia tiriamas asimptotinis grafų, neturinčių k+1 nepriklausomų ciklų, skaičius, rezultatai apibendrinami grafų, neturinčių k+1 uždraustųjų minorų, tačiau tenkinančių tam tikrą „vėduoklės“ apribojimą, klasėms. Įrodoma, kad tipiniai tokių klasių grafai turi paprastą „k dydžio blokatoriaus“ struktūrą, nustatomos kitos tokių grafų asimptotinės savybės (jungumas, komponenčių skaičius, viršūnių laipsniai). Galiausiai parodoma, kad tipiniai grafai, neturintys k+1 nepriklausomų minorų K4 turi sudėtingesnę „2k+1 dydžio blokatoriaus“ struktūrą ir ištiriamos kitos jų savybės. Dalis šių rezultatų įrodoma daug bendresniu atveju. Darbe pasitelkiami įvairūs informatikos, kombinatorikos, grafų, tikimybių ir generuojančiųjų funkcijų teorijos metodai.
| Identifer | oai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2013~D_20131216_081822-36288 |
| Date | 16 December 2013 |
| Creators | Kurauskas, Valentas |
| Contributors | MANSTAVIČIUS, EUGENIJUS, BAREIKIS, GINTAUTAS, BIKELIS, ALGIMANTAS JONAS, DUBICKAS, ARTŪRAS, JANUŠKEVIČIUS, ROMANAS, KRYLOVAS, ALEKSANDRAS, MAČIULIS, ALGIRDAS, Vilnius University |
| Publisher | Lithuanian Academic Libraries Network (LABT), Vilnius University |
| Source Sets | Lithuanian ETD submission system |
| Language | English |
| Detected Language | Unknown |
| Type | Doctoral thesis |
| Format | application/pdf |
| Source | http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2013~D_20131216_081822-36288 |
| Rights | Unrestricted |
Page generated in 0.0029 seconds