\documentclass{beamer}[8pt]
\usepackage{beamerthemesplit}
\usetheme{Warsaw}
%\usepackage{verbatim}
\usepackage{pdfpages}
\usepackage{color}
\usepackage{graphicx}
\usepackage{fontspec}
\setmainfont[Script=Devanagari]{Sanskrit 2003}

\newfontfamily \dv[Script=Devanagari]{Sanskrit 2003}

\title{\textcolor{yellow}{\'{S}ivas{\=u}tra}}
\author{Amba Kulkarni}
\institute{ Fellow IIAS, Shimla}
\date{1st April 2017}

\begin{document}
\setbeamertemplate{footline}[frame number]
%===================================slide 1=========================%
\begin{frame}

\titlepage

\end{frame}
%============================================================%
\begin{frame}
Given a class of sets, is it always possible to \\
arrive at a linear order with markers that will define all the sets?\\
\vspace{0.2cm}
Petersen provided an algorithm.\\

\vspace{0.2cm}
In what follows we discuss this algorithm.\\
But before that some Mathematical preliminaries.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Partial Order}
A stict partial order is a binary relation $R$ ($<$) over a set P where R is Relflexive and transitive.\\

\begin{itemize}
\item A relation $R$ is reflexive, if $aRa$.
\item A relation $R$ is transitive, if $aRb$, $bRc$ then $aRc$.
\end{itemize}

\end{frame}
%============================================================%
\begin{frame}
\frametitle{Partially Ordered Set (POSET)}
A set S is a partially ordered set (POSET), if $R$ is a partial order over the elements of S.\\

\vspace{0.2cm}
The power set of S is a POSET over the relation of set inclusion/ subset relation.\\

\vspace{0.2cm}
In a POSET, all sets need not be comparable. Or in other words, there will be pair of sets which have partial overlap between them.
\end{frame}
%============================================================%
\begin{frame}
\begin{figure}
\includegraphics[scale=0.5]{haze.png}
\end{figure}
The Hasse diagram of the set of all subsets of a three-element set \{x, y, z\}, ordered by inclusion. Sets on the same horizontal level are incomparable with each other. Some other pairs, such as \{x\} and \{y,z\}, are also incomparable.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{S-alphabet}
A well-formed \'{S}ivas{\=u}tra-alphabet or S-alphabet is a triple $(A,\Sigma,<)$ consisting of a finaite alphabet A, a finite set of markers $\Sigma$ such that $ A \cap \Sigma = \phi $, and a strict partial order $<$ on $A \cup \Sigma$.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{S-encodable/praty{\=a}h{\=a}ra}
A subset $T$ of the alphabet $A$ is S-encodable in an $S-alphabet$ $(A,\Sigma,\le)$ iff there exists $a \in A$ and $M_1 \in \Sigma$ such that $T = \{b \in A / a \leq b < M_1\}$. \\
$aM_1$ is called a praty{\=a}h{\=a}ra or S-encoding of $T$ in $(A,\Sigma,<)$.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{S-Order and S-sortable}
Given a set of classes, order the elements of the classes (without
duplications) in a linear order (in a list) such that each single class
forms a continuous interval with respect to that order.\\
\begin{itemize}
\item The target orders are called S-orders
\item A set of classes is S-sortable if it has an S-order
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{S-Order and S-sortable}
Given a set of classes, find an S-order of the elements of the classes.
Interrupt this list by markers (anubandhas) such that each single class
can be denoted by a sound-marker-pair (praty{\=a}h{\=a}ra).\\
\vspace{0.5cm}
Every S-order becomes a \'{s}ivas{\=u}tra-alphabet (S-alphabet)
by adding a marker (anubandha) behind each element.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Examples}
\begin{itemize}
\item Given the set of classes \{\{a, b\}, \{a, b, c\}, \{a, b, c, d\}\}, the order
\textbf{a b c d} is one of its S-orders and a $\{M_1 b M_2 c M_3 d M_4\}$ is one of its
S-alphabets.
\item The set of classes \{\{a,b\},\{b,c\},\{c,a\}\} is not S-sortable.
\item The set of classes \{\{d,e\},\{a,b\},\{b,c,d\},\{b,c,d,f\}\} is not S-sortable.
\end{itemize}
\end{frame}
%============================================================%
%\begin{frame}
%\frametitle{Lattice (order)}
%A lattice consists of a partially ordered set in which every two elements have a unique supremum (also called a least upper bound or join) and a unique infimum (also called a greatest lower bound or meet).
%\end{frame}
%============================================================%
\begin{frame}
\frametitle{Algorithm to get S-order}
Algorithm to decide whether the given set of sets is S-encodable or not.
\begin{itemize}
\item Take the Union of all the sets. Let it be denoted by $U$.\\
   Let the given sets be denoted by A[i]

\item Take all possible intersections of the given sets.

\item Now we have the given sets, universal set, and the intersections of the sets.
\begin{itemize}
  \item Name these sets in the following way.
   \item Name the smallest set containing a as 'a'.
   \item If two sets have same name, say b and c, name it as 'bc'.

   \item At the most only n sets will have names, if 'n' is the number of distinct elements in U. Remaining sets are names as 1,2,3 etc.
\end{itemize}
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Algorithm to get S-order ...}
\begin{itemize}
\item Now draw a graph as follows.
\begin{itemize}
   \item Draw a circle corresponding to each of the sets listed in step 3. Place the circles as described below.
   \item Draw a circle corresponding to null set at the top, and a circle corresponding to the Universal set at the bottom. 
   \item Every set is connected to it's immediate subset by an upward arrow. Place the circles in such a way that there are no crossings of the arrows.
\end{itemize}

\item If you can avoid the crossings altogether, then go to next step.\\
   In case you can not avoid crossings, duplicate the elements one at a time in order to avoid the crossings.
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Algorithm to get S-order ...}
\begin{itemize}
\item Remove all the arrows to the null set. Then select those arrows, that lead to a boundary of the graph towards its infinte side. \\
If it contains all the nodes, then Shivasutra style representation exists for the give set of sets. The procedure to get the shivasutra style representation is described in step 7.\\
However, if there are some nodes which are in the interior side of the boundary facing infinite side, then one can not have a shivasutra style representation corresponding to the given set of sets.
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Algorithm to get S-order ...}
\begin{itemize}
\item Traverse the graph as explained below.
\begin{itemize}
\item Start from the universal set. You can traverse the graph either in clockwise or anticlockwise direction. 
\item Go on writing the names of the nodes (which are member of universal sets; do not write the names 1,2,3 etc), as you are traversing them. 
\item Insert a marker, when you traverse in an oppposite direction of an arrow.
Then remove multiple occurances of the same node, keeping any one of its occurances. 
\item Replace consecutive markers by a single marker.
\end{itemize}
This should give the shivasutra style representation (linear representation) of the members of the sets, such that one can get all the given sets, just by refering to one of the members of the set followed by a marker.

\item Multiple traverses of the graph are possible.
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Examples}
Decide if the following classes of sets are S-sortable, and if yes, give the S-order (linear order).
\begin{itemize}
\item \{\{b,c\},\{d,e,f\},\{a,d,f\},\{b,e,f\}\}
\item \{\{a,b\},\{a,b,c\},\{a,b,c,d\}\}
\item \{\{a,b\},\{b,c\},\{a,c\}\}
\item \{\{a,b,\},\{b,c,d\},\{b,c,d,f\},\{d,e\}\}
\item \{\{d,e\},\{a,b\},\{f,i\},\{g,h\},\{b,c,d,f,g,h,i\},\{c,d,e,f,g,h,i\}\}
\end{itemize}
\end{frame}
%============================================================%
\end{document}