Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 12 of 12 for “"Kneser graph"”.
-
Colouring Subspaces
… theory, but our main results concern colouring a graph that is intimately related to these vector space analogues. The vertices of the <em>q</em>-Kneser graph are the <em>k</em>-dimensional subspaces of a vector space of dimension <em>v</em> over F<sub><em>q</em></sub>, and two …
-
Coloring of Metric Spaces and L(2,1)-Labeling of Graphs
… = q 2 + q = Delta2 - Delta for the incidence graph G of the projective plane PG (2, q). To prove this result, we convert the problem to a problem of packing of bipartite graphs into a complete bipartite graph. We also bound lambda(G) when G is the Kneser graph K(2k + 1, k).
-
Problems in extremal combinatorics
… \ge 2$, we study the chromatic number of the subgraphs of the Kneser graph $\textrm{KG}(n,k)$ induced by the family the $s$-stable sets in $\binom{[n]}{k}$. We prove a conjecture of Meunier that $\chi(\textrm{KG}(n,k)_{3\text{-stable}})=n-3(k-1)$ for large enough $n$. To this end, we also prove a …
-
Higher Order Random Walks, Local Spectral Expansion, and Applications
The study of spectral expansion of graphs and expander graphs has been an extremely fruitful line of research in Mathematics and Computer Science, with applications ranging from random walks and fast sampling to optimization. In this dissertation, we study high dimensional local spectral expansion, …
-
Dominating sets in Kneser graphs
This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures. We begin with background on the …
-
TOPOLOGICAL AND COMBINATORIAL PROPERTIES OF NEIGHBORHOOD AND CHESSBOARD COMPLEXES
… that the neighborhood complex of the stable Kneser graph SGn,k is homotopy equivalent to a k-sphere. Further, for n = 2 they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron. They went on to ask whether or not, for all n and k, the …
-
Extremal problems in graph theory
We consider generalized graph coloring and other extremal problems in graph theory. We also construct twisted hypercubes of small radius and find the domination number of the Kneser graph $K(n,k)$ when $n\ge{3\over4}k\sp2\pm k,$ depending on whether k is even or odd. The path chromatic number …
-
Topics In Probabilistic Combinatorics
… basic definitions, lemmas, and theorems from graph theory, asymptotic analysis, and probability which will be used throughout the paper. Chapter 2 introduces the independent domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the …
-
Pebbling in Erdős-Rényi random graphs
Graph pebbling is a game in which a collection of pebbles is placed on the vertices of a connected graph. A pebbling move consists of removing two pebbles from one vertex and placing a pebble on any adjacent vertex. Of interest is the pebbling number of a graph G: the least k such that for any …
-
Some isoperimetric-type problems on graphs
… isoperimetric problems are extremal problems on graphs that ask how we can choose a fixed number of vertices that are as closely packed as possible to have a small 'boundary'. This thesis discusses three problems with this common motivation behind, while varying how we measure the boundary and …
-
On problems in Extremal Combinatorics
… families. Another central area is extremal graph theory, in which the structures being studied are graphs, and the configurations to be avoided are given subgraphs. A basic result in this area is the Tur\'an's theorem, which gives the maximum number of edges in graphs with no copy of a given …