\documentclass[12pt]{article} \usepackage{e-jc} \specs{P23}{19(2)}{2012} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} %\sloppy \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \title{\bf Some results on chromaticity of\\ quasi-linear paths and cycles} \author{ Ioan Tomescu\\ \small Faculty of Mathematics and Computer Science\\[-0.8ex] \small University of Bucharest\\[-0.8ex] \small Bucharest, Romania\\ \small and\\ \small Abdus Salam School of Mathematical Sciences\\[-0.8ex] \small GC University, Lahore, Pakistan\\ \small\tt ioan@fmi.unibuc.ro } \date{\dateline{Feb 7, 2012}{May 21, 2012}{May 31, 2012}\\ \small Mathematics Subject Classifications: 05C15, 05C65} \begin{document} \maketitle \begin{abstract} Let $r\geq 1$ be an integer. An $h$-hypergraph $H$ is said to be $r$-quasi-linear (linear for $r=1$) if any two edges of $H$ intersect in 0 or $r$ vertices. In this paper it is shown that $r$-quasi-linear paths $P_{m}^{h,r}$ of length $m\geq 1$ and cycles $C_{m}^{h,r}$ of length $m\geq 3$ are chromatically unique in the set of $h$-uniform $r$-quasi-linear hypergraphs provided $r\geq 2$ and $h\geq 3r-1$. \bigskip\noindent\textbf{Keywords:} quasi-linear hypergraph; sunflower hypergraph; quasi-linear path;\\ quasi-linear cycle; chromatic polynomial; chromatic uniqueness; potential function \end{abstract} \section{ Notation and preliminary results} A simple hypergraph $H=(V,{\cal E})$, with order $n=|V|$ and size $m=|{\cal E}|$, consists of a vertex-set $V(H)=V$ and an edge-set $E(H)={\cal E}$, where $E \subseteq V$ and $|E|\geq 2$ for each edge $E$ in ${\cal E}$. $H$ is $h$-uniform, or is an $h$-hypergraph, if $|E|=h$ for each $E$ in ${\cal E}$ and $H$ is linear if no two edges intersect in more than one vertex [1]. $H$ is said to be antilinear if for every two edges $E,F$ of $H$ we have $|E\cap F|\neq 1$. Let $r\geq 1$ and $h\geq 2r+1$. $H$ is said to be $r$-quasi-linear (or shortly quasi-linear) [13] if any two edges intersect in 0 or $r$ vertices. Examples of quasi-linear hypergraphs are $t$-stars [5, 8], also called sunflower hypergraphs [7, 11, 12]. We say that a hypergraph $S$ is a $t$-star with kernel $K$ where $K\subseteq V(S)$ and $t\geq 1$ if $S$ has exactly $t$ edges and $e\cap e'=K$ for all distinct edges $e$ and $e'$ of $S$. A system of $t$ pairwise disjoint edges (matching) is a $t$-star with empty kernel. In [12] a sunflower hypergraph was denoted by $SH(n,p,h)$; it is an $h$-hypergraph having a kernel of cardinality $h-p$, $n$ vertices and $k$ edges, where $n=h+(k-1)p$ and $1\leq p\leq h-1$.\\ A hypergraph for which no edge is a subset of any other is called Sperner. Two vertices $u,v\in V(H)$ belong to the same component if there are vertices $x_{0}=u,x_{1},\ldots,x_{k}=v$ and edges $E_{1},\ldots,E_{k}$ of $H$ such that $x_{i-1}$, $x_{i}\in E_{i}$ for each $i$ $(1\leq i\leq k)$ [1]. $H$ is said to be connected if it has only one component. An $h$-uniform hypertree is a connected linear $h$-hypergraph without cycles. We shall define two classes of quasi-linear uniform hypergraphs called quasi-linear elementary paths and quasi-linear elementary cycles and denoted by $P_{m}^{h,r}$ and $C_{m}^{h,r}$, respectively, as follows: $P_{m}^{h,r}$ consists of $m$ edges $E_1,\ldots,E_m$ such that $|E_1|=\ldots =|E_m|=h, |E_k\cap E_l|=r$ if $\{k,l\}=\{i,i+1\}$ for any $1\leq i\leq m-1$ and 0 otherwise. Cycles $C_{m}^{h,r}$ are defined analogously, by also imposing $|E_m\cap E_1|=r$. \par If $\lambda \in \mathbb{N}$, a $\lambda$-coloring of a hypergraph $H$ is a function $f: V(H)\rightarrow \{1,\ldots,\lambda \}$ such that for each edge $E$ of $H$ there exist $x$, $y$ in $E$ for which $f(x)\neq f(y)$. The number of $\lambda$-colorings of $H$ is given by a polynomial $P(H,\lambda)$ of degree $|V(H)|$ in $\lambda$, called the chromatic polynomial of $H$. $P(H,\lambda)$ can be obtained applying inclusion-exclusion principle, in the same way as for graphs, getting the following formula: \begin{equation} P(H,\lambda )= \sum _{W\subseteq E(H)}(-1)^{|W|}\lambda ^{c(W)}, \end{equation} where $c(W)$ denotes the number of components of the spanning subhypergraph induced by the edges from $W$. By rearranging terms in (1) we obtain that if $H$ has order $n$ then $P(H,\lambda)=\lambda ^{n}+a_{n-1}\lambda^{n-1}+\ldots +a_1\lambda $, where \begin{equation} a_i=\sum_{j\geq 0}(-1)^{j}N(i,j) \end{equation} and $N(i,j)$ denotes the number of spanning subhypergraphs of $H$ with $n$ vertices, $i$ components and $j$ edges [10].\\ All $h$-uniform hypertrees have the same chromatic polynomial. \begin{lemma} {\rm [6]}. If $T_{k}^{h}$ is any $h$-uniform hypertree with $k$ edges, then \begin{equation} P(T_{k}^{h},\lambda )=\lambda (\lambda ^{h-1}-1)^{k}. \end{equation} \end{lemma} Two hypergraphs $H$ and $G$ are said to be chromatically equivalent or $\chi$-equivalent, written $H\sim G$, if $P(H,\lambda)=P(G,\lambda)$. Let us restrict ourselves to the class of Sperner hypergraphs. A simple hypergraph $H$ is said to be chromatically unique if $H$ is isomorphic to $H'$ for every simple hypergraph $H'$ such that $H'\sim H$; that is, the structure of $H$ is uniquely determined up to isomorphism by its chromatic polynomial. The notion of $\chi$-unique graphs was first introduced and studied by Chao and Whitehead [4] (see also [9]). It is clear that all $h$-hypergraphs are Sperner. The notion of $\chi $-uniqueness in the class of $h$-hypergraphs may be defined as follows: An $h$-hypergraph $H$ is said to be $h$-chromatically unique if $H$ is isomorphic to $H'$ for every $h$-hypergraph $H'$ such that $H'\sim H$. \par Non-trivial chromatically unique hypergraphs are extremely rare. One example of a non-trivial chromatically unique hypergraph was proposed by Borowiecki and Lazuka; it is $SH(n,1,h)$. \begin{theorem} {\rm [3]} $SH(n,1,h)$ is chromatically unique. \end{theorem} The proof of this result was completed in [11]. Note that for $p=h-1$, $SH(n,h-1,h)$ is an $h$-uniform hypertree. The chromaticity of $SH(n,p,h)$ may be stated as follows. \begin{theorem} {\rm [12]} Let $n=h+(k-1)p$, where $h\geq 3$, $k\geq 1$ and $1\leq p\leq h-1$. Then SH(n,p,h) is $h$-chromatically unique for every $1\leq p\leq h-2$; for $p=h-1$ $SH(n,h-1,h)$ is $h$-chromatically unique for $k=1$ or $k=2$ but it has not this property for $k\geq 3$. Moreover, $SH(n,p,h)$ is not chromatically unique for every $p,k\geq 2$. \end{theorem} $SH(n,p,h)$ is quasi-linear with $r=h-p$ and it is a path for $k=2$.\\ Since $P_{2}^{h,r}$ is a sunflower hypergraph $SH(n,p,h)$ with $p=h-r$ having $k=2$ edges, from Theorem 1.3 it follows that $P_{2}^{h,r}$ is $h$-chromatically unique for every $1\leq r\leq h-1$. Also $P_{m}^{h,1}$ is an $h$-uniform hypertree, hence for $m\geq 3$ it is not $h$-chromatically unique. We shall prove that $P_{m}^{h,r}$ for every $m\geq 1$ and $C_{m}^{h,r}$ for every $m\geq 3$ are $h$-chromatically unique hypergraphs in the set of quasi-linear hypergraphs provided $r\geq 2$ and $h\geq 3r-1$. In [10] it was shown that $C_{m}^{h,r}$ is $h$-chromatically unique for $r=1$ and every $m,h\geq 3$, but it is not chromatically unique for $r=1$ and $m,h\geq 3$ [2]. The chromaticity of non-uniform hypertrees was studied by Walter [15]. \section{Main results} We need the following result about the first coefficients of the chromatic polynomial of a quasi-linear $h$-hypergraph with a particular structure relatively to subhypergraphs induced by 3 edges. \begin{lemma} Let $r\geq 2$, $h\geq 2r+1$ and $H$ be a quasi-linear $h$-hypergraph of order $n$ and size $m$ having the property that all subhypergraphs induced by $3$ edges have one of the following patterns:\\ $a) P_{3}^{h,r}$; $b) P_{2}^{h,r}$ and an isolated edge, or $c)\, \,3$ isolated edges. Then \begin{equation} P(H,\lambda)= \lambda ^{n}-m\lambda ^{n-h+1}+\beta _{1}\lambda ^{n-2h+r+1}+ \beta _{2}\lambda ^{n-2h+2}-\beta _{3}\lambda ^{n-3h+2r+1}+R(\lambda ), \end{equation} where $R(\lambda )$ is a polynomial in $\lambda $ of degree at most equal to $n-3h+2r$, $\beta _{2}$ is the number of pairwise disjoint edges of $H$ and $\beta _{1}$ and $\beta _{3}$ are the numbers of induced subhypergraphs of $H$ isomorphic to $P_{2}^{h,r}$ and $P_{3}^{h,r}$, respectively. \end{lemma} \begin{proof} By the hypothesis we have $n-h+1>n-2h+r+1>n-2h+2>n-3h+2r+1$. If $W\subset E(H)$ in (1) consists of one edge we get $N(n-h+1,j)=m$ if $j=1$ and $N(n-h+1,j)=0$ otherwise.\\ If $|W|=2$ then $N(n-2h+r+1,2)$ and $N(n-2h+2,2)$ count the number of unordered pairs $\{E,F\}$ of edges such that $|E\cap F|=r$ and $E\cap F=\emptyset$, respectively. In these two cases suppose that there exists an edge $G\in \mathcal{E}$, $G\neq E,F$, such that $G\subset E\cup F$. Denote $i=|G\cap E\cap F|$. It follows that $0\leq i\leq r$, $|G\cap (E\backslash F)|=r-i$, $|G\cap (F\backslash E)|=r-i$, thus yielding $h=|G|=2r-i\leq 2r$, which contradicts the hypothesis. It follows that $N(n-2h+r+1,j)=N(n-2h+2,j)=0$ for every $j\neq 2$ and $\beta _{1},\beta _{2}$ represent the numbers of induced subhypergraphs of $H$ consisting of $P_{2}^{h,r}$ and of an unordered pair of disjoint edges, respectively.\\ Similarly, if $|W|=3$, by the hypoyhesis 3 edges can induce only subhypergraphs of types a), b) or c). We obtain that $N(n-3h+2r+1),N(n-3h+r+2,3)$ and $N(n-3h+3,3)$ count the subhypergraphs of $H$ induced by an unordered triple of edges $\{D,E,F\}$ such that these subhypergraphs are isomorphic to $P_{3}^{h,r}$, $P_{2}^{h,r}$ and an isolated edge and 3 isolated edges, respectively. We also have $n-3h+2r+1>n-3h+r+2>n-3h+3$ since $r\geq 2$ and $N(n-3h+2r+1,j)=0$ for every $0\leq j\leq 2$.\\ If the edges $D,E,F$ of $H$ induce a $P_{3}^{h,r}$, where $D\cap F=\emptyset $, suppose that there exists an edge $G\neq D,E,F$ such that $G\subset D\cup E\cup F$. We have proved that $G\not \subset E\cup F$, thus implying $G\cap D\neq \emptyset$; similarly $G\not \subset D\cup F$ implies $G\cap E\neq \emptyset$. We have found 3 edges $D,E,G$ such that $D\cap E\neq \emptyset,D\cap G\neq \emptyset$ and $E\cap G\neq \emptyset$, which contradicts the hypothesis. This implies that $N(n-3h+2r+1,j)=0$ for every $j\geq 4$. Since by adding new edges to $W$ the number of components $c(W)$ decreases, it follows that $P(H,\lambda)$ is given by (4), where $\beta _{3}$ is the number of induced subhypergraphs of $H$ isomorphic to $P_{3}^{h,r}$. \end{proof} \begin{theorem} Let $H$ be an antilinear $h$-hypergraph such that $P(H,\lambda)=P(G,\lambda)$, where $G$ is $P_{m}^{h,r} (m\geq 1)$ or $C_{m}^{h,r} (m\geq 3)$. If $r\geq 2$ and $h\geq 3r-1$ then $H$ is isomorphic to $G$. \end{theorem} \begin{proof} It is trivial to see that $P_{m}^{h,r}$ for $1\leq m\leq 3$ and $C_{3}^{h,r}$ are $h$-chromatically unique. Let $m\geq 4$. We shall consider two subcases:\\ I. $G=P_{m}^{h,r}$ and II. $G=C_{m}^{h,r}$.\\ I. Let $H$ be an antilinear $h$-hypergraph such that $P(H,\lambda)=P(P_{m}^{h,r},\lambda)$.\\ The order of an hypergraph is being determined by the leading term of the chromatic polynomial, it follows that $H$ has order $n=h+(m-1)(h-r)$. From (2) one deduces that \begin{equation} P(P_{m}^{h,r},\lambda)=\lambda ^{n}-m\lambda ^{n-h+1}+\alpha _{1}\lambda ^{n-2h+r+1}+\alpha _{2}\lambda ^{n-2h+2}-\alpha _{3}\lambda ^{n-3h+2r+1}+Q(\lambda), \end{equation} where $Q(\lambda)$ is a polynomial of degree at most equal to $n-3h+r+2$, $\alpha _{1}=m-1$ is the number of subpaths $P_{2}^{h,r}$ of length two, $\alpha _{2}={{m}\choose{2}}-m+1$ is the number of pairs of pairwise disjoint edges and $\alpha _{3}=m-2$ is the number of subpaths $P_{3}^{h,r}$ of length three in $P_{m}^{h,r}$. Also since any spanning subhypergraph of $P_{m}^{h,r}$ induced by less than $m$ edges is not connected, it follows that in (5) the coefficient of $\lambda$ is $(-1)^{m}$, which implies that $H$ is also connected [15].\\ Since $H$ has all edges of cardinality $h$, it follows that the number of components of a spanning subhypergraph of $H$ may be $n,n-h+1$ or a smaller number. Any spanning subhypergraph of $H$ with $n$ vertices and $n-h+1$ components must contain only one edge. From (2) we deduce that $a_{n-h+1}=-N(n-h+1,1)=-|E(H)|$, hence $H$ has exactly $m$ edges. Every spanning subhypergraph of $H$ with $n$ vertices has two kinds of components: isolated vertices and components including at least $h$ vertices. The components including at least $h$ vertices will be called major components [10].\\ If such a spanning subhypergraph has at least two major components then it contains at most $n-2h+2$ components and this bound is reached when the major components are two disjoint edges and minor components are $n-2h$ isolated vertices. It follows that all coefficients $a_{n-h+1},\ldots,a_{n-2h+r+1}$ given by (2) correspond to the case when all spanning subhypergraphs of $H$ of order $n$ contain only one major component. In this way $N(n-h,j)$ counts the spanning subhypergraphs of $H$ consisting of a subset $Y$ of vertices (the major component) and $n-h-1$ isolated vertices, where $Y\subset V(H), |Y|=h+1$.\\ Denote by $\varphi (Y)$ the number of edges included in $Y$. Because $Y$ induces a component having $h+1$ vertices, it follows that $\varphi (Y)\geq 2$ and for each $i\geq 2$ the union of any $i$ edges included in $Y$ equals $Y$. Since $N(n-h,0)=N(n-h,1)=0$, by (2) we get $$ a_{n-h}=\sum _{j\geq 2}(-1)^{j}N(n-h,j)=\sum _{j\geq 2}(-1)^{j}\sum _{|Y|=h+1,\, \varphi (Y)\geq 2}{{\varphi (Y)}\choose{j}}$$ $$=\sum _{|Y|=h+1,\, \varphi (Y)\geq 2}\, \, \sum _{j\geq 2}(-1)^{j}{{\varphi (Y)}\choose{j}}= \sum _{|Y|=h+1,\, \varphi (Y)\geq 2}(\varphi (Y)-1).$$ Since $a_{n-h}=0$ it follows that no such $Y$ can exist, or equivalently, for any two distinct edges $E,F$ we have $|E\cup F|\geq h+2$. If $Y\subset V(H), |Y|=h+2$ and $E,F\in E(H),E\neq F$ and $E,F\subset Y$ we get $E\cup F=Y$ since $|E\cup F|\geq h+2$. Since $a_{n-h-1}=0$ we deduce in the same way that $|E\cup F|\geq h+3$ and by induction we obtain that for any two distinct edges $E,F\in E(H)$ we have $|E\cup F|\geq 2h-r$, or $|E\cap F|\leq r$.\\ Let now $Y\subset V(H), |Y|=2h-r$ be a major component of a spanning subhypergraph of $H$ such that $Y$ contains exactly $j\geq 2$ edges. We shall prove that $j=2$. For this let $E,F\subset Y$ be two distinct edges such that $E\cup F=Y$. Suppose that there exists an edge $G,G\neq E,F$ such that $G\subset Y$. By denoting $a=|(E\backslash F)\cap G|$ and $b=|(F\backslash E)\cap G|$ we get $a+b\leq h$. Since $|G\cup E|=h+b\geq 2h-r$, $|G\cup F|=h+a\geq 2h-r$, it follows $a,b\geq h-r$, hence $a+b\geq 2h-2r$, which implies $h\geq 2h-2r$. But this contradicts the hypotheses $h\geq 3r-1$ and $r\geq 2$. For hypergraph $H$ we can write $$\sum _{|Y|=2h-r,\, \varphi (Y)=2}1 = a_{n-2h+r+1}=m-1,$$ which implies that $H$ contains exactly $m-1$ pairs of edges $\{E,F\}$ such that $|E\cap F|=r$, or $|E\cup F|=2h-r$.\\ Let $p$ be such that $n-2h+2n-3h+2r+1$ and $n-3h+3r+1< n-2h+2$, unless $h=3r-1$. If $n-3h+3r+1