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 3.7 Challenge Problems

Given graphs $F$ and $H\text{,}$ let $\ex(F,H)$ be the maximum number of edges in a subgraph of $F$ which does not contain a copy of $H\text{.}$ Let $Q_d$ be the $d$-dimensional hypercube; i.e. the graph with vertex set $\{0,1\}^d$ in which two vertices are adjacent if they differ in a unique coordinate. Prove that

\begin{equation*} \ex(Q_d,C_6)\geq \frac{1}{3}|E(Q_d)|\text{.} \end{equation*}
The packing density of a permutation $\sigma$ is defined in Exercise 9 in Section 3.6. Find the packing density of any permutation $\sigma$ of length $k\geq4$ such that $\sigma$ is not the increasing permutation $(1,2,\dots,k)$ or the decreasing permutation $(k,k-1,\dots,1)\text{.}$ (You get to choose $k$ and $\sigma$).

Prev Top Next