Pairs of Points.tex

\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphics}
\usepackage{tikz}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{color}
\usepackage{mathtools}
\usepackage{stmaryrd}

\usepackage{pgf, latexsym, float, soul, array, booktabs, dsfont, gensymb}

\usepackage{fancyhdr}


%%% Formating the Page
% \usepackage[margin=1in]{geometry}
\usepackage[top=1.5in,bottom=1.5in,left=1.5in,right=1.5in, marginparwidth=.5 in]{geometry}

% \pagestyle{plain}

%%% Uncomment next line to turn of page numbers.
%\pagenumbering{gobble}

%%% Uncomment next line to begin paragraphs with an empty line rather than an indent
%\usepackage[parfill]{parskip}

%%% Line spacing -- change to 2 for double space, etc.
\renewcommand{\baselinestretch}{1.1}

%%% Useful commands--use the syntax \newcommand{\what you want to type}{real command}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zz}{\mathcal{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\NN}{\mathcal{N}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\ELL}{\mathcal{ELL}}
\renewcommand{\O}{\mathcal{O}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\dabba}{\partial}
\newcommand{\e}{\epsilon}
\newcommand{\eu}{\text{e}}
\newcommand{\bs}{\blacksquare}
\newcommand{\di}{\diamond}
\newcommand{\lb}{\left\lbrace}
\newcommand{\rb}{\right\rbrace}
\newcommand{\on}[1]{\operatorname{#1}}
\newcommand{\lcm}{\on{lcm}}
\newcommand{\multichoose}[2]{\left[#1\atop #2\right]}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\Inn}{\operatorname{Inn}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\id}{\operatorname{id}}

\newcommand{\lra}[1]{\overleftrightarrow{#1}}
\newcommand{\la}[1]{\overleftarrow{#1}}
\newcommand{\ra}[1]{\overrightarrow{#1}}
\newcommand{\ma}[1]{\mu(\angle #1)}



%%% Theorem styles and definitions. Since this is a homework template, numbering is
%%% turned off for most things.
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem*{problem}{Problem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{proposition}{Proposition}
\newtheorem*{fact}{Fact}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem*{question}{Question}

% You can customize your QED symbol. Make it your own!
\renewcommand{\qedsymbol}{\ensuremath{\blacksquare}}
%%%


\newcommand{\head}[2][]{\newpage\section*{#2 \ \ #1}}




\newcommand{\mytitle}{Pairs of Points}
\newcommand{\myauthor}{Peter E. Francis}
\newcommand{\mydate}{September 19, 2021}


\title{\mytitle}
\author{\myauthor}
\date{\mydate}

\pagestyle{fancy}
\fancyhf{}
\rhead{\myauthor}
\chead{\mytitle}
\lhead{\mydate}
\cfoot{\thepage}


\begin{document}
\thispagestyle{empty}
\noindent\hrule
\begin{center}
  \vspace{0.5em}
  {\huge Pairs of Points}\\
  Peter E. Francis
  \vspace{0.5em}
\end{center}
\noindent\hrule

\vspace{2em}

\begin{definition}
  Two paths $f_1:I\to\R^2$ and $f_2:I\to\R^2$ are said to \textit{properly intersect} if there exist $t_1,t_2\in(0,1)$ for which $f_1(t_1)=f_2(t_2)$.
\end{definition}

That is, $f_1$ and $f_2$ properly intersect if they intersect at a point other than their endpoints. The paths $f_1$ and $f_2$ are properly non-intersecting if they share, at most, some of their endpoints.


\begin{question}
  Does there exist a largest $N\in\N$ for which given any set $P=\{(a_1,b_1), \dots,(a_N,b_N)\}\subset\R^2\times\R^2$, there exist pairwise properly non-intersecting paths $f_j:I\to\R^2$, such that $f_j(0)=a_j$ and $f_j(1)=b_j$? If so, what is it?
\end{question}


\begin{claim}
  A largest such $N$ exists, and $N=8$.
\end{claim}
\begin{proof}
  Consider $P=\{(0,0),(0,1),(0,2)\}\times\{(1,0),(1,1),(1,2)\}$, so $|P|=9$. The resulting paths between pairs of points are the edges in the $K_{3,3}$ graph, which is not planar; thus, $N<9$.

  Suppose we have a set $P$ of 8 pairs of points. We can assume that $P$ contains no symmetric pairs, since any path from $a$ to $b$ that is properly non-intersecting any other is contained in an open tube, in which another path can be drawn. We can also assume that $P$ contains no pair of the form $(a,a)$ since the constant path at $a$ and any other path are properly non-intersecting.

Then the paths between the pairs of points in $P$ form a graph with at most 8 edges, and any graph with at most 8 edges is planar. This follows from Kuratowski's Theorem, since no graph with 8 edges can have a subdivision of $K_5$ or $K_{3,3}$ as a subgraph (these graphs have 9 and 10 edges, respectively).
\end{proof}











\end{document}