CATS-Jan-17-2014
Title[edit]
Defining sets in combinatorics with emphasis in graph theory
Speaker[edit]
E. S.Mahmoodian, Professor of Mathematics, Sharif University of Technology
Abstract[edit]
In a given graph $G$, a set of vertices $S$ with an assignment of colors is called a {\em defining set (of a $k$--coloring)}, if there exists a unique extension of the colors of $S$ to a proper $k$-coloring of the vertices of $G$. A defining set with minimum cardinality is called a {\em minimum defining set.} The cardinality of minimum defining set is the {\em defining number} denoted by {$d(G, k)$}. A {\em critical set} is a minimal defining set. Defining sets are defined and discussed for many concepts and parameters in graph theory and combinatorics. For example in Latin squares a {\em{critical set}} is a partial Latin square that has a unique completion to a Latin square, and is minimal with respect to this property. Smallest possible size of a critical set in any Latin square of order $n$ is of interest and is denoted by $\scs{n}$. But it is clear that any $n \times n$ Latin square may be used as an $n$-coloring of the Cartesian product of ${K_n}$ by ${K_n}$ and vice versa. So \ d(${{K_n}\Box{K_n}},n$) = $\scs{n}$. The following conjecture which is made in 1995, is still open: For any $n$, \ $d({{K_n}\Box{K_n}},n) =\lfloor n^2/4 \rfloor$. In this talk we discuss these concepts in different areas and introduce some more open problems. Our emphasis will be in graph colorings and perfect matching. For some references and a survey, we refer to the author's webpage and papers referenced in there.
