Details

Autor(en) / Beteiligte

• Wysocka, Beata Bernadetta

Titel

Some results in anti-Ramsey theory

Ort / Verlag

ProQuest Dissertations & Theses

Erscheinungsjahr

1995

Quelle

ProQuest Dissertations & Theses A&I

Beschreibungen/Notizen

• This dissertation addresses some problems in Ramsey theory. In Chapter 1 we consider anti-Ramsey type problems for k-uniform hypergraphs. A subset Y of an n-element set X is totally multicolored, if the restriction of a coloring of k-element subsets of X to ($Y\rbrack \sp{k}$ is a one-to-one coloring. We study the maximum size of totally multicolored subsets for colorings which satisfy the following restriction: any two distinct k-element subsets with at least h elements in the intersection are colored differently. It is shown that the size of the largest totally multicolored subset can be bounded from below by $c\sb{k} \cdot (ln\ n)\sp{1\over2k-1} \cdot n\sp{k-h\over2k-1},$ where $c\sb{k}$ is a positive constant and this lower bound is sharp (up to a multiplicative constant). In Chapter 2 and Chapter 3 various related problems concerning edge-colorings of complete graphs are considered. In Chapter 2 we show that there exists a proper edge-coloring of complete graph with no totally multicolored complete subgraph of size 2.21$n\sp{1\over3}$(ln $n{1\over3},$ provided $n \ge n\sb0.$ This sharpens earlier result of L. Babai and is up to a multiplicative constant the best possible. As a tool for proving the existence of such a coloring we derive an upper bound for permanents of rectangular (0.1)-matrices which might be of interest on its own. In Chapter 3 we consider a different anti-Ramsey type problem. We investigate the size of the largest totally multicolored subset under the condition that each color appears only a restricted number of times. Let $f\sbsp{u}{*}(n)$ denote the maximum size of a totally multicolored complete subgraph of $K\sb{n},$ where the edges of $K\sb{n}$ are colored under restriction that each color class is bounded in size by u. We prove that$$\left(1/\sqrt{2} - o(1)\right)\ \sqrt{n/u} \le f\sbsp{u}{*}(n) \le \sqrt{3}\sqrt{n\ l{\rm n}\ n)/u},$$provided $n \ge n\sb0.$ Next, we consider edge-coloring of $K\sb{n}$ such that each color class is a matching of size at most u. Under this restriction, let $f\sb{u}(n,2.1)$ denote the maximum size of a totally multicolored subgraph of $K\sb{n}.$ We show that there exist positive constants $c\sb1, c\sb2, c\sb3$ such that the lower bound for $f\sb{u}(n,2,1)$ is$$\max\left\{c\sb1\left({n\sp2\over u}\right)\sp{1\over3},\ c\sb2\left({n\sp2{\rm ln}({u\over\sqrt{n}})\over u}\right)\sp{1\over3}\right\},$$ and the upper bound for $f\sb{u}(n,2,1)$ is $c\sb3\ ({n\sp2{\rm n}n\over u})\sp{1\over3}.$ Finally, in Chapter 4 we consider the closely related problem of determining the maximum size of Sidon sets in arbitrary groups.