File | Description | Format |
---|---|---|
Kantor_Ida.pdf (588KB) | (no description provided) |
Title: | Graphs, codes, and colorings |
Author(s): | Kantor, Ida |
Director of Research: | Furedi, Zoltan |
Doctoral Committee Chair(s): | West, Douglas B. |
Doctoral Committee Member(s): | Furedi, Zoltan; Kostochka, Alexandr V.; Reznick, Bruce A. |
Department / Program: | Mathematics |
Discipline: | Mathematics |
Degree Granting Institution: | University of Illinois at Urbana-Champaign |
Degree: | Ph.D. |
Genre: | Dissertation |
Subject(s): |
sum choice number
list coloring product dimension graph representation codes |
Abstract: | \noindent{This thesis focuses on topics in extremal combinatorics.} Given an integer-valued function $f$ defined on the vertices of a graph $G$, we say $G$ is {\em $f$-choosable} if for every collection of lists with list sizes specified by $f$ there is a proper coloring using the colors from the lists. The {\em sum choice number}, $\chi_{sc}(G)$, is the minimum of $\sum f(v)$ such that $G$ is $f$-choosable. We show that if $q\geq 4 a^2\log a$, then there exist constants $c_1$ and $c_2$ such that \[ 2q+c_1a\sqrt{q\log {a}}\leq \chi_{\rm sc}(K_{a,q})\leq 2q+c_2a\sqrt{q\log {a}}.\] As a consequence, $\chi_{sc}(G)/|V(G)|$ can be bounded while the minimum degree $\delta_{\rm min}(G)\to \infty$. This is not true for the list chromatic number, $\chi_\ell(G)$. We further prove that, for fixed $a$, the limit $\lim_{q\to \infty} (\chi_{\rm sc}(K_{a,q})-2q)/\sqrt{q}$ exists, and we give tight bounds for sum choice numbers of the graphs $G_{a,q}$, which are obtained from $K_{a,q}$ by adding all possible edges in the part of size $a$. A pair of ordered $k$-tuples $(x_1,...,x_k)$, $(y_1,...,y_k)$ is {\em reverse-free} if, for all $i<j$, $(x_i,x_j)$ does not equal $(y_j,y_i)$. Let $F(n,k)$ be the maximum size of a pairwise reverse-free set of $k$-tuples with $k$ distinct entries taken from $[n]$. Allowing repetitions within the $k$-tuples, we analogously define $\overline{F}(n,k)$. We determine the asymptotics of $F(n,3)$ and $\overline{F}(n,3)$ as $n$ approaches infinity, and we obtain exact formulas if $n$ is a power of $3$. We present some bounds for $F(n,k)$ for general $k$ and for other related quantities. We also present upper and lower bounds for the important special case $F(n,n)$ (i.e., reverse-free permutations). We also determine the order of magnitude of $\overline{F}(n,k)$ for $n$ fixed and $k\to \infty$. Finally, the {\em product dimension} $\dimm(G)$ of a graph $G$ is the minimum $k$ such that $G$ is an induced subgraph of the tensor product of $k$ complete graphs. We focus on bounding this parameter on the family of trees. We improve the known upper and lower bounds, and we determine the exact values of product dimension for infinitely many trees. We extend some of the results to {\em odd dimension} $\odd(G)$, defined as the minimum $k$ such that we can assign subsets of $[k]$ to the vertices of $G$ in such a way that two vertices are adjacent if and only if the corresponding sets have odd-sized intersection. |
Issue Date: | 2011-01-14 |
URI: | http://hdl.handle.net/2142/18247 |
Rights Information: | Copyright 2010 Ida Kantor. SIAM holds the copyright to part of the work included in Chapter 2 of the thesis, since it was published in a SIAM journal. |
Date Available in IDEALS: | 2011-01-14 |
Date Deposited: | December 2 |