Academic literature on the topic 'Combinatorics. graph theory'

We present a novel theorem of Borel Combinatorics that sheds light on the types of continuous functions that can be defined on the Cantor space. We specifically consider the part X=F(2ᴳ) from the Cantor space, where the group G is the additive group of integer pairs ℤ². That is, X is the set of aperiodic {0,1} labelings of the two-dimensional infinite lattice graph. We give X the Bernoulli shift action, and this action induces a graph on X in which each connected component is again a two-dimensional lattice graph. It is folklore that no continuous (indeed, Borel) function provides a two-coloring of the graph on X, despite the fact that any finite subgraph of X is bipartite. Our main result offers a much more complete analysis of continuous functions on this space. We construct a countable collection of finite graphs, each consisting of twelve "tiles", such that for any property P (such as "two-coloring") that is locally recognizable in the proper sense, a continuous function with property P exists on X if and only if a function with a corresponding property P' exists on one of the graphs in the collection. We present the theorem, and give several applications.

There has been much recent interest in random graphs sampled uniformly from the set of (labelled) graphs on n vertices in a suitably structured class A. An important and well-studied example of such a suitable structure is bridge-addability, introduced in 2005 by McDiarmid et al. in the course of studying random planar graphs. A class A is bridge-addable when the following holds: if we take any graph G in A and any pair u,v of vertices that are in different components in G, then the graph G′ obtained by adding the edge uv to G is also in A. It was shown that for a random graph sampled from a bridge-addable class, the probability that it is connected is always bounded away from 0, and the number of components is bounded above by a Poisson law. What happens if ’bridge-addable’ is replaced by something weaker? In this thesis, this question is explored in several different directions. After an introductory chapter and a chapter on generating function methods presenting standard techniques as well as some new technical results needed later, we look at minor-closed, labelled classes of graphs. The excluded minors are always assumed to be connected, which is equivalent to the class A being decomposable - a graph is in A if and only if every component of the graph is in A. When A is minor-closed, decomposable and bridge-addable various properties are known (McDiarmid 2010), generalizing results for planar graphs. A minor-closed class is decomposable and bridge-addable if and only if all excluded minors are 2-connected. Chapter 3 presents a series of examples where the excluded minors are not 2-connected, analysed using generating functions as well as techniques from graph theory. This is a step towards a classification of connectivity behaviour for minor-closed classes of graphs. In contrast to the bridge-addable case, different types of behaviours are observed. Chapter 4 deals with a new, more general vari- ant of bridge-addability related to edge-expander graphs. We will see that as long as we are allowed to introduce ’sufficiently many’ edges between components, the number of components of a random graph can still be bounded above by a Pois- son law. In this context, random forests in Kn,n are studied in detail. Chapter 5 takes a different approach, and studies the class of labelled forests where some vertices belong to a specified stable set. A weighting parameter y for the vertices belonging to the stable set is introduced, and a graph is sampled with probability proportional to y*s where s is the size of its stable set. The behaviour of this class is studied for y tending to ∞. Chapters 6 concerns random graphs sampled from general decomposable classes. We investigate the minimum size of a component, in both the labelled and the unlabelled case.

What is the cohomology of a graph? Cohomology is a topological invariant and encodes such information as genus and euler characteristic. Graphs are combinatorial objects which may not a priori admit a natural and isomorphism invariant cohomology ring. In this project, given any finite graph G, we constructively define a cohomology ring H*(G) of G. Our method uses graph associahedra and toric varieties. Given a graph, there is a canonically associated convex polytope, called the graph associahedron, constructed from G. In turn, a convex polytope uniquely determines a toric variety. We synthesize these results, and describe the cohomology of the associated variety directly in terms of the graph G itself.

Thesis (Ph. D.)--Mathematics, Georgia Institute of Technology, 2008.<br>Committee Chair: Tetali, Prasad; Committee Member: Duke, Richard; Committee Member: Heitsch, Christine; Committee Member: Randall, Dana; Committee Member: Trotter, William T.

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.

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}^d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Q_m in Q_d. Specifically, we show that for m &ge; 2 fixed and d large there exists a subgraph G of Q_d of bounded average degree such that G does not contain a copy of Q_m but, for every G' such that G &subne; G' &sube; Q_d, the graph G' contains a copy of Q_m. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists &epsilon; &gt; 0 such that for all k and for n sufficiently large there is a collection of at most 2^{(1-&epsilon;)k} subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, P&aacute;lv&ouml;lgyi and Patk&oacute;s. We also prove that there exists a constant c &isin; (0,1) such that the smallest such collection is of cardinality 2^{(1+o(1))^ck} for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Q_m in Q_d. That is, we determine the minimum number of edges in a spanning subgraph G of Q_d such that the edges of E(Q_d)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Q_m. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A₀ of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A₀ percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r &ge; 2, every percolating set in Q_d has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollob&aacute;s and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset &Vscr;(q,n) consisting of all subspaces of &Fopf;_qⁿordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in &Vscr;(q,n) and a bound on the size of the largest antichain in a p-random subset of &Vscr;(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (&epsilon;_i)^&infin;_i=1 tending to zero such that, for all i &ge; 1, every weak &epsilon;_i-regular partition of W has at least exp(&epsilon;_i^-2/2^{5log&lowast;&epsilon;_i^-2}) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lov&aacute;sz and Szegedy. For positive integers p,q with p/q &VerticalSeparator;&ge; 2, a circular (p,q)-colouring of a graph G is a mapping V(G) &rarr; &Zopf;_p such that any two adjacent vertices are mapped to elements of &Zopf;_p at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 &le; p/q &LT; 4 and is PSPACE-complete for p/q &ge; 4.

The topic of this thesis is the hat problem. In this problem, a team of n players enters a room, and a blue or red hat is randomly placed on the head of each player. Every player can see the hats of all of the other players but not his own. Then each player must simultaneously guess the color of his own hat or pass. The team wins if at least one player guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of winning. This thesis is based on publications, which form the second chapter. In the first chapter we give an overview of the published results. In Section 1.1 we introduce to the hat problem and the hat problem on a graph, where vertices correspond to players, and a player can see the adjacent players. To the hat problem on a graph we devote the next few sections. First, we give some fundamental theorems about the problem. Then we solve the hat problem on trees, cycles, and unicyclic graphs. Next we consider the hat problem on graphs with a universal vertex. We also investigate the problem on graphs with a neighborhood-dominated vertex. In addition, we consider the hat problem on disconnected graphs. Next we investigate the problem on graphs such that the only known information are degrees of vertices. We also present Nordhaus-Gaddum type inequalities for the hat problem on a graph. In Section 1.6 we investigate the hat problem on directed graphs. The topic of Section 1.7 is the generalized hat problem with q &gt;= 2 colors. A modified hat problem is considered in Section 1.8. In this problem there are n &gt;= 3 players and two colors. The players do not have to guess their hat colors simultaneously and we modify the way of making a guess. We give an optimal strategy for this problem which guarantees the win. Applications of the hat problem and its connections to different areas of science are presented in Section 1.9. We also give there a comprehensive list of variations of the hat problem considered in the literature.