%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%           FPSAC/SFCA '94, May 23-27, 1994   at DIMACS
%                     Problem Session
%   LaTeX file of problem submitted by Sergey Fomin (May 24, 1994)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[12pt]{article}
\textwidth6.0truein
\textheight8.0truein
\topmargin-.5truein
\oddsidemargin+0truein
\evensidemargin+0truein
\baselineskip0.20truein
\parskip0.20truein

\begin{document}
\begin{center}
{FPSAC/SFCA '94}\\
{PROBLEM SESSION}\\
{Submission received May 24, 1994}\\[.2in]
{\bf GENERALIZATIONS OF THE GREENE-KLEITMAN THEOREM}\\[.1in]
Sergey Fomin\\[.2in]
\end{center}
%text of problem goes after this line
Let $G=(V,E)$ be a finite non-oriented graph.
Let $R_k$\,, $k=0,1,2,\dots$ be the maximal number of vertices
in a union of $k$ cliques in $G$.
Dually, let $Q_k$ be the maximal number of vertices
in a union of $k$ independent subsets of $G$.
Denote $x_k=R_k-R_{k-1}$ and $y_k=Q_k-Q_{k-1}$.
The following result was first proved by C.~Greene and
D.~Kleitman~\cite{GK,Greene} (see also \cite{F1,Frank,HS,Saks}).

{\bf Theorem.}
Suppose that either $G$ or its complement is a comparability graph
of some partially ordered set.
Then $(x_1,x_2,\dots)$ and $(y_1,y_2,\dots)$ are conjugate partitions.

{\bf Problem.} Find other classes of graphs
for which this result is true.
Generalize the theorem to a {\it natural}
class of graphs that includes both comparability
and incomparability graphs.

The second question was proposed in \cite{F2}, Section 6,
and seems to be very hard.

We give below some examples borrowed from \cite{F2}.
A graph $G$ defined by
$$ V=\{a,b,c,d,e,f,g\}\ ,\quad E=\{ab,bc,cd,de,ef,fg,ag,ad,bf,cf,dg\} $$
is neither a comparability
nor an incomparability graph though the statement of the theorem holds.
On the other hand, the graph $G$ given by
$$ V=\{a,b,c,d,e,f\}\ ,\quad E=\{ab,bc,ac,ad,be,cf\} $$
is {\it perfect} but the $x_i$ do not even form a partition.

A general survey of the area was given in \cite{West}.
For generalizations to acyclic directed graphs,
see \cite{Felsner} and the references therein.

\begin{thebibliography}{x}
\bibitem{Felsner}
S.~Felsner, Orthogonal structures in directed graphs,
{\it J.\ Comb.\ Theory, Ser.\ B} {\bf 57} (1993), 309--321.

\bibitem{F1}
S.~V.~Fomin, Finite partially ordered sets and Young tableaux,
{\it Soviet Math.\ Dokl.}\ {\bf 19} (1978), 1510--1514.

\bibitem{F2}
S.~V.~Fomin, Duality theorem for posets: algorithms,
{\it Mathematical Methods of Design and Analysis of Algorithms}, Leningrad,
Nauka, 1990, 190--199 [in Russian].

\bibitem{Frank}
A.~Frank, On chain and antichain families of a partially ordered set,
{\it J.\ Comb.\ Theory, Ser.\ B} {\bf 29} (1980), 176--184.

\bibitem{GK}
C.~Greene, D.~Kleitman,
The structure of Sperner $k$-families,
{\it J.\ Comb.\ Theory, Ser.\ A} {\bf 20} (1976), 41--68.

\bibitem{Greene}
C.~Greene,
Some partitions assosiated with a partially ordered set,
{\it J.\ Comb.\ Theory, Ser.\ A} {\bf 20} (1976), 69--79.

\bibitem{HS}
A.~J.~Hoffman, D.~E.Schwarz, On partitions of a partially ordered set,
{\it J.\ Comb.\ Theory, Ser.\ B} {\bf 18} (1976), 593--598.

\bibitem{Saks}
M.~Saks, A short proof of the existence of $k$-saturated partitions
of partially ordered sets,
{\it Adv.\ in Math.}\ {\bf 33} (1979), 207--211.

\bibitem{West}
D.~B.~West, Parameters of partial orders and graphs:
Packing, covering and representation,
{\it in} ``Graphs and Orders'' (I.\ Rival, Ed.),
pp.\ 267--350, Reidel, Dordrecht, 1985.

\end{thebibliography}

\end{document}