Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for +publisher:"ETH Zürich" +contributor:("Sudakov, Benny"). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


ETH Zürich

1. Kamčev, Nina. Colourings of Graphs and Words.

Degree: 2018, ETH Zürich

Extremal graph theory is concerned with the extreme values of a graph parameter over various classes of graphs. Randomised constructions have played a major role in extremal combinatorics. This phenomenon acted as a catalyst for the development of probabilistic combinatorics and the theory of random graphs as independent research areas. In the present thesis, we consider three graph parameters – anagram-chromatic number, rainbow connectivity and zero forcing number. Each of them is lower-bounded by a corresponding well-studied parameter (the Thue-chromatic number, diameter and minimum rank respectively). Our aim is to understand the hierarchy of graphs delineated by the parameter in consideration, and to highlight the role of random graphs as a surprising or close-to-optimal examples. Furthermore, we analyse a random graph process constrained to the König property. A graph is called König if the size of its maximum matching is equal to the order of its minimal vertex cover. We answer questions about the evolution and the final outcome of the process. A common feature of our proofs is that parts of them parallel classical problems concerning existence of relevant substructures in random graphs (Hamilton cycle, spanning tree, independent set, perfect matching). This allows us to rely on some well-known approaches. The second part of the thesis contains two Ramsey-type results. A catchphrase of Ramsey theory is that ‘any sufficiently large structure contains a well-organised substructure’. Let c be an edge-colouring of the complete n-vertex graph. The problem of finding properly coloured and rainbow Hamilton cycles in c was initiated in 1976 by Bollobás and Erdős and has been extensively studied since then. We study the problem in a more general hypergraph setting, giving sufficient local (resp. global) restrictions on the colourings which guarantee a properly coloured (resp. rainbow) copy of a given hypergraph G. We also look at multipartite analogues of these questions. In our final chapter, the ‘well-organised substructure’ of interest is a combinatorial line in [m]^n. The Hales–Jewett theorem states that for any m and r there exists an n such that any r-colouring of the elements of [m]^n contains a monochromatic combinatorial line. We look more closely at the obtained combinatorial line and prove tight results about the structure of its active coordinate set. Advisors/Committee Members: Sudakov, Benny, Axenovich, Maria.

Subjects/Keywords: random graphs; Ramsey theory; Graph theory; Random regular graph; Random processes; Hales-Jewett theorem; Local lemma; info:eu-repo/classification/ddc/510; Mathematics

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Kamčev, N. (2018). Colourings of Graphs and Words. (Doctoral Dissertation). ETH Zürich. Retrieved from http://hdl.handle.net/20.500.11850/282692

Chicago Manual of Style (16th Edition):

Kamčev, Nina. “Colourings of Graphs and Words.” 2018. Doctoral Dissertation, ETH Zürich. Accessed July 11, 2020. http://hdl.handle.net/20.500.11850/282692.

MLA Handbook (7th Edition):

Kamčev, Nina. “Colourings of Graphs and Words.” 2018. Web. 11 Jul 2020.

Vancouver:

Kamčev N. Colourings of Graphs and Words. [Internet] [Doctoral dissertation]. ETH Zürich; 2018. [cited 2020 Jul 11]. Available from: http://hdl.handle.net/20.500.11850/282692.

Council of Science Editors:

Kamčev N. Colourings of Graphs and Words. [Doctoral Dissertation]. ETH Zürich; 2018. Available from: http://hdl.handle.net/20.500.11850/282692


ETH Zürich

2. Vieira, Pedro. Problems on Random Graphs and Set Systems.

Degree: 2017, ETH Zürich

Subjects/Keywords: info:eu-repo/classification/ddc/510; Mathematics

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Vieira, P. (2017). Problems on Random Graphs and Set Systems. (Doctoral Dissertation). ETH Zürich. Retrieved from http://hdl.handle.net/20.500.11850/176516

Chicago Manual of Style (16th Edition):

Vieira, Pedro. “Problems on Random Graphs and Set Systems.” 2017. Doctoral Dissertation, ETH Zürich. Accessed July 11, 2020. http://hdl.handle.net/20.500.11850/176516.

MLA Handbook (7th Edition):

Vieira, Pedro. “Problems on Random Graphs and Set Systems.” 2017. Web. 11 Jul 2020.

Vancouver:

Vieira P. Problems on Random Graphs and Set Systems. [Internet] [Doctoral dissertation]. ETH Zürich; 2017. [cited 2020 Jul 11]. Available from: http://hdl.handle.net/20.500.11850/176516.

Council of Science Editors:

Vieira P. Problems on Random Graphs and Set Systems. [Doctoral Dissertation]. ETH Zürich; 2017. Available from: http://hdl.handle.net/20.500.11850/176516


ETH Zürich

3. Korándi, Dániel. Some Extremal Problems about Saturation and Random Graphs.

Degree: 2016, ETH Zürich

Subjects/Keywords: BIGRAPHEN (GRAPHENTHEORIE); ZUFALLSGRAPHEN (GRAPHENTHEORIE); EXTREMALPROBLEME (GRAPHENTHEORIE); ZYKLEN (GRAPHENTHEORIE); BIGRAPHS (GRAPH THEORY); RANDOM GRAPHS (GRAPH THEORY); EXTREMAL PROBLEMS (GRAPH THEORY); CYCLES (GRAPH THEORY); info:eu-repo/classification/ddc/510; Mathematics

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Korándi, D. (2016). Some Extremal Problems about Saturation and Random Graphs. (Doctoral Dissertation). ETH Zürich. Retrieved from http://hdl.handle.net/20.500.11850/155686

Chicago Manual of Style (16th Edition):

Korándi, Dániel. “Some Extremal Problems about Saturation and Random Graphs.” 2016. Doctoral Dissertation, ETH Zürich. Accessed July 11, 2020. http://hdl.handle.net/20.500.11850/155686.

MLA Handbook (7th Edition):

Korándi, Dániel. “Some Extremal Problems about Saturation and Random Graphs.” 2016. Web. 11 Jul 2020.

Vancouver:

Korándi D. Some Extremal Problems about Saturation and Random Graphs. [Internet] [Doctoral dissertation]. ETH Zürich; 2016. [cited 2020 Jul 11]. Available from: http://hdl.handle.net/20.500.11850/155686.

Council of Science Editors:

Korándi D. Some Extremal Problems about Saturation and Random Graphs. [Doctoral Dissertation]. ETH Zürich; 2016. Available from: http://hdl.handle.net/20.500.11850/155686

.