Challenge Problems

Skip to main content

\( \providecommand{\glspostdescription}{} \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 7.7 Challenge Problems

A Latin square of order \(n\) is an \(n\times n\) matrix in which each of the symbols in \(\{1,\dots,n\}\) appears exactly once in every row and column (sort of like Sudoku, but with one fewer restriction). Let \(L(n)\) be the number of Latin squares of order \(n\text{.}\) Prove that

\begin{equation*} L(n)^{1/n^2}=(1+o(1))\frac{n}{e^2}\text{.} \end{equation*}

Hint: Look up van der Waerden’s Conjecture (which was proved in [80, 110]) for lower bounding the permanent of a “doubly stochastic matrix” and apply it.

🔗

🔗
Recall that \(P_k\) is the path with \(k\) vertices. Prove that, for every graph \(G\text{,}\)

\begin{equation*} t(P_6,G)^3\geq t(P_4,G)^5\text{.} \end{equation*}

Generalize this to prove that, for all \(k\geq2\text{,}\)

\begin{equation*} t(P_{k+2},G)^{|E(P_k)|}\geq t(P_{k},G)^{|E(P_{k+2})|}\text{.} \end{equation*}

Hint: Construct a distribution on homomorphisms from \(P_{k+2}\) to \(G\) and play around with its entropy.

🔗

🔗
A “generalized theta graph” is obtained by taking two “terminal” vertices \(s\) and \(t\) and adding paths between them. It is said to be “odd” if all the paths have an even number of edges. Prove that if \(H\) is an odd generalized theta graph, then, for any graph \(G\text{,}\)

\begin{equation*} t(H,G)\geq t(K_2,G)^{|E(H)|}. \end{equation*}

🔗

🔗