# Browse Dissertations and Theses - Mathematics by Contributor "Kostochka, Alexandr"

• (2017-07-10)
The \emph{separation dimension} of a graph $G$, written $\pi(G)$, is the minimum number of linear orderings of $V(G)$ such that every two nonincident edges are separated'' in some ordering, meaning that both endpoints ...

application/pdf

PDF (648kB)
• (2004)
Then, we consider packing problems for d-degenerate graphs. Two graphs G1 and G 2 pack if G1 is a subgraph of the complement G¯2 of G 2. We disprove one of the conjecture of Bollobas and Eldridge and prove an extension of ...

application/pdf

PDF (6MB)
• (2018-05-02)
In this dissertation we study problems related to colorings of combinatorial structures both in the “classical” finite context and in the framework of descriptive set theory, with applications to topological dynamics and ...

application/pdf

PDF (1MB)
• (2016-07-14)
In this dissertation, we will focus on a few problems in extremal graph theory. The first chapter consists of some basic terms and tools. In Chapter 2, we study a conjecture of Mader on embedding subdivisions of cliques. ...

application/pdf

PDF (702kB)
• (2015-12-04)
In this thesis, we study supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a ...

application/pdf

PDF (649kB)
• (2008)
This thesis considers three families of problems in graph theory about partitions of the edge sets of graphs (also known as graph decompositions). The first family we address consists of induced Ramsey number problems. ...

application/pdf

PDF (1MB)
• (2006)
We study the threshold on theta(G) to ensure that G is H -packable, where H = {K1, C3, K4 - e, C5 + e}, that is, G packs with each graph with |V(G)| vertices whose components lie in H .

application/pdf

PDF (3MB)
• (2008)
The Friendship Theorem states that if G is a graph in which every two vertices have exactly one common neighbor, then G has a dominating vertex. Sos defined an analogous friendship property for 3-uniform hypergraphs, and ...

application/pdf

PDF (2MB)
• (2016-05-11)
In this thesis we study combinatorial games on graphs and some graph parameters whose consideration was inspired by an interest in the symmetry of hypercubes. A capacity function f on a graph G assigns a nonnegative integer ...

application/pdf

PDF (792kB)
• (2016-12-01)
A graph is {\it reconstructible} if it is determined by its {\it deck} of unlabeled subgraphs obtained by deleting one vertex; a {\it card} is one of these subgraphs. The {\it Reconstruction Conjecture} asserts that all ...

application/pdf

PDF (712kB)
• (2017-04-05)
A classical problem in combinatorics is, given graphs G and H, to determine if H is a subgraph of G. It is usually computationally complex to determine if H is a subgraph of G. Therefore, we often prove conditions that ...

application/pdf

PDF (942kB)
• (2017-03-27)
This thesis focuses on using techniques from probability to solve problems from extremal and structural combinatorics. The main problem in Chapter 2 is determining the typical structure of $t$-intersecting families in ...

application/pdf

PDF (741kB)