List of Theorems

Author

Carlos Buitrago

1 Theorems Discussed in Class

Proposition 0.1 — Lower Bound for Ramsey Numbers

If \(\binom{n}{k}\cdot 2^{1-\binom{k}{2}}<1\), then

\[ R(k,k)>n. \]

Thus,

\[ R(k,k)>\left\lfloor 2^{k/2}\right\rfloor \]

for all \(k\geq 3\).

Theorem 0.2 — Property S_k

We say that a tournament \(T\) has property \(S_k\) if, for every set of \(k\) players, there exists a player who beats all of them.

\[ \binom{n}{k}\left(1-2^{-k}\right)^{n-k}<1, \]

then there exists a tournament on \(n\) vertices that has property \(S_k\).

Definition 0.3 — Dominating Set

A dominating set of an undirected graph \(G=(V,E)\) is a set \(U\subseteq V\) such that every vertex \(v\in V\setminus U\) has at least one neighbor in \(U\).

Theorem 0.4 — Upper Bound for the Domination Number

Let \(G=(V,E)\) be a graph on \(n\) vertices with minimum degree \(\delta>1\).

Then \(G\) has a dominating set of at most

\[ n\cdot\frac{1+\ln(\delta+1)}{\delta+1} \]

vertices.

1.1 Hypergraph Two-Colorability

Let \(H=(V,E)\) be an \(n\)-uniform hypergraph, meaning that each of its edges contains precisely \(n\) vertices.

We say that \(H\) has property B, or that it is two-colorable, if there exists a two-coloring of \(V\) such that no edge is monochromatic.

Let \(m(n)\) denote the minimum possible number of edges of an \(n\)-uniform hypergraph that does not have property B.

Proposition 0.5 — Erdős (1963a)

Every \(n\)-uniform hypergraph with fewer than

\[ 2^{n-1} \]

edges has property B.

Therefore,

\[ m(n)\geq 2^{n-1}. \]

Theorem 0.6 — Upper Bound for m(n)

\[ m(n)<(1+o(1))\frac{e\ln 2}{4}n^2 2^n. \]

1.2 Intersecting Families

Definition 0.7 — Intersecting Family

A family \(\mathcal{F}\) of sets is called intersecting if

\[ A,B\in\mathcal{F} \quad\Longrightarrow\quad A\cap B\neq\varnothing. \]

Suppose \(n\geq 2k\), and let \(\mathcal{F}\) be an intersecting family of \(k\)-element subsets of an \(n\)-set, for definiteness \(\{0,\ldots,n-1\}\).

Theorem 0.8 — Erdős–Ko–Rado

Let \(n\geq 2k\), and let \(\mathcal{F}\) be an intersecting family of \(k\)-element subsets of an \(n\)-element set.

Then

\[ |\mathcal{F}| \leq \binom{n-1}{k-1}. \]

1.3 Graph Theory and the Probabilistic Method

Theorem 0.9 — Erdős (1959)

For all integers \(k,\ell\), there exists a graph \(G\) such that

\[ \operatorname{girth}(G)>\ell \qquad\text{and}\qquad \chi(G)>k. \]

Here:

\(\operatorname{girth}(G)\) denotes the length of the shortest cycle in \(G\).
\(\chi(G)\) denotes the chromatic number of \(G\).

Theorem 0.10 — Hamiltonian Paths in Tournaments

There exists a tournament \(T\) with \(n\) players and at least

\[ n!\,2^{-(n-1)} \]

Hamiltonian paths.

Theorem 0.11 — Bipartite Subgraphs

Let \(G=(V,E)\) be a graph with \(n\) vertices and \(e\) edges.

Then \(G\) contains a bipartite subgraph with at least

\[ \frac{e}{2} \]

edges.

Theorem 0.12 — Improved Bounds for Bipartite Subgraphs

Part (a). If \(G\) has \(2n\) vertices and \(e\) edges, then it contains a bipartite subgraph with at least

\[ \frac{en}{2n-1} \]

edges.

Part (b). If \(G\) has \(2n+1\) vertices and \(e\) edges, then it contains a bipartite subgraph with at least

\[ \frac{e(n+1)}{2n+1} \]

edges.

Theorem 0.13 — Lower Bound for the Independence Number

Let \(G=(V,E)\) be a graph with \(n\) vertices and \(\frac{nd}{2}\) edges, where \(d\geq 1\).

Then

\[ \alpha(G)\geq\frac{n}{2d}, \]

where \(\alpha(G)\) denotes the independence number of \(G\).

2 Theorems Not Included in The Probabilistic Method

Theorem — Random Graphs: Independence and Chromatic Numbers

Let \(G\sim G(n,\frac12)\).

Then, for every \(\varepsilon>0\), with high probability,

\[ \frac{\chi_{\mathrm{gr}}(G)}{\chi(G)} \leq 2+\varepsilon, \]

and

\[ \frac{\alpha(G)}{\alpha_{\mathrm{gr}}(G)} \leq 2+\varepsilon. \]

Here:

\(\chi(G)\) denotes the chromatic number.
\(\chi_{\mathrm{gr}}(G)\) denotes the number of colors used by the greedy coloring algorithm.
\(\alpha(G)\) denotes the independence number.
\(\alpha_{\mathrm{gr}}(G)\) denotes the size of an independent set produced by a greedy algorithm.

Remark. Within this course, only the inequality concerning the independence number will be proved. The proof for the chromatic number proceeds analogously.