The main focus of this thesis is to evaluate .k_r(n,\delta)., the minimal number of $r$-cliques in graphs with $n$ vertices and minimum degree~$\delta$. A fundamental result in Graph Theory states that a triangle-free graph of order $n$ has at most $n 2/4$ edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if $k_3(n,\delta) =0$ then $\delta \le n/2$. For $n/2 \leq \delta \leq 4n/5$, I have evaluated $k_r(n,\delta)$ and determined the structures of the extremal graphs. For $\delta \ge 4n/5$, I give a conjecture on $k_r(n,\delta)$, as well as the structures of these extremal graphs. Moreover, I have proved various partial results that support this conjecture. Let $k_r �(n, \delta)$ be the analogous version of $k_r(n,\delta)$ for regular graphs. Notice that there exist $n$ and $\delta$ such that $k_r(n, \delta) =0$ but $k_r �(n, \delta) >0$. For example, a theorem of Andr{\'a}sfai, Erd{\H}s and S{\'o}s states that any triangle-free graph of order $n$ with minimum degree greater than $2n/5$ must be bipartite. Hence $k_3(n, \lfloor n/2 \rfloor) =0$ but $k_3 �(n, \lfloor n/2 \rfloor) >0$ for $n$ odd. I have evaluated the exact value $k_3 �(n, \delta)$ for $\delta$ between $2n/5+12 \sqrt{n}/5$ and $n/2$ and determined the structure of these extremal graphs. At the end of the thesis, I investigate a question in Ramsey Theory. The Ramsey number $R_k(G)$ of a graph $G$ is the minimum number $N$, such that any edge colouring of $K_N$ with $k$ colours contains a monochromatic copy of $G$. The constrained Ramsey number $f(G,T)$ of two graphs $G$ and $T$ is the minimum number $N$ such that any edge colouring of $K_N$ with any number of colours contains a monochromatic copy of $G$ or a rainbow copy of $T$. It turns out that these two quantities are closely related when $T$ is a matching. Namely, for almost all graphs $G$, $f(G,tK_2) =R_{t-1}(G)$ for $t \geq 2$.

In this dissertation we treat three tiling problems and three problems in combinatorial geometry, extremal graph theory and sparse Ramsey theory. We first consider tilings of $\mathbb{Z}^n$. In this setting a tile $T$ is just a finite subset of $\mathbb{Z}^n$. We say that $T$ tiles $\mathbb{Z}^n$ if the latter set admits a partition into isometric copies of $T$. Chalcraft observed that there exist $T$ that do not tile $\mathbb{Z}^n$ but tile $\mathbb{Z}^{d}$ for some $d > n$. He conjectured that such $d$ exists for any given tile. We prove this conjecture in Chapter 2. In Chapter 3 we prove a conjecture of Lonc, stating that for any poset $P$ of size a power of $2$, if $P$ has a greatest and a least element, then there is a positive integer $k$ such that $[2]^k$ can be partitioned into copies of $P$. The third tiling problem is about vertex-partitions of the hypercube graph $Q_n$. Offner asked: if $G$ is a subgraph of $Q_n$ such $|G|$ is a power of $2$, must $V(Q_d)$, for some $d$, admit a partition into isomorphic copies of $G$? In Chapter 4 we answer this question in the affirmative. We follow up with a question in combinatorial geometry. A line in a planar set $P$ is a maximal collinear subset of $P$. P\'or and Wood considered colourings of finite $P$ without large lines with a bounded number of colours. In particular, they examined whether monochromatic lines always appear in such colourings provided that $|P|$ is large. They conjectured that for all $k,l \ge 2$ there exists an $n \ge 2$ such that if $|P| \ge n$ and $P$ does not contain a line of cardinality larger than $l$, then every colouring of $P$ with $k$ colours produces a monochromatic line. In Chapter 5 we construct arbitrarily large counterexamples for the case $k=l=3$. We follow up with a problem in extremal graph theory. For any graph, we say that a given edge is triangular if it forms a triangle with two other edges. How few triangular edges can there be in a graph with $n$ vertices and $m$ edges? For sufficiently large $n$ we prove a conjecture of F\"uredi and Maleki that gives an exact formula for this minimum. This proof is given in Chapter 6. Finally, Chapter 7 is concerned with degrees of vertices in directed hypergraphs. One way to prescribe an orientation to an $r$-uniform graph $H$ is to assign for each of its edges one of the $r!$ possible orderings of its elements. Then, for any $p$-set of vertices $A$ and any $p$-set of indices $I \subset [r]$, we define the $I$-degree of $A$ to be the number of edges containing vertices $A$ in precisely the positions labelled by $I$. Caro and Hansberg were interested in determining whether a given $r$-uniform hypergraph admits an orientation where every set of $p$ vertices has some $I$-degree equal to $0$. They conjectured that a certain Hall-type condition is sufficient. We show that this is true for $r$ large, but false in general.

abstract: Since the seminal work of Tur ́an, the forbidden subgraph problem has been among the central questions in extremal graph theory. Let ex(n;F) be the smallest number m such that any graph on n vertices with m edges contains F as a subgraph. Then the forbidden subgraph problem asks to find ex(n; F ) for various graphs F . The question can be further generalized by asking for the extreme values of other graph parameters like minimum degree, maximum degree, or connectivity. We call this type of question a Tura ́n-type problem. In this thesis, we will study Tura ́n-type problems and their variants for graphs and hypergraphs. Chapter 2 contains a Tura ́n-type problem for cycles in dense graphs. The main result in this chapter gives a tight bound for the minimum degree of a graph which guarantees existence of disjoint cycles in the case of dense graphs. This, in particular, answers in the affirmative a question of Faudree, Gould, Jacobson and Magnant in the case of dense graphs. In Chapter 3, similar problems for trees are investigated. Recently, Faudree, Gould, Jacobson and West studied the minimum degree conditions for the existence of certain spanning caterpillars. They proved certain bounds that guarantee existence of spanning caterpillars. The main result in Chapter 3 significantly improves their result and answers one of their questions by proving a tight minimum degree bound for the existence of such structures. Chapter 4 includes another Tur ́an-type problem for loose paths of length three in a 3-graph. As a corollary, an upper bound for the multi-color Ramsey number for the loose path of length three in a 3-graph is achieved. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2018

In this dissertation, we are interested in studying several parameters of graphs and understanding their extreme values. We begin in Chapter~$2$ with a question on edge colouring. When can a partial proper edge colouring of a graph of maximum degree $\Delta$ be extended to a proper colouring of the entire graph using an `optimal' set of colours? Albertson and Moore conjectured this is always possible provided no two precoloured edges are within distance $2$. The main result of Chapter~$2$ comes close to proving this conjecture. Moreover, in Chapter~$3$, we completely answer the previous question for the class of planar graphs. Next, in Chapter~$4$, we investigate some Ramsey theoretical problems. We determine exactly what minimum degree a graph $G$ must have to guarantee that, for any two-colouring of $E(G)$, we can partition $V(G)$ into two parts where each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct colours. The following saturation problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger is considered in Chapter~$5$. Given a graph $H$ and a set of colours $\{1,2,\ldots,t\}$ (for some integer $t\geq |E(H)|$), we define $sat_{t}(n, R(H))$ to be the minimum number of $t$-coloured edges in a graph on $n$ vertices which does not contain a rainbow copy of $H$ but the addition of any non-edge in any colour from $\{1,2,\ldots,t\}$ creates such a copy. We prove several results concerning these extremal numbers. In particular, we determine the correct order of $sat_{t}(n, R(H))$, as a function of $n$, for every connected graph $H$ of minimum degree greater than $1$ and for every integer $t\geq e(H)$. In Chapter~$6$, we consider the following question: under what conditions does a Hamiltonian graph on $n$ vertices possess a second cycle of length at least $n-o(n)$? We prove that the `weak' assumption of a minimum degree greater or equal to $3$ guarantees the existence of such a long cycle. We solve two problems related to majority colouring in Chapter~$7$. This topic was recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number $k$, the smallest positive integer $m = m(k)$ such that every digraph can be coloured with $m$ colours, where each vertex has the same colour as at most a proportion of $\frac{1}{k}$ of its out-neighbours. Our main theorem states that $m(k) \in \{2k-1, 2k\}$. We study the following problem, raised by Caro and Yuster, in Chapter~$8$. Does every graph $G$ contain a `large' induced subgraph $H$ which has $k$ vertices of degree exactly $\Delta(H)$? We answer in the affirmative an approximate version of this question. Indeed, we prove that, for every $k$, there exists $g(k)$ such that any $n$ vertex graph $G$ with maximum degree $\Delta$ contains an induced subgraph $H$ with at least $n-g(k)\sqrt{\Delta}$ vertices such that $V(H)$ contains at least $k$ vertices of the same degree $d \ge \Delta(H)-g(k)$. This result is sharp up to the order of $g(k)$. %Subsequently, we investigate a concept called $\textit{path-pairability}$. A graph is said to be path-pairable if for any pairing of its vertices there exist a collection of edge-disjoint paths routing the the vertices of each pair. A question we are concerned here asks whether every planar path pairable graph on $n$ vertices must possess a vertex of degree linear in $n$. Indeed, we answer this question in the affirmative. We also sketch a proof resolving an analogous question for graphs embeddable on surfaces of bounded genus. Finally, in Chapter~$9$, we move on to examine $k$-linked tournaments. A tournament $T$ is said to be $k$-linked if for any two disjoint sets of vertices $\{x_1,\ldots ,x_k\}$ and $\{y_1,\dots,y_k\}$ there are directed vertex disjoint paths $P_1,\dots, P_k$ such that $P_i$ joins $x_i$ to $y_i$ for $i = 1,\ldots, k$. We prove that any $4k$ strongly-connected tournament with sufficiently large minimum out-degree is $k$-linked. This result comes close to proving a conjecture of Pokrovskiy.

In a 2011 paper by Beeler and Hoilman, the game of peg solitaire is generalized to arbitrary boards. These boards are treated as graphs in the combinatorial sense. An open problem from that paper is to determine the minimum number of edges necessary for a graph with a fixed number of vertices to be solvable. This thesis provides new bounds on this number. It also provides necessary and sufficient conditions for two families of graphs to be solvable, along with criticality results, and the maximum number of pegs that can be left in each of the two graph families.

We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, which invokes Alon's combinatorial nullstellensatz. This method usually requires computer power to complete the calculations needed for even a modest-sized hypergraph. The other method is elementary, and uses the idea of minimum improper colourings. We apply these methods to various classes of hypergraphs, including the projective planes. We focus on solving the list-colouring problem for Steiner triple systems (STS). It is not hard using either method to determine that Steiner triple systems of orders 7, 9 and 13 are 3-list-chromatic. For systems of order 15, we show that they are 4-list-colourable, but they are also ``almost'' 3-list-colourable. For all Steiner triple systems, we prove a couple of simple upper bounds on their list-chromatic numbers. Also, unlike ordinary colouring where a 3-chromatic STS exists for each admissible order, we prove using probabilistic methods that for every $s$, every STS of high enough order is not $s$-list-colourable. The second problem is on embedding nearly-spanning bounded-degree trees in sparse graphs. We determine sufficient conditions based on expansion properties for a sparse graph to embed every nearly-spanning tree of bounded degree. We then apply this to random graphs, addressing a question of Alon, Krivelevich and Sudakov, and determine a probability $p$ where the random graph $G_{n,p}$ asymptotically almost surely contains every tree of bounded degree. This $p$ is nearly optimal in terms of the maximum degree of the trees that we embed. Finally, we solve a problem that arises from quantum computing, which can be formulated as an extremal question about maximizing the size of a type of acyclic directed graph.

We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, which invokes Alon's combinatorial nullstellensatz. This method usually requires computer power to complete the calculations needed for even a modest-sized hypergraph. The other method is elementary, and uses the idea of minimum improper colourings. We apply these methods to various classes of hypergraphs, including the projective planes. We focus on solving the list-colouring problem for Steiner triple systems (STS). It is not hard using either method to determine that Steiner triple systems of orders 7, 9 and 13 are 3-list-chromatic. For systems of order 15, we show that they are 4-list-colourable, but they are also ``almost'' 3-list-colourable. For all Steiner triple systems, we prove a couple of simple upper bounds on their list-chromatic numbers. Also, unlike ordinary colouring where a 3-chromatic STS exists for each admissible order, we prove using probabilistic methods that for every $s$, every STS of high enough order is not $s$-list-colourable. The second problem is on embedding nearly-spanning bounded-degree trees in sparse graphs. We determine sufficient conditions based on expansion properties for a sparse graph to embed every nearly-spanning tree of bounded degree. We then apply this to random graphs, addressing a question of Alon, Krivelevich and Sudakov, and determine a probability $p$ where the random graph $G_{n,p}$ asymptotically almost surely contains every tree of bounded degree. This $p$ is nearly optimal in terms of the maximum degree of the trees that we embed. Finally, we solve a problem that arises from quantum computing, which can be formulated as an extremal question about maximizing the size of a type of acyclic directed graph.

of doctoral thesis Structural graph theory Jan Hladký In the thesis we make progress on the Loebl-Komlós-Sós Conjecture which is a classic problem in the field of Extremal Graph Theory. We prove the following weaker version of the Conjecture: For every α > 0 there exists a number k0 such that for every k > k0 we have that every n-vertex graph G with at least (1 2 +α)n vertices of degrees at least (1+α)k contains each tree T of order k as a subgraph. The proof of our result follows a strategy common to approaches which employ the Szemerédi Regularity Lemma: the graph G is decomposed, a suitable combinatorial structure inside the decomposition is found, and then the tree T is embedded into G using this structure. However the decomposition given by the Regularity Lemma is not of help when G sparse. To surmount this shortcoming we develop a decomposition technique that applies also to sparse graphs: each graph can be decomposed into vertices of huge degrees, regular pairs (in the sense of the Regularity Lemma), and two other components each exhibiting certain expander-like properties. The results were achieved in a joint work with János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein and Endre Szemerédi. 1

The need to understand the structure of complex networks increases as both their complexity and the dependency of human society on them grows. Network centralities help to recognize the key elements of these networks. Betweenness centrality is a network centrality measure based on shortest paths. More precisely, the contribution of a pair of vertices u, v to a vertex w ̸= u, v is the fraction of the shortest uv-paths which lead through w. Betweenness centrality is then given by the sum of contributions of all pairs of vertices u, v ̸= w to w. In this work, we have summarized known results regarding both exact values and bounds on betweenness. Additionally, we have improved an existing bound and obtained more exact formulation for r-regular graphs. We have made two major contributions about betweenness uniform graphs, whose vertices have uniform betweenness value. The first is that all betweenness uniform graphs of order n with maximal degree n − k have diameter at most k, by which we have solved a conjecture posed in the literature. The second major result is that betweenness uniform graphs nonisomorphic to a cycle that are either vertex- or edge-transitive are 3-connected, by which we have partially solved another conjecture. 1

In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property. The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows. In Chapter 2, we explore conditions for a graph to be supereulerian.In Section 1 of Chapter 2, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we strengthen the result in [93] and we also address a conjecture in the paper.In Section 2 of Chapter 2, we prove that if $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$ to be supereulerian is obtained. This result extends the result in [21].In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai [Conjecture~8.6 of [33]] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton- connected which strengthens the result in [91].In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $F\subseteq E(Cay(B:S_{n}))$, if $|F|\leq n-3$ and $n\geq4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not a star graph, $n\geq4$ and $|F|\leq n-3$.In Chapter 5, we consider several extremal problems on the size of graphs.In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $\sum\limits_{i=0}^ {s}2^{t_i}$, $t_0=[\log_2m]$ and $t_i= [\log_2({m-\sum\limits_{r=0}^{i-1}2 ^{t_r}})]$ for $i\geq1$) vertices of an $n$-cube (hypercube) has at most $\sum\limits_{i=0}^{s}t_i2^{t_i-1} +\sum\limits_{i=0}^{s} i\cdot2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $m\leq2^{[\frac{n}2]}$ and $g$-extra edge-connectivity of the folded hypercube for $g\leq n$.In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of minimumrestricted edge connected graphs.In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.