Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `+publisher:"ETH Zürich" +contributor:("Sudakov, Benny")`

.
Showing records 1 – 3 of
3 total matches.

▼ Search Limiters

ETH Zürich

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

Degree: 2018, ETH Zürich

URL: http://hdl.handle.net/20.500.11850/282692

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 Details Similar Records

❌

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

APA (6^{th} 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 (16^{th} 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 (7^{th} 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

URL: http://hdl.handle.net/20.500.11850/176516

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

Record Details Similar Records

❌

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

APA (6^{th} 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 (16^{th} 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 (7^{th} 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

URL: http://hdl.handle.net/20.500.11850/155686

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 Details Similar Records

❌

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

APA (6^{th} 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 (16^{th} 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 (7^{th} 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