Challenge Problems

\(\renewcommand{\glspostdescription}{} \def\cprime{\char"7E } \def\cdprime{\char"7F } \def\eoborotnoye{\char'013} \def\Eoborotnoye{\char'003} \newcommand{\beq}[1]{\begin{equation}\label{#1}} \newcommand{\eeq}{\end{equation}} \newcommand{\weakstar}{weak${}^*$ } \newcommand{\rng}{\operatorname{rng}} \newcommand{\ex}{\operatorname{ex}} \newcommand{\colex}{\prec_{\operatorname{colex}}} \newcommand{\lex}{\prec_{\operatorname{lex}}} \newcommand{\per}{\operatorname{per}} \newcommand{\permat}{\operatorname{pm}} \renewcommand{\hom}{\operatorname{hom}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\degree}{d} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Section 4.8 Challenge Problems

Prove that $t(P_4,G)\geq t(K_2,G)^3$ for any graph $G\text{.}$ Generalize the proof of this and Exercise 19 of Section 4.7 to yield $t(P_{k},G)\geq t(K_2,G)^{k-1}$ for any $k\geq1\text{.}$
Let $Q_d$ be the $d$-dimensional hypercube. Prove that $t(Q_d,G)\geq t(K_2,G)^{|E(Q_d)|}$ for every graph $G\text{.}$ (Hint: Adapting the idea in Exercise 20 of Section 4.7 should work).
Prove that there exists $c>1$ such that $t(K_3,G)\geq c\left(t(K_2,G)-\frac{1}{2}\right)$ for every graph $G\text{.}$ The maximum value of $c$ for which such a bound holds is $c=4/3\text{.}$ Observe that this bound is better than Theorem 4.1.1 when $t(K_2,G)$ is slightly larger than $1/2\text{.}$
Prove that every graph $G$ satisfies

\begin{equation*} t(C_5,G)+t(C_5,\overline{G})\geq t(K_2,G)^5 + t(K_2,\overline{G})^5-o(1)\text{.} \end{equation*}

Prev Top Next