No description available.

Thesis (Ph. D.)--Rutgers University, 2009. / "Graduate Program in Mathematics." Includes bibliographical references (p. 57-58).

No description available.

Given two set systems $\mathscr{A}$ and $\mathscr{B}$ over an $n$-element set, we say that $(\mathscr{A,B})$ forms a recovering pair if the following conditions hold: \\ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr{B}$, $A \setminus B = A' \setminus B' \Rightarrow A=A'$ \\ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr {B}$, $B \setminus A = B' \setminus A' \Rightarrow B=B'$ \\ In 1989, G\'bor Simonyi conjectured that if $(\mathscr)$ forms a recovering pair, then $|\mathscr||\mathscr|\leq 2^n$. This conjecture is the focus of this thesis. This thesis contains a collection of proofs of special cases that together form a complete proof that the conjecture holds for all values of $n$ up to 8. Many of these special cases also verify the conjecture for certain recovering pairs when $n>8$. We also present a result describing the nature of the set of numbers over which the conjecture in fact holds. Lastly, we present a new problem in graph theory, and discuss a few cases of this problem.

Thesis (Ph.D) - Swinburne University of Technology, Faculty of Information & Communication Technologies, 2008. / [A thesis submitted in total fulfillment of the requirements of for the degree of Doctor of Philosophy, Faculty of Information and Communication Technologies, Swinburne University of Technology, 2008]. Typescript. Includes bibliographical references p. 193-201.

Diplomarbeit--Rheinische Friedrich-Wilhelms-Universität, 2003. / Includes bibliographical references (p. 102-103).

For integers $n \geq k \geq 2$, let $V$ be an $n$-element set, and let $\binom{V}{k}$ denote the family of all $k$-element subsets of $V$. For disjoint subsets $A, B \subseteq V$, we say that $\{A, B\}$ {\it covers} an element $K \in \binom{V}{k}$ if $K \subseteq A \dot\cup B$ and $K \cap A \neq \emptyset \neq K \cap B$. We say that a collection $\cC$ of such pairs {\it covers} $\binom{V}{k}$ if every $K \in \binom{V}{k}$ is covered by at least one $\{A, B\} \in \cC$. When $k=2$, covers $\cC$ of $\binom{V}{2}$ were introduced in~1961 by R\'enyi~\cite{Renyi}, where they were called {\it separating systems} of $V$ (since every pair $u \neq v \in V$ is separated by some $\{A, B\} \in \cC$, in the sense that $u \in A$ and $v \in B$, or vice-versa). Separating systems have since been studied by many authors. For a cover $\cC$ of $\binom{V}{k}$, define the {\it weight} $\omega(\cC)$ of $\cC$ by $\omega(\cC) = \sum_{\{A, B\} \in \cC} (|A|+|B|)$. We define $h(n, k)$ to denote the minimum weight $\omega(\cC)$ among all covers $\cC$ of $\binom{V}{k}$. In~1964, Hansel~\cite{H} determined the bounds $\lceil n \log_2 n \rceil \leq h(n, 2) \leq n\lceil \log_2 n\rceil$, which are sharp precisely when $n = 2^p$ is an integer power of two. In~2007, Bollob\'as and Scott~\cite{BS} extended Hansel's bound to the exact formula $h(n, 2) = np + 2R$, where $n = 2^p + R$ for $p = \lfloor \log_2 n\rfloor$. The primary result of this dissertation extends the results of Hansel and of Bollob\'as and Scott to the following exact formula for $h(n, k)$, for all integers $n \geq k \geq 2$. Let $n = (k-1)q + r$ be given by division with remainder, and let $q = 2^p + R$ satisfy $p = \lfloor \log_2 q \rfloor$. Then h(n, k) = np + 2R(k-1) + \left\lceil\frac{r}{k-1}\right\rceil (r + k - 1). A corresponding result of this dissertation proves that all optimal covers $\cC$ of $\binom{V}{k}$, i.e., those for which $\omega(\cC) = h(n, k)$, share a unique {\it degree-sequence}, as follows. For a vertex $v \in V$, define the {\it $\cC$-degree} $\deg_{\cC}(v)$ of $v$ to be the number of elements $\{A, B\} \in \cC$ for which $v \in A \dot\cup B$. We order these degrees in non-increasing order to form $\bd(\cC)$, and prove that when $\cC$ is optimal, $\bd(\cC)$ is necessarily binary with digits $p$ and $p+1$, where uniquely the larger digits occur precisely on the first $2R(k-1) + \lceil r/(k-1) \rceil (r + k - 1)$ many coordinates. That $\bd(\cC)$ satisfies the above for optimal $\cC$ clearly implies the claimed formula for $h(n,k)$, but in the course of this dissertation, we show these two results are, in fact, equivalent. In this dissertation, we also consider a $d$-partite version of covers $\cC$, written here as {\it $d$-covers} $\cD$. Here, the elements $\{A,B\} \in \cC$ are replaced by $d$-element families $\{A_1, \dots, A_d\} \in \cD$ of pairwise disjoint sets $A_i \subset V$, $1 \leq i \leq d$. We require that every element $K \in \binom{V}{k}$ is covered by some $\{A_1, \dots, A_d\} \in \cD$, in the sense that $K \subseteq A_1 \dot\cup \cdots \dot\cup A_d$ where $K \cap A_i \neq \emptyset$ holds for each $1 \leq i \leq d$. We analogously define $h_d(n,k)$ as the minimum weight $\omega(\cD) = \sum_{D \in \cD} \sum_{A \in D} |A|$ among all $d$-covers $\cD$ of $\binom{V}{k}$. In this dissertation, we prove that for all $2 \leq d \leq k \leq n$, the bound $h_d(n,k) \geq n \log_{d/(d-1)} (n/(k-1))$ always holds, and that this bound is asymptotically sharp whenever $d = d(k) = O (k/\log^2 k)$ and $k = k(n) = O(\sqrt{\log \log n})$.

In this dissertation we consider several extremal and probabilistic problems in bootstrap percolation on various families of graphs, including grids, hypercubes and trees. Bootstrap percolation is one of the simplest cellular automata. The most widely studied model is the so-called r-neighbour bootstrap percolation, in which we consider the spread of infection on a graph G according to the following deterministic rule: infected vertices of G remain infected forever and in successive rounds healthy vertices with at least r already infected neighbours become infected. Percolation is said to occur if eventually every vertex is infected. In Chapter 1 we consider a particular extremal problem in 2-neighbour bootstrap percolation on the n \times n square grid. We show that the maximum time an infection process started from an initially infected set of size n can take to infect the entire vertex set is equal to the integer nearest to (5n^2-2n)/8. In Chapter 2 we relax the condition on the size of the initially infected sets and show that the maximum time for sets of arbitrary size is 13n^2/18+O(n). In Chapter 3 we consider a similar problem, namely the maximum percolation time for 2-neighbour bootstrap percolation on the hypercube. We give an exact answer to this question showing that this time is \lfloor n^2/3 \rfloor. In Chapter 4 we consider the following probabilistic problem in bootstrap percolation: let T be an infinite tree with branching number \br(T) = b. Initially, infect every vertex of T independently with probability p > 0. Given r, define the critical probability, p_c(T,r), to be the value of p at which percolation becomes likely to occur. Answering a problem posed by Balogh, Peres and Pete, we show that if b \geq r then the value of b itself does not yield any non-trivial lower bound on p_c(T,r). In other words, for any \varepsilon > 0 there exists a tree T with branching number \br(T) = b and critical probability p_c(T,r) < \varepsilon. However, in Chapter 5 we prove that this is false if we limit ourselves to the well-studied family of Galton--Watson trees. We show that for every r \geq 2 there exists a constant c_r>0 such that if T is a Galton--Watson tree with branching number \br(T) = b \geq r then \[ p_c(T,r) > \frac{c_r}{b} e^{-\frac{b}{r-1}}. \] We also show that this bound is sharp up to a factor of O(b) by describing an explicit family of Galton--Watson trees with critical probability bounded from above by C_r e^{-\frac{b}{r-1}} for some constant C_r>0.

The main focus of this thesis is to evaluate .k_r(n,\delta)., the minimal number of $r$-cliques in graphs with $n$ vertices and minimum degree~$\delta$. A fundamental result in Graph Theory states that a triangle-free graph of order $n$ has at most $n 2/4$ edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if $k_3(n,\delta) =0$ then $\delta \le n/2$. For $n/2 \leq \delta \leq 4n/5$, I have evaluated $k_r(n,\delta)$ and determined the structures of the extremal graphs. For $\delta \ge 4n/5$, I give a conjecture on $k_r(n,\delta)$, as well as the structures of these extremal graphs. Moreover, I have proved various partial results that support this conjecture. Let $k_r �(n, \delta)$ be the analogous version of $k_r(n,\delta)$ for regular graphs. Notice that there exist $n$ and $\delta$ such that $k_r(n, \delta) =0$ but $k_r �(n, \delta) &gt;0$. For example, a theorem of Andr{\'a}sfai, Erd{\H}s and S{\'o}s states that any triangle-free graph of order $n$ with minimum degree greater than $2n/5$ must be bipartite. Hence $k_3(n, \lfloor n/2 \rfloor) =0$ but $k_3 �(n, \lfloor n/2 \rfloor) &gt;0$ for $n$ odd. I have evaluated the exact value $k_3 �(n, \delta)$ for $\delta$ between $2n/5+12 \sqrt{n}/5$ and $n/2$ and determined the structure of these extremal graphs. At the end of the thesis, I investigate a question in Ramsey Theory. The Ramsey number $R_k(G)$ of a graph $G$ is the minimum number $N$, such that any edge colouring of $K_N$ with $k$ colours contains a monochromatic copy of $G$. The constrained Ramsey number $f(G,T)$ of two graphs $G$ and $T$ is the minimum number $N$ such that any edge colouring of $K_N$ with any number of colours contains a monochromatic copy of $G$ or a rainbow copy of $T$. It turns out that these two quantities are closely related when $T$ is a matching. Namely, for almost all graphs $G$, $f(G,tK_2) =R_{t-1}(G)$ for $t \geq 2$.

Szemere´di’s Regularity Lemma [32, 33] is an important tool in combinatorics, with numerous appli- cations in combinatorial number theory, discrete geometry, extremal graph theory, and theoretical computer science. The Regularity Lemma hinges on the following concepts. Let G = (V, E) be a graph and let ∅ /= X, Y ⊂ V be a pair of disjoint vertex subsets. We define the density of the pair (X, Y ) by dG(X, Y ) = |E[X, Y ]|/(|X||Y |) where E[X, Y ] denotes the set of edges {x, y} ∈ E with x ∈ X and y ∈ Y . We say the pair (X, Y ) is ε-regular if all subsets XI ⊆ X and Y I ⊆ Y satisfying |XI| > ε|X| and |Y I| > ε|Y | also satisfy |dG(XI, Y I) − dG(X, Y )| < ε. The Regularity Lemma states that, for all ε > 0, all large n-vertex graphs G = (V, E) admit a partition V = V1 ∪ · · · ∪ Vt, where t = t(ε) depends on ε but not on n, so that all but εt2 pairs (Vi, Vj), 1 ≤ i < j ≤ t, are ε-regular. While Szemere´di’s original proof demonstrates the existence of such a partition, it gave no method for (efficiently) constructing such partitions. Alon, Duke, Lefmann, Ro¨dl, and Yuster [1, 2] showed that such partitions can be constructed in time O(M (n)), where M (n) is the time needed to multiply two n × n {0, 1}-matrices over the integers. Kohayakawa, Ro¨dl, and Thoma [17, 18] improved this time to O(n2). The Regularity Lemma can be extended to k-uniform hypergraphs, as can algorithmic for- mulations thereof. The most straightforward of these extends the concepts above to k-uniform hypergraphs H = (V, E) in a nearly verbatim way. Let ∅ /= X1, . . . , Xk ⊂ V be pairwise disjoint subsets, and let E[X1, . . . , Xk] denote the set of k-tuples {x1, . . . , xk} ∈ E satisfying x1 ∈ X1, . . . , xk ∈ Xk. We define the density of (X1, . . . , Xk) as dH(X1, . . . , Xk) = |E[X1, . . . , Xk]| / |X1| · · · |Xk|. We say that (X1, . . . , Xk) is ε-regular if all subsets XiI ⊆ Xi, 1 ≤ i ≤ k, satisfying |XiI| > ε|Xi| also satisfy |dH (X1I , . . . , XkI ) − dH (X1, . . . , Xk)| < ε. With these concepts, Szemeredi’s original proof can be applied to give that, for all integers k ≥ 2 and for all ε > 0, all n-vertex k-uniform hypergraphs H = (V, E) admit a partition V = V1 ∪· · ∪ Vt, where t = t(k, ε) is independent of n, so that all but εtk many k-tuples (Vi1 , . . . , Vik) are ε-regular, where 1 ≤ i1 < · · · < ik ≤ t. Czygrinow and Ro¨dl [4] gave an algorithm for such a regularity lemma, which in the context above, runs in time O(n2k−1 log5 n). In this dissertation, we consider regularity lemmas for 3-uniform hypergraphs. In this setting, our first main result improves the algorithm of Czygrinow and Ro¨dl to run in time O(n3), which is optimal in its order of magnitude. Our second main result shows that this algorithm gives a stronger notion of regularity than what is described above, where this stronger notion is described in the course of this dissertation. Finally, we discuss some ongoing applications of our constructive regularity lemmas to some classical algorithmic hypergraph problems.