Recent Extremal Problems in Combinatorics
In this dissertation,, we shall consider three problems in combinatorics and graph theory. These three problems can all be classified as extremal problems. The first chapter considers another variant of graph Ramsey theory. In 2003, Bollobas asked the following question: Whenever we colour the ed...
Lưu vào:
| Tác giả chính: | |
|---|---|
| Định dạng: | Luận án |
| Ngôn ngữ: | en_US |
| Thông tin xuất bản: |
The University Of Memphis
2007
|
| Chủ đề: | |
| Truy cập trực tuyến: | http://ir.vnulib.edu.vn/handle/123456789/1409 |
| Từ khóa: |
Thêm từ khóa bạn đọc
Không có từ khóa, Hãy là người đầu tiên gắn từ khóa cho biểu ghi này!
|
| id |
oai:192.168.1.90:123456789-1409 |
|---|---|
| record_format |
dspace |
| spelling |
oai:192.168.1.90:123456789-14092022-03-28T10:19:22Z Recent Extremal Problems in Combinatorics Liu, Henry Tổ hợp (Toán học) Đồ thị, Lý thuyết In this dissertation,, we shall consider three problems in combinatorics and graph theory. These three problems can all be classified as extremal problems. The first chapter considers another variant of graph Ramsey theory. In 2003, Bollobas asked the following question: Whenever we colour the edges of the complete graph Kn with r colours, on how many vertices can we find a k-connected subgraph using at most s colours? With Morris and Prince (see also [14], [15] and [16]), we were able to provide several partial solutions to Bollobas' question. However, the problem remains largely unsolved. So, we shall also provide many conjectures and open problems. The second chapter considers a well-known combinatorial geometry problem: The determination of the convex decomposition number F(n) of point sets in the plane. For each n > 3, we shall provide a construction of a point set An C 1[g2, where On = n and An is in general position. We then conjecture that this construction gives F(n) > n + [2L.22 -91 for n > 3. If this conjecture is true, then it disproves conjectures of Aichholzer and Krasser (2001) [1] and Neumann-Lara, Rivera-Campo and Urrutia (2004) [18]. We will also provide some new conjectures concerning what the true value of F(n) may be. The third chapter considers a set systems problem. In 1999, Cameron asked a question concerning a game played between two players, which later turned out to be equivalent to the following older problem: If A C P([n]), and for every A, B, C, D E A, we have AUB CUD, then how large can 1,A1 be? This second problem was considered by Erdos and Moser (1969) [7], and Frankl and Fiiredi (1984) [8]. Leader and Walters (2000) [25] studied both problems, including the observation of the above equivalence. In Chapter 3, we shall consider extensions to both problems. Throughout this dissertation, the symbol will either denote the end of the proof of a result, or is given with the statement of a result if either it is trivial, or if it has already been proved. Also, in all three chapters, we will be seeing constructions of many combinatorial objects. The symbol Q will denote the end of a construction. 2007-12-19T03:51:02Z 2007-12-19T03:51:02Z 2006 Thesis http://ir.vnulib.edu.vn/handle/123456789/1409 en_US Doctor of Philosophy application/pdf The University Of Memphis |
| institution |
Đại học Quốc Gia Hồ Chí Minh |
| collection |
DSpace |
| language |
en_US |
| topic |
Tổ hợp (Toán học) Đồ thị, Lý thuyết |
| spellingShingle |
Tổ hợp (Toán học) Đồ thị, Lý thuyết Liu, Henry Recent Extremal Problems in Combinatorics |
| description |
In this dissertation,, we shall consider three problems in combinatorics and graph theory. These three problems can all be classified as extremal problems.
The first chapter considers another variant of graph Ramsey theory. In 2003, Bollobas asked the following question: Whenever we colour the edges of the complete graph Kn with r colours, on how many vertices can we find a k-connected subgraph using at most s colours? With Morris and Prince (see also [14], [15] and [16]), we were able to provide several partial solutions to Bollobas' question. However, the problem remains largely unsolved. So, we shall also provide many conjectures and open problems.
The second chapter considers a well-known combinatorial geometry problem: The determination of the convex decomposition number F(n) of point sets in the plane. For each n > 3, we shall provide a construction of a point set An C 1[g2, where On = n and An is in general position. We then conjecture that this construction gives F(n) > n + [2L.22 -91 for n > 3. If this conjecture is true, then it disproves conjectures of Aichholzer and Krasser (2001) [1] and Neumann-Lara, Rivera-Campo and Urrutia (2004) [18]. We will also provide some new conjectures concerning what the true value of F(n) may be.
The third chapter considers a set systems problem. In 1999, Cameron asked a question concerning a game played between two players, which later turned out to be
equivalent to the following older problem: If A C P([n]), and for every A, B, C, D E A, we have AUB CUD, then how large can 1,A1 be? This second problem was considered by Erdos and Moser (1969) [7], and Frankl and Fiiredi (1984) [8]. Leader and Walters (2000) [25] studied both problems, including the observation of the above equivalence. In Chapter 3, we shall consider extensions to both problems.
Throughout this dissertation, the symbol will either denote the end of the proof of a result, or is given with the statement of a result if either it is trivial, or if it has already been proved. Also, in all three chapters, we will be seeing constructions of many combinatorial objects. The symbol Q will denote the end of a construction. |
| format |
Thesis |
| author |
Liu, Henry |
| author_facet |
Liu, Henry |
| author_sort |
Liu, Henry |
| title |
Recent Extremal Problems in Combinatorics |
| title_short |
Recent Extremal Problems in Combinatorics |
| title_full |
Recent Extremal Problems in Combinatorics |
| title_fullStr |
Recent Extremal Problems in Combinatorics |
| title_full_unstemmed |
Recent Extremal Problems in Combinatorics |
| title_sort |
recent extremal problems in combinatorics |
| publisher |
The University Of Memphis |
| publishDate |
2007 |
| url |
http://ir.vnulib.edu.vn/handle/123456789/1409 |
| work_keys_str_mv |
AT liuhenry recentextremalproblemsincombinatorics |
| _version_ |
1749008461160513536 |