%        File: misc.tex
%
% (c) Copyright 2008 Andrea Lo Pumo aka AlpT <alpt@freaknet.org>
%
% This source code is free software; you can redistribute it and/or
% modify it under the terms of the GNU General Public License as published 
% by the Free Software Foundation; either version 2 of the License,
% or (at your option) any later version.
%
% This source code is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
% Please refer to the GNU Public License for more details.
%
% You should have received a copy of the GNU Public License along with
% this source code; if not, write to:
% Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
%

\documentclass[a4paper]{article}
%%% 	 Orientamento	      %%%
%\usepackage[landscape]{geometry}
%%%			      %%%

\usepackage{xr-hyper}
\usepackage{amath}


\externaldocument[AI-]{algebraI}[../../algebra/1/algebraI.pdf]
\externaldocument[GII-]{geometriaII}[../../geometria/2/geometriaII.pdf]
\externaldocument[AC-]{complementi}[../../algebra/complementi/complementi.pdf]
\ifpdf
\newcommand{\AI}[1]{\T{[AI,\ref{AI-#1},pg.\pageref{AI-#1}]}}
\newcommand{\GII}[1]{\T{[GII,\ref{GII-#1},pg.\pageref{GII-#1}]}}
\newcommand{\AC}[1]{\T{[AC,\ref{AC-#1},pg.\pageref{AC-#1}]}}
\else
\newcommand{\AI}[1]{\T{[AI,x.y.z,pg.xx]}}
\newcommand{\GII}[1]{\T{[GII,x.y.z,pg.xx]}}
\newcommand{\AC}[1]{\T{[AC,x.y.z,pg.xx]}}

% add label debugging if we are not compiling pdf.
\let\oldlabel\label
\renewcommand{\label}[1]{ [#1] \oldlabel{#1}}
\fi

\begin{document}
\title{Teoria degli Ipergrafi e Combinatoria}
\author{AlpT (@freaknet.org)\\
\small{\url{http://freaknet.org/alpt}}
}


\pagenumbering{roman}
\maketitle{}

\begin{abstract}
Questo testo e' una rielaborazione personale degli appunti presi durante
il corso di Modelli Discreti, tenuto dal Prof. Mario Gionfriddo presso il dipartimento di
Matematica, Catania, A.A. 2008/2009.\\
Saro' ben lieto di correggere ogni eventuale errore che mi comunicherai.

Buon lettura.
\begin{center}
	\verb|^_^|
\end{center}
\end{abstract}

\input{gpl}

\clearpage
\tableofcontents
\clearpage
\pagenumbering{arabic}

\let\oldsection\section
\renewcommand{\section}[1]{\oldsection{#1}\ilabel{#1}}
\let\oldsubsection\subsection
\renewcommand{\subsection}[1]{\oldsubsection{#1}\ilabel{#1}}
\let\oldsubsubsection\subsubsection
\renewcommand{\subsubsection}[1]{\oldsubsubsection{#1}\ilabel{#1}}

\def\P{{\mathcal{P}}}
\def\H{{\mathbb{H}}}
\def\E{{\mathcal{E}}}
\def\D{{\Delta}}
\def\N{{\mathbb{N}}}
\def\Z{{\mathbb{Z}}}
\def\cl#1{{{#1}^*}}
\def\crom{{\chi}}
\def\crn{{\chi}}
\def\K{{\mathbb{K}}}
\def\t{{\tau}}

\section{Ipergrafi}
\begin{defn}\label{defP}
	Sia $X$ un insieme,
	\eal{&\P(X)\definizione{=} \pgra{ Y\;|\;Y\( X}\\
	&\P_k(X) \definizione{=} \pgra{Y\;|\;Y\in \P(X),\;\;|Y|=k}
	}
\end{defn}
\begin{defn}
	$\H=(X,\E)$ e' un \iemph{ipergrafo} $\=$ $X \neq \0,\;\E\(
	\P(X)\-\pgra{\pgra{\0}}$.\\
	Gli elementi di $X$ si chiamano \iemph{vertici}. Gli elementi di $\E$,
	\iemph{spigoli}.\\
	Noi considereremo solo ipergrafi finiti, ovvero con $X,\E$ insiemi
	finiti.\\

	$\H\T{ e' uniforme } \definizione{\=} \exists k:\;|E|=k\;\forall E\in \E$
\end{defn}
\begin{defn}
	\ilabel{rango}
	Sia $\H=(X,\E)$ un ipergrafo,
	\eal{&r(\H)\definizione{=}\max_{E\in \E}|E|\\
	}
	$r(\H)$ si chiama \emph{rango} dell'ipergrafo.

	Sia $\H$ un ipergrafo \uline{uniforme}, poniamo:
	\eal{&\dim \H \definizione{=}r(\H)-1}
	\eal{&\H\T{ e' un $(k-1)$ grafo} \definizione{\=} \dim \H = k-1 \=
	r(\H)=k}
	Nota\footnote{si da' questa  definizione di dimensione perche' uno spigolo $E$
	di cardinalita' $|E|=k$ si puo' rappresentare geometricamente in uno
	spazio di dimensione $k-1$. Ad  esempio, se $|E|=3$, $E=\{a,b,c\}$,
	allora possiamo disegnare un triangolo in un piano. I vertici di tale
	triangolo saranno $a,b,c$ mentre il triangolo per intero
	rappresentera' $E$. Se abbiamo $|E|=4$, $E=\pgra{a,b,c,d}$, allora
	possiamo rappresentare $E$ con un tetraedro.}
	\eal{
	&d:\P(X) \longrightarrow \N\NN
	d(T) \definizione{=} \pass{\pgra{E\in \E\;|\;T\( E}}\\
	&d:X\longrightarrow \N\\
	&d(x)\definizione{=} d(\pgra{x})=\pass{\pgra{E\in \E\;|\;x\in E}}\\
	&\D(\H)\definizione{=}\max_{x\in X} d(x)\NN
	}
	$d(x)$ e' il \iemph{grado} del vertice $x$.\\
	$\D(\H)$ e' il grado massimo di $\H$.
\end{defn}
\begin{defn}
	\label{ipergrafo!lineare}
	Sia $\H=(X,\E)$ un ipergrafo,
	\eal{&\H \T{ e' lineare }\= |E\^F|\le 1 \;\forall E,F\in \E,\;E \neq
	F}
\end{defn}
\begin{defn}
	\label{ipergrafo!regolare}
	$\H$ e' regolare di grado $k$ $\= \forall x\in X\;\;d(x)=k$
\end{defn}
\begin{defn}
	Sia $\H=(X,\E)$, definiamo
	\eal{&\cl\H = (X,\cl\E)\\
	&\cl\E=\pgra{F\;|\;\exists E\in \E:\;F\( E,\;F \neq \0}
	}
	$\cl\H$ e' la \iemph{chiusura} di $\H$.\\
	In pratica, in $\cl\E$ stiamo  considerando tutti gli spigoli di $\E$ e
	tutti i loro sottoinsiemi.
\end{defn}
\begin{conje}\label{conj1}
	\eal{&\H=(X,\E) \T{ lineare } \> \exists C=\pgra{C_j}_{j\in J}\T{
	partizione di } \cl\E\T{ t.c. } \sist{|C|=\D(\cl\H)\\
					      A\^B=\0\;\;\forall A,B\in
					      C_j,\;A \neq B\;\;\forall j \in
					      J}
	}
	Nota: richiediamo che le classi siano in numero $\D(\cl\H)$ perche'
	questo e' il piu' piccolo possibile per rispettare la condizione 
	$A\^B=\0$. (Infatti, il vertice $x\in X:\;\cl
	d(x)=\D(\cl H)$ deve stare in almeno $\D(\cl H)$ classi distinte.)
\end{conje}
\begin{exemp}\label{expconj1}
	Consideriamo il seguente ipergrafo:
	\eal{&X=\pgra{1,\dots,7}\NN
	\E=\pgra{\pgra{1,2,3},\pgra{1,4,5},\pgra{1,6,7},\pgra{2,4,6},\pgra{2,5,7},\pgra{3,4,7},\pgra{3,5,6}}
	}
		\begin{center}
			\includegraphics[scale=0.24]{fig/c1}
		\end{center}
	$\H=(X,\E)$ e' un ipergrafo lineare di rango 3. E' lineare ed e' anche
	regolare. Quindi, anche $\cl\H$ e' regolare.  $\D(\cl\H)=10$.
	Una possibile partizione di $\cl\E$ che rispetta la congettura
	\see{conj1} e':
	\begin{center}
		\begin{tabular}{c|c|c|c|c|c|c|c|c|c}
			123 & 167 & 12 & 13 & 14 & 15 & 16 & 17 &145 & 1\\
			45&   25&   347&246 &257 &26  & 47 &24  &23 & 46\\
			67&   34&    56&57  &36  &37&   35 &356 &6  & 27\\
			  &     &       &    &   &4 &    2 &    &7  &3\\
			  &     &       &    &   & &     &    &  &5
		\end{tabular}
	\end{center}
	Inoltre possiamo osservare che ogni classe e' a sua volta una
	partizione di $X$.
\end{exemp}
\begin{defn}
	\ilabel{colorazione!vertici}
	Sia dato un ipergrafo $\H=(X,\E)$ e sia data una funzione
	$f:X\longrightarrow C$, con $C$ insieme arbitrario, chiamato insieme
	dei colori.
	\eal{&f\T{ e' una colorazione di } X\definizione{\=}
	\forall E \in \E:\;|E| \ge 2\; |f(E)| \ge 2\=
	\forall E \in \E:\;\exists x,y\in E;\;f(x) \neq f(y)\=
	\\
	&f\T{ e' una colorazione forte di }X\definizione{\=}
	\forall E\in \E\;\;f_{|E}\T{ e' iniettiva } \=
	\forall E\in \E \;\forall x,y\in E:x \neq y\;\;f(x) \neq f(y)
	}
\end{defn}
\begin{rem}\label{colorazioneforteedebole}
	\eal{&1.\;\;f\T{ e' una colorazione forte } \> f\T{ e' una colorazione
	debole}\\
	&2.\;\;f:X\longrightarrow C\T{ e' una funzione iniettiva } \> f\T{
	e' una colorazione forte}
	}
	La $2.$ garantisce l'esistenza delle colorazioni. Non vale
	il viceversa della $1.$ e della $2.$ (trova i controesempi).
\end{rem}
\begin{rem}
	In un grafo la defizione di colorazione forte coincide con quella di
	colorazione debole.
\end{rem}
\begin{defn}
Definiamo il
	\iemph{numero cromatico}:
	\eal{&\chi(\H)=\min\pgra{|f(X)|\;|\;f:X\longrightarrow C\T{ colorazione
	di X}}}
Analogamente definiamo il numero cromatico forte:
	\eal{&\chi_F(\H)=\min\pgra{|f(X)|\;|\;f:X\longrightarrow C\T{ colorazione
	forte di X}}}
\end{defn}
\begin{prop}\label{xiFgexi}
	Dalla $\see{colorazioneforteedebole}$ si ha subito che
	\eal{&\chi_F(\H) \ge  \chi(\H)
	}
\end{prop}
\begin{defn}
	\ilabel{colorazione!spigoli}
	Sia dato un ipergrafo $\H=(X,\E)$ e sia data una funzione
	$f:\E\longrightarrow C$, con $C$ insieme arbitrario, chiamato insieme
	dei colori.
	\eal{&f\T{ e' una colorazione di } \E
	\definizione{\=} 
	\forall E,E' \in \E:\;E\^E' \neq \0,\;E \neq E'\T{ si ha } \;\;f(E) \neq f(E')
	}
	Ovvero, gli spigoli che si incontrano non devono avere lo stesso
	colore.
\end{defn}
\begin{defn}
Definiamo l'\iemph{indice cromatico}:
	\eal{&\chi'(\H)=\min\pgra{|f(\E)|\;|\;f:\E\longrightarrow C\T{ colorazione
	di $\E$}}}
\end{defn}
\begin{prop}
	\eal{&\chi'(\H) \ge  \Delta(\H)
	}
\end{prop}
\begin{proof}
	Sia $x\in X$ un vertice tale che $d(x)=\Delta(X)$ e sia $f$ una
	qualsiasi colorazione di $\E$, si ha
	\eal{&\T{Sia } \E_x=\pgra{E\in \E\;|\;x\in E}, \T{ e sia } f\T{ una
	colorazione t.c. }|f(\E)|=\chi'(\H), \T{ ovvero, una di quelle piu'
	piccole}\NN
	 |\E_x| = d(x) = \Delta(X)\NN
	 E,E'\in \E_x,\;\;E \neq E'  \ubrace{\>}{x\in E,E'}  E\^ E'  \neq 0 \>f(E) \neq
	 f(E')\NN
	 \qq \> f(E) \neq f(E')  \;\;\forall E,E'\in \E_x,\;E \neq E'
	 \> f_{|\E_x} \T{ e' iniettiva }  \>  \Delta(X) = d(x)=|\E_x| = |f(\E_x)| \le 
|f(\E)| = \chi'(\H)
	 }
\end{proof}
%\begin{defn}
%	\ilabel{ciclo}
%	Grafo ciclico:
%	\eal{&C_n\definizione{=}(X,E)\T{ dove } \sist{|X|=n\\
%	\forall x\in X\;\;d(x)=2\exists !(E,E')\in \E^2\;\;
%	\;E\^E'=\pgra{x}
%	}
%	}
%\end{defn}
\begin{defn}
	\ilabel{ipergrafo!completo}
	Ipergrafo completo:
	\eal{&(X,\E)\in \K_{n,k} \definizione{=}(X,\E)\T{ ipergrafo con }
	\sist{|X|=n\\
	\E=\P_k(X)}
	}
	Grafo completo:
	\eal{&\K_n\definizione{=} \K_{n,2}
	}
	$\H=(X,\E)$ e' un ipergrafo completo $\definizione{\=}\exists
	n,k:\;\;|X|=n,\;\E=\P_k(X)$
\end{defn}
\begin{prop}
	\eal{&\H\T{ ipergrafo completo } \> H\T{ regolare }}
	Non vale il viceversa (considera il grafo $C_4$ (il quadrato)).
\end{prop}
\begin{defn}
	Sia $\H=(X,\E)$ un ipergrafo. $\pgra{C_{i}}_{i=1}^{n}
	\( \P(\E)$ e' 
una 	\iemph{1-fattorizzazione} di $\H$ $\definizione{\=}$
\eal{&1.\;\;\pgra{C_{i}}_{i=1}^{n} \T{ e' una partizione di }\E\NN
2.\;\;C_i\T{ e' una partizione di }X\;\;\forall i=1,\dots,n-1
}
\end{defn}
\begin{prop}\label{prop1fatt}
	Sia $(X,\E)\in \K_n$ un grafo completo di ordine $n$, cioe' $|X|=n$,
	$\E=\P_2(X)$. 
	\eal{&\pgra{C_{i}}_{i=1}^{m} \T{ e' una 1-fattorizzazione di $(X,\E)$ }
	\> \sist{m=n-1\\
	|C_i|=\frac{n}{2}\\
	n\T{ e' pari}
	}
	}
\end{prop}
\begin{proof}
	\eal{&C_i\in \P(\E) \> \forall c\in C_i\;\;c\in \E=\P_2(X) \>
	|c|=2\;\;\forall c\in C_i\NN
	C_i\T{ partizione di }X \> |X|=\pass{\bigcup_{c\in C_i} c} 
	=\sum_{c\in C_i}|c| = \sum_{c\in C_i} 2 =  2|C_i| \> |C_i| =
	\frac{|X|}{2} \in \N \> |X|\T{ e' pari }\NN
	\pgra{C_i}_{i=1}^m \T{ partizione di }\E \>
|\E|=\pass{\bigcup_{i=1\dots,m} C_i}
=\sum_{i=1\dots,m}|C_i| = \sum_{i=1\dots,m} \frac{|X|}{2} = m \frac{|X|}{2}
\>\NN
\>m = |\E| \frac{2}{|X|} = |\P_2(X)|\frac{2}{|X|} =
\frac{n!}{2(n-2)!}\frac{2}{n}=n-1
	}
\end{proof}
\begin{thm}\label{thmesistefattorizzazione}
	Sia $K_n\in \K_n$
	\eal{& n\in 2\mathbb{N}^*\;\=\;\exists \T{ una 1-fattorizzazione di
	}K_n}
\end{thm}
\begin{proof}
	\BEGINsufficiente
	Per la prop \see{prop1fatt} sappiamo che $n$ deve essere pari.	
	\END
	\BEGINpnecessaria
	Sia $X=\pgra{A,0,1,\dots,m-1}$, dove $A$ e' una qualsiasi lettera  e
	$m=n-1$. Scegliamo la seguente fattorizzazione
	\eal{&C_i \T{ e' l'insieme formato dai seguenti insiemi }: 
	\NN
	\qq \pgra{i,A}\NN
	\qq \pgra{i-1,i+1}\NN
	\qq \pgra{i-2,i+2}\NN
	\qq \vdots\NN
	\qq \pgra{i-\frac{n-2}{2},\;i+\frac{n-2}{2}}\NN
	\T{ovvero, }\NN
\forall i=0,\dots,m-1\;\;	C_i=\pgra{ \pgra{i,A}}
	\U \bigcup_{j=1,\dots,\frac{n-2}{2}} \pgra{\pgra{i-j,i+j}}
	}
	dove le addizioni si intendono in $\Z_m$.\\

	Se si rappresenta $K_n$ su un cerchio in cui i vertici sono stati
	numerati e disposti ordinatamente da $0,1,2,\dots,m-1$ e un vertice e'
	stato chiamato $A$, allora e' immediato
	intuire come funziona questa partizione.\\

	In ogni caso, ecco la dimostrazione formale.
	\step{}{$C_i$ e' una partizione di $X=\pgra{A,0,1,\dots,m-1}$}
	\begin{prova}
	\eal{&
	\frac{n-2}{2} = \frac{n}{2}-1 \ubrace{<}{n>0} n-1\;\;(1)\NN
	1\le j\le \frac{n-2}{2} < n-1=m\;\;(1.1)\NN
	i\pm j= i\pm j'\;\;\Z_m \=  \pm j=\pm j'\;\;\Z_m  \ubrace{\=}{(1.1)} j=j'\NN
	i=i\pm j \= \pm j =0\;\;\Z_m \= m\div \pm j \T{ assurdo contro
	}(1.1)\NN
	}
	Quindi due elementi di $C_i$ sono necessariamente disgiunti. Tra
	l'altro
	\eal{&i-j=i+m-j=i+n-1-j\;\;\Z_m
	}
	I numeri  che consideriamo sono quindi:
	\eal{&i\NN
	i+1,i+2,\dots,i+\frac{n-2}{2}=i+\frac{n}{2}-1\NN
i+n-1-1=i+n-2, i+n-3,\dots,i+n-1-\frac{n-2}{2}=i+\frac{n}{2}, 
	}
	ovvero
	\eal{&\pgra{i\pm j\;|\;j=0,1,\dots,n-2} = \pgra{0,1,\dots,n-2}}
	Poiche' $\pgra{i,A}\in C_i$, possiamo affermare che 
	\eal{&\bigcup C_i = \pgra{A,0,1,\dots,n-2}= X
	}
	\end{prova}
	\step{}{$C_i\^C_h=\0\;\;\forall i \neq h$}
	\begin{prova}
		\case{$\pgra{i,A}\in C_h$}
		\begin{prova}
			L'unico elemento di $C_h$ che contiene $A$ e'
			$\pgra{h,A}$ quindi
			\eal{&\pgra{i,A}=\pgra{h,A} \> i=h
			}
			\T{ assurdo } 
		\end{prova}
		\case{$\pgra{h,A}\in C_i$}
		\begin{prova}
			analogamente a prima.
		\end{prova}
		\step{}{$\pgra{i-j,i+j}\in C_h$}
		\begin{prova}
			Supponiamo $i<h$,
			\eal{&\pgra{i-j,i+j}\in C_h 
			\> \pgra{i-j,i+j}=\pgra{h-j',h+j'}
			}
			Supponiamo $i-j=h-j',\;\;i+j=h+j'$.
			\case{$j=j'$}
			\begin{prova}
				\eal{&i=h\;\;\Z_m \ubrace{\>}{i,h\le m-1} i=h}
				assurdo.
			\end{prova}
			Supponiamo $j<j'$
			\eal{&1\le j<j'\le \frac{n}{2}-1 \> \exists 
			0<k<j':\;\;j+k=j'\NN
			2k<2j' \le  n-2=m-1\;\;(*)\NN
			i-j=h-j'\;\;\Z_m \> i=h-j'+j\;\;\Z_m\NN
			i+j=h+j'\;\;\Z_m \> i=h+j'-j\;\;\Z_m\NN
			\qq \> h-j'+j = h+j'-j \= 2j = 2j'
			=2j+2k\=2k=0\;\;\Z_m  \ubrace{\>}{(*)} 2k =0 \> k=0 \>
			j=j'
			}
			assurdo.\\
			Analogamente si procede negli altri casi.
		\end{prova}
	\end{prova}

	Come dimostrazione alternativa, vedi \begin{quote}
	J. Korean Math. Soc. 45 (2008), No. 5, pp. 1243-1253\\
        A CONSTRUCTION OF ONE-FACTORIZATION\\
			       Yoonyoung Choi, Sang-Mok Kim, Seon-Ju Lim, and
			       Bongjoo Park\\
\url{http://www.mathnet.or.kr/mathnet/thesis\_file/03\_J06-478.pdf}
	\end{quote}
	\END
\end{proof}

\begin{thm}\label{thmsumdx}
	Sia $\H=(X,\E)$ un ipergrafo uniforme di rango $k$. Si ha:
	\eal{&\sum_{x\in X}d(x) = k|\E| =|E||\E|
	}
\end{thm}
\begin{proof}
$d(x)$ indica quante volte $x$ compare negli spigoli:
\eal{&d(x)=\sum_{E\in \E}\psi_E(x),\;\;\T{ con }\psi_E(x)=\sist{1&x\in E\\
0&\T{altrimenti}}
	}
Quindi il gioco e' fatto:
\eal{&\sum_{x\in X}d(x) = \sum_{x\in X}\sum_{E\in \E}\psi_E(x)
=\sum_{E\in \E}\sum_{x\in X}\psi_E(x) = \sum_{E\in \E}|E| = |E| |\E|
	}
\end{proof}
\begin{cor}
	Sia $\H=(X,\E)$ un ipergrafo uniforme di rango $k$.
	\eal{&k\T{ pari } \> |\pgra{x\in X\;|\;d(x)\T{ dispari }}| \T{ e' pari}
	}
\end{cor}
\begin{proof}
	$k=2m$. Se per assurdo $|\pgra{x\in X\;|\;d(x)\T{ dispari }}|=2b+1$,
	si avrebbe
	\eal{&\sum_{x\in X:\;d(x)\T{ dispari}}d(x)=
	\sum_{x\in X:\;d(x)\T{ dispari}} 2c_x+1
	= 2\pton{\sum_{x\in X:\;d(x)\T{ disp.}} c_x}+2b+1 =2a+1=\T{ dispari
	}\;\;(1)\NN
	\sum_{x\in X}d(x) = \sum_{x\in X:\;d(x)\T{ pari}}d(x) +\sum_{x\in
	X:\;d(x)\T{ dispari}}d(x)  \ubrace{=}{(1)} 
	2t+2a+1=\T{ dispari}\NN
	\sum_{x\in X}d(x)  \ubrace{=}{\see{thmsumdx} } k|\E| = 2m|\E| =\T{
	pari}
	}
	assurdo.
\end{proof}
\begin{defn}\label{deftrasversale}
	Sia $\H=(X,\E)$ un ipergrafo e $T\(X$
	\eal{&T\T{ e' un trasversale di }\H \definizione{\=} \forall E\in \E\;\;T\^E \neq
	\0\NN
	\tau(\H)\definizione{=}\min_{T\T{ trasversale di }\H}|T|
	}
	$\t(\H)$ e' il \iemph{numero di trasversalita'} di  $H$.
\end{defn}
\begin{rem}
	$X$ e' un trasversale, quindi l'insieme dei trasversali e' non vuoto.
\end{rem}
\begin{exemp}
	Si consideri l'ipergrafo dell'esempio \see{expconj1}. Si ha $\forall
	E\in \E\;\;E$ e' un trasversale di $X$.\\
	Inoltre, $\t(\H)=3$.
\end{exemp}
\begin{defn}\label{defblockset}
	\ilabel{blocking-set}
	$H=(X,\E)$. Sia $B\(X$
	\eal{&B\T{ e' un blocking-set (blocking-set) } \definizione{=} 
	B,\;X\-B \T{ sono trasversali }
	}
\end{defn}
\begin{rem}
	Non e' detto che esistano blocking-set di $\H$. Ad esempio,
	l'ipergrafo $\pton{\pgra{1,2},\pgra{\pgra{1},\pgra{2}}}$ non ha
	blocking-set.
\end{rem}
\begin{prop}
	\eal{&E\in \E \> E\T{ non e' un blocking-set}
	}
\end{prop}
\begin{proof}
	Infatti,
	\eal{&(X\-E)\^E =\0 \> X\-E\T{ non e' un trasversale}}
\end{proof}
\begin{prop}
	\eal{&B\T{ blocking set di } (X,\E) \> X\-B \T{ blocking set di
	}(X,\E)
	}
\end{prop}
\begin{exemp}
	Consideriamo
	\eal{&\H=(X,\E)\NN
	X=\pgra{1,2,\dots,8}\NN
	\E:  1234, 5678, 1256, 1278, 3456, 3478\NN
	\qq 1357, 1368, 2457, 2768, 1458, 1467, 2358, 2367}
	Si puo' verificare che ogni $B\in \P_4(X)\-\E$ e' un
	blocking-set, ad esempio $B=\pgra{1,2,3,7}$ (vedi \see{SQSbset},
	\see{expSQSbset}).
\end{exemp}
\begin{exemp}\label{esempiograficobset}
Graficamente, possiamo rappresentare un blocking set $B$ cosi':
	\begin{center}
		\includegraphics[scale=0.5]{fig/bset}
	\end{center}
I pallini rappresentano i punti di $X$. Gli ovali rappresentano gli spigoli di
$\E$.
\end{exemp}
\begin{prop}\label{equivalenzabsetchi}
	\eal{&\exists B\T{ bset di } \H=(X,\E) \= \chi(\H) = 2,\;\;\forall
	E\in \E\;\;|E| \ge 2
	}
	dove $\chi$ e' il numero cromatico (\vedi{numero cromatico}).\\

	Nota che $2$ e' il piu' piccolo numero cromatico che si possa
	ottenere.
\end{prop}
\begin{proof}
	Intuitivamente, basta osservare la rappresentazione grafica di un
	bset (\vedi{esempiograficobset}): ai punti di sinistra assegnamo un
	colore e a quelli di destra ne assegnamo un altro. Viceversa, se
	abbiamo una colorazione che usa solo due colori, un blocking set sara'
	l'insieme di tutti i vertici che hanno un solo colore.
	\BEGINpnecessaria
	Definiamo la seguente colorazione:
	\eal{&f(x)=\sist{1& x\in B\\
	0 & x\in X\-B}
	}
	$f$ e' una colorazione: sia $E\in \E:\;|E| \ge 2$, allora se per
	assurdo $|f(E)|=1$, si ha
	\eal{&f(E)=1 \= E\(B  \|  E\( X\-B\NN
	E\( B \> X\-B\^E=\0\NN
	E\( X\-B \> B\^E=\0
	}
	assurdo contro $B$ blocking set.\\

	Infine, se per assurdo $\exists E\in \E:\;\;|E|=1$, allora si possono
	verificare due casi
	\eal{&E \( B, \;\; E\(X\-B
	}
	ma come abbiamo visto, questo e' assurdo contro $B$ blocking set.
	\END
	\BEGINsufficiente
	\eal{&\chi(\H) =2 \> \exists f\T{ colorazione: } |f(X)|=2 \=
	f(X)=\pgra{a,b},\;a \neq b\NN
	\T{sia } B=\inv f(a)\NN
	\pgra{\inv f(a),\inv f(b)}\T{ e' una partizione di }X \> X\-B = \inv f(b)
	}
	$B$ e' un blocking set, infatti, sia $E\in \E$
	\eal{& E \( X,\;|E| \ge 2,\;f\T{ colorazione }   \> \exists x,y\in
	E:\;\;f(x)=a,\;f(y)=b \> x\in B,\;y\in X\-B \> B\^E \neq \0,\;X\-B\^E
	\neq \0
	}
	Quindi, sia $B$ che $X\-B$ sono dei trasversali.
	\END
\end{proof}
\section{Sistema di Steiner}
\def\l{{\lambda}}
\begin{defn}
	Sistema di Steiner.\ilabel{Steiner!sistema di}
	\eal{&\H=(X,\E)\in S_\l(h,r,v)\definizione{ \=} \sist{|X|=v\\
	\H\T{ e' uniforme di rango } r\\
	\forall Y\in \P_{h}(X)\;\;d(Y)=\l
	}\NN
	S(h,r,v)\definizione{=} S_1(h,r,v)
	}
	Nota: chiaramente si richiede $1\le h \le  r\le v$.\\

	Gli elementi di $\P_h(X)$ verranno chiamati $h$-\iemph{oggetti} di $X$.
\end{defn}
\begin{exemp}
L'ipergrafo dell'esempio \see{expconj1} appartiene a $S_1(2,3,7)$
\end{exemp}
\begin{domanda}
	Il problema di Woolhouse (1844) e' ancora un aperto. La domanda e':
	\eal{&S_{\l}(h,r,v) \neq \0  \;\;?
	}
	O in altri termini, per quali $\l,h,r,v$ esiste almeno un ipergrafo in
	$S_{\l}(h,r,v) $?
\end{domanda}
\begin{exemp}
	I casi $h=r,r=v,h=v$ si riducono a sistemi banali. Esaminiamo quelli
	con $\l=1$.\\
Per definizione si deve avere $1\le h\le r\le v$.
\begin{prova}
	\case{$h=r$}
	\begin{prova}
		Si ha direttamente che:
		\eal{&(X,\E)\in S(h,h,v)\=
		\E=\P_h(X)
		}
	\end{prova}
	\case{$r=v$}
	\begin{prova}
		\eal{&                (X,\E)\in S(h,r,r)  \= \E=\pgra{\pgra{X}}
		}
	\end{prova}
	\case{$h=v$}
	\begin{prova}
		\eal{&1\le h \le  r \le  h \> h=r=v}
		e quindi torniamo nel caso $r=v$:
		\eal{&
		(X,\E)\in S(h,h,h)
		\= \E=\pgra{\pgra{X}}
		}
	\end{prova}
\end{prova}
\qq\\
Esaminiamo adesso il caso $h=1,\l=1$. Si vede facilmente che:
\eal{&(X,\E)\in S(1,r,v)\= \sist{\E\T{ e' una partizione  di } X\\
\forall E\in \E\;\;|E|=r
}
\;\;(1)
}
infatti, basta osservare che gli spigoli sono disgiunti tra loro
$(\l=1)$, ciascuno ha cardinalita' $r$, e che $\bigcup_{E\in \E} E=X$ perche'
$h=1$ permette di scegliere qualsiasi elemento di $X$.\\
Dalla $(1)$ possiamo dedurre che:
\eal{&S(1,r,v) \neq \0 \= r\div v
}
\end{exemp}

\begin{prop}	\label{propderivato}
	Sia $x\in X$. Posto
	\eal{&
	\E_x=\pgra{E\in \E\;|\;x\in E}\NN
	\E_x' =\pgra{E\-\pgra{x}\;|\;E\in \E_x}
	}, si ha
	\eal{&\H=(X,\E) \in S(h,r,v) \> \H_x'=(X\-\pgra{x}, \E_x')\in
	S(h-1,r-1,v-1)
	}
	$\H_x'$ e' chiamato l'\iemph{ipergrafo derivato} di $\H$ secondo $x$
\end{prop}
\begin{proof}
Intanto,  $\H_x'$ e' chiaramente un ipergrafo uniforme di rango $r-1$.\\
Sia $Y\in \P_{h-1}(X\-\pgra{x})$.\\ $d_x'(Y)\ge 1$ (nota\footnote{$d_x'$ e' il grado di
$Y$ in $\H_x'$}), infatti,
\eal{&Y\U\pgra{x} \in \P_h(X)  \ubrace{\>}{\H\in S(h,r,v)} \exists E\in
\E:\;Y\U\pgra{x}\(E \> Y\( E\-\pgra{x}\in \E_x' \> d_x'(Y) \ge 1
}
Se per assurdo $d_x'(Y) >1$, si avrebbe:
\eal{&d_x'(Y) >1 \> \exists C_1,C_2\in \E_x':\;C_1 \neq C_2,\;Y\( C_1\^C_2
\> Y\U\pgra{x}\( (C_1\U\pgra{x})\^(C_2\U\pgra{x}) \> 
d(Y\U\pgra{x}) > 1
}
ma questo e' assurdo contro $d(Z)=1\;\;\forall Z\in \P_h(X)$.
\end{proof}
\begin{prop}\label{propSgradoTh-1}
Sia $\H=(X,\E) \in S(h,r,v)$, allora
\eal{&T\in \P_{h-1}(X) \> d(T)=\frac{v-h+1}{r-h+1}
	}
\end{prop}
\begin{proof}
	Sia $\E_T=\pgra{E\in \E\;|\;T\( E}$. Si ha
	\eal{& y\in X\-T \ubrace{\>}{\H\in S(h,r,v),\;|T|=h-1} 
	\exists ! E\in \E:\;T\U\pgra{y}\( E\;\;(1)\NN
	E_1,E_2\in \E_T:\;E_1 \neq E_2 \> (E_1\-T)\^(E_2\-T)=\0\;\;(2)\NN
	\qq \T{
	infatti, se per assurdo }\NN
	\qq y\in E_1\^E_2\-T \> T\U\pgra{y}\(E_1,E_2\T{ assurdo contro
	}(1)\NN
	\bigcup_{E\in \E_T}E\-T=X\-T\;\;(3)\NN
	\qq\T{ infatti, } y\in X\-T \ubrace{\>}{(1)} 
	\exists ! E\in \E:\;T\U\pgra{y} \( E \> T\( E \> E\in \E_T \> y\in  \bigcup_{E\in
	\E_T}E\-T\NN
	(2),(3) \> E_T' =\pgra{E\-T\;|\;E\in \E_T}\T{ e' una
	partizione di }X\-T\;\;(4)\NN
	(4) \> |X\-T| = \sum_{E'\in E_T'}|E'|   \ubrace{=}{|
	E'|=r-|T|=r-(h-1)\;\;\forall E'\in E_T'}
	(r-h+1)|{\E_T}|=(r-h+1)d(x) \>\NN
	\>
	d(x)=\frac{|X\-T|}{r-h+1}=\frac{v-(h-1)}{r-h+1}
	}
\end{proof}


\subsection{S(h,h+1,v)}
\begin{prop}
	\label{Shh+1prop1}
	\eal{&(X,\E) \in S(h,h+1,v) \> |\E| = 
	\frac{\binom{v}{h}}{\binom{h+1}{h}}=\frac{v!}{(h+1)!(v-h)!}
	}	
\end{prop}
\begin{proof}
Ogni oggetto $C\in \P_h(X)$ deve essere contenuto in un solo
	spigolo. Ogni spigolo contiene $\binom{h+1}{h}$ oggetti. Quindi tutti
	gli oggetti
	contenuti dagli spigoli sono
	in numero $\binom{h+1}{h}|\E|$.\\
	Tutti gli oggetti contenuti dagli spigoli sono
	tutti gli oggetti possibili.\\
	Percio':
	\eal{&|\P_h(X)| = \binom{v}{h} \NN  
	\binom{h+1}{h}|\E| = |P_h(X)| \> |\E|= \frac{\binom{v}{h}}{
	\binom{h+1}{h}} = \frac{v!}{(h+1)!(v-h)!} 
	}
In termini formali:
	\eal{&(X,\E) \in S(h,h+1,v) \> \forall C\in \P_h(X)\;\;d(C)=1 \= \forall C\in \P_h(X)
	\;\;\exists ! \;E\in \E:\;\;C\( E\;\;(1)\NN
	(X,\E) \T{ uniforme di rango } h+1 \> |E| =h+1\;\forall E\in \E \>
	|\P_h(E)|=\binom{h+1}{h}\;\;\forall E\in \E\;\;(2)\NN
	C_1\in \P_h(E_1), \;C_2\in \P_h(E_2),\;E_1,E_2\in \E,\;E_1 \neq E_2
	\ubrace{\>}{(1)}  C_1 \neq C_2\;\;(3)\NN
	(3)\=\P_h(E_1)\^\P_h(E_2)=\0\;\;\forall E_1,E_2\in \E:\;E_1 \neq
	E_2\;\;(3.1)\NN
	|\pgra{C\in \P_h(X)\;|\;\exists E\in \E:\;C\( E}|  =
	|\bigcup_{E\in \E}\P_h(E)|  \ubrace{=}{(3.1)} 
	\sum_{E\in \E} |\P_h(E)|  \ubrace{=}{(2)} |\E|\binom{h+1}{h}\;\;(4)\NN
	\pgra{C\in \P_h(X)\;|\;\exists E\in \E:\;C\( E}  \ubrace{=}{(1)}
	\P_h(X)\;\;(5)\NN
	|P_h(X) | = \binom{v}{h} \;\;(6)\NN
	\binom{v}{h}  \ubrace{=}{(6)}   |\P_h(X)|  \ubrace{=}{(5),\;(4)} |\E|\binom{h+1}{h}
	\> |\E|= \frac{|\P_h(X)|}{\binom{h+1}{h}}=
	\frac{\binom{v}{h} }{\binom{h+1}{h}}
	=\frac{v!}{h!(v-h)!}\frac{h!(h+1-h)!}{(h+1)!}
	=\frac{v!}{(v-h)!(h+1)!}
	}
\end{proof}
\begin{prop}
		\label{Shh+1gradox}
		\eal{&\H=(X,\E) \in S(h,h+1,v) \> \H \T{ e' regolare di grado  }
		\frac{\binom{v-1}{h-1}}{\binom{h}{h-1}}=\frac{(v-1)!}{h!(v-h)!}
	}
\end{prop}
\begin{proof}
	Fissiamo  $x\in X$ e sia $\H_x'$ il derivato di $\H$. Per la prop
	\see{propderivato}
	 si ha
	 \eal{&\H_x'\in S(h-1,h,v-1) \;\;(1)\NN
	 d(x)=|\E_x|  \ubrace{=}{\see{Shh+1prop1}} 
	\frac{\binom{v-1}{h-1}}{\binom{h}{h-1}}=\frac{(v-1)!}{h!((v-1)-(h-1))!}
	 }
\end{proof}

\subsection{Steiner Triple System}
\def\STS{\oname{STS}}
\begin{defn}
	\eal{&\STS(v)\definizione{=} S(2,3,v)}
\end{defn}
\begin{rem}
	Gli STS vengono anche chiamati \iemph{Spazi di rette}, infatti,
	chiamando ``rette'' gli spigoli $E\in \E$ e ``punti'' gli elementi di
	$X$ e considerando un $(X,\E)\in \STS(v)$, abbiamo
	\eal{&\T{Presi due punti distinti }x,y\in X\;\;\exists ! \T{ retta
	}r\in \E\T{ tale che }x,y\in r
	}
\end{rem}
Adesso daremo alcune proposizioni ``distruttive'', che ci aiuteranno a capire
se un ipergrafo non e' un STS.

\begin{prop}
	\label{STSprop1}
	\eal{&(X,\E) \in \STS(v) \> |\E| = \frac{v(v-1)}{6}  
	}	
\end{prop}
\begin{proof}
	Ricordiamo che $\STS(v)=S(2,3,v)$, quindi per la prop \see{Shh+1prop1}
	abbiamo:
	\eal{&
	 |\E| = 
		\frac{v!}{(h+1)!(v-h)!} = 
		\frac{v!}{3!(v-2)!} = \frac{v(v-1)}{6}
	}
\end{proof}
\begin{prop}\label{STSprop2}
	\eal{&\H \in \STS(v) \> \H\T{ e' regolare di grado }\frac{v-1}{2}
	\> v\T{ dispari }
	}
\end{prop}
\begin{proof}
Sia $x\in X$. Usando la prop \see{Shh+1gradox} abbiamo:
\eal{&d(x) = \frac{(v-1)!}{h!(v-h)!} \ubrace{=}{h=2}  \frac{v-1}{2}
	}
\end{proof}
\begin{prop}\label{STSnecessaria}
	\eal{& \STS(v) \neq \0 \> v=1\;\;\Z_6 \| \;v=3\;\;\Z_6}
\end{prop}
\begin{proof}
	Sia $(X,\E)\in \STS(v)$,
	\eal{&d(x) \ubrace{=}{\see{STSprop2}} \frac{v-1}{2},\;d(x)\in \N  
	\> v-1 =0\;\;\Z_2 \= v=1 \;\;\Z_2\;\;(1)\NN
	\N \ni |\E|  \ubrace{=}{\see{STSprop1}} \frac{v(v-1)}{6} 
	\> v(v-1)=0\;\;\Z_6\;\;(2)}
	Risolviamo il sistema
	\eal{&\sist{v=1 \;\;\Z_2\\
	v(v-1)=0\;\;\Z_6}}
	utilizzando la prop \AI{sistemcongrm1divm2divmn}:
	\eal{&1.\;\;v=1\;\;\Z_2 \NN
	2.\;\;X_1:\;\;v=1,3,5\;\;\Z_6\NN
	3.\;\;X_2:\;\;v=1,3\;\;\Z_6
	}
\end{proof}
\subsection{Steiner Quadruple System}
\def\SQS{\oname{SQS}}
\def\STS{\oname{STS}}
\begin{defn}
	\eal{&\SQS(v)\definizione{=} S(3,4,v)}
\end{defn}
\begin{rem}
	Procederemo analogamente alle $\STS$, ma avremo una ulteriore
	condizione sul grado dei $2$-oggetti (negli $\STS$ il grado
	dei $2$-oggetti era banalmente $1$).
\end{rem}
\begin{prop}
	\label{SQSprop1}
	\eal{&(X,\E) \in \SQS(v) \> |\E| = \frac{v(v-1)(v-2)}{24}  
	}	
\end{prop}
\begin{proof}
	Ricordiamo che $\SQS(v)=S(3,4,v)$, quindi per la prop \see{Shh+1prop1}
	abbiamo:
	\eal{&
	 |\E| = 
		\frac{v!}{(h+1)!(v-h)!} = 
		\frac{v!}{4!(v-3)!} = \frac{v(v-1)(v-2)}{24}
	}
\end{proof}
\begin{prop}\label{SQSprop2}
	\eal{&\H \in \SQS(v) \> \H\T{ e' regolare di grado
	}\frac{(v-1)(v-2)}{6}
	}
\end{prop}
\begin{proof}
Sia $x\in X$. Usando la prop \see{Shh+1gradox} abbiamo:
\eal{&d(x) = \frac{(v-1)!}{h!(v-h)!} \ubrace{=}{h=3}  \frac{(v-1)(v-2)}{6}
	}
\end{proof}
\begin{prop}
	\label{SQSprop3}
	\eal{&\H=(X,\E) \in \SQS(v),\;C\in \P_2(X) \>d(C)=\frac{v-2}{2} 
	\> v\T{ pari}
	}
\end{prop}
\begin{proof}
	Usiamo la prop \see{propSgradoTh-1}
	\eal{&
	d(C)=\frac{v-h+1}{r-h+1} = \frac{v-3+1}{4-3+1} =\frac{v-2}{2}
	}
\end{proof}
\begin{prop}\label{SQSnecessaria}
	\eal{&\SQS(v)  \neq \0 \> v=2,4\;\;\Z_6
	}
\end{prop}
\begin{proof}
	Dalle prop \see{SQSprop1},\see{SQSprop2} abbiamo
	\eal{&\frac{v-2}{2},\;\frac{(v-1)(v-2)}{6}
	\in \N
	}
	Che equivale al sistema:
	\eal{&\sist{v=0\;\;\Z_2\;\;(1)\\
	(v-1)(v-2)=0\;\;\Z_6}}
	Risolviamolo utilizzando la prop \AI{sistemcongrm1divm2divmn}:
	\eal{&1.\;\;v=0\;\;\Z_2\NN
2.\;\;	X_1:\;\;v=0,2,4\;\;\Z_6\NN
3.\;\;X_2:\;\;v=2,4\;\;\Z_6
	}
\end{proof}
\subsection{Spettro}
\def\l{{\lambda}}
\begin{defn}
	Lo spettro di $S_\l(h,r,v)$ e' l'insieme
	\eal{&\pgra{v\in \N\;|\;S_\l(h,r,v) \neq \0}
	}
\end{defn}
\begin{thm}\label{thmspettri}
	Gli unici spettri attualmente conosciuti sono quelli di 
	$S(2,3,v),\;S(3,4,v),\;S(2,4,v)$, infatti valgono i seguenti teoremi:
	\eal{&
	S(2,3,v) \neq \0 \= v=1,3\;\;\Z_6,\;\;v\ge 3\NN
	S(3,4,v) \neq \0 \= v=2,4\;\;\Z_6,\;\;v\ge 4\NN
	S(2,4,v) \neq \0 \= v=1,4\;\;\Z_{12},\;\;v\ge 4
	}
	Per tutti gli altri spettri si conoscono solo condizioni del tipo
	$\>$.
\end{thm}
\begin{proof}
	\BEGINpnecessaria
	Nelle precedenti sezioni abbiamo provato la condizione
	$\>$ per le prime due. Analogamente si prova quella per $S(2,4,v)$.
	\END
	\BEGINsufficiente
		DA VERIFICARE!
	\END
\end{proof}
\subsection{$S_{l}(h,r,v)$}
\def\l{{\lambda}}
\begin{prop}\label{cardESlambdahrv}
	\eal{&\H=(X,\E)\in S_\lambda(h,r,v) \>
	|\E|=\lambda\frac{\binom{v}{h}}{\binom{r}{h}}
	= \lambda\frac{v!(r-h)!}{r!(v-h)!}
	}
\end{prop}
\begin{proof}
	Generalizziamo la prop \see{Shh+1prop1}.\\

Ogni oggetto $C\in \P_h(X)$ deve essere contenuto esattamente in $\l$ spigoli
. Ogni spigolo contiene $\binom{r}{h}$ oggetti. Quindi tutti
	gli oggetti distinti
	contenuti dagli spigoli sono
	in numero $\frac{\binom{r}{h}|\E|}{\lambda}$.\\
	Tutti gli oggetti contenuti dagli spigoli sono
	tutti gli oggetti possibili.
	In altri termini,
	\eal{&\sum_{E\in \E} |\P_h(E)| = \sum_{Y\in \P_h(X)} d(Y) = d(Y)|\P_h(X)| =\lambda
	\binom{v}{h}\NN
	\sum_{E\in\E} |\P_h(E)| =\sum_{E\in \E} \binom{r}{h} =  \binom{r}{h} |\E| \NN
	\qq \>  |\E| =\lambda\frac{ \binom{v}{h}}{\binom{r}{h}}
	}
In termini formali:
\eal{&(X,\E) \in S_{\lambda}(h,r,v) \> \forall C\in \P_h(X)\;\;d(C)=\lambda \= \forall
	C\in \P_h(X)\;\;\exists S_1,\dots,S_\l\in \E\T{ distinti t.c.
	}C\(S_i\;\;\forall i=1,\dots,\l \;\;\;(1)\NN
	(X,\E) \T{ uniforme di rango } r \> |E| =r\;\forall E\in \E \>
	|\P_h(E)|=\binom{r}{h}\;\;\forall E\in \E\;\;(2)}
	Nominiamo gli spigoli e gli oggetti:
	\eal{&\T{Sia }\E=\pgra{E_1,\dots,E_k}\NN
	\T{Sia }	\P_h(E_{i})=\pgra{C_{i1},\dots,C_{it}}\NN
	t \ubrace{=}{(2)} \binom{r}{h}\NN
	\pass{	\pgra{(i,j)\;|\;\exists E\in \E:\;C_{ij} \in \P_h(E) }}
	=\pass{\pgra{(i,j)\;|\;
	\;|\;1\le i\le k,\;1\le j\le t}}=kt=|\E| \binom{r}{h}\;\;(3) \NN
	\pass{\pgra{(i,j)\;|\;\exists E\in \E:\;C_{ij} \in \P_h(E) }}
	\ubrace{=}{(1)}\pass{ \bigcup_{C\in \P_h(X)}
	\pgra{(i,j)\;|\;C_{ij}=C}}
	= \sum_{C\in \P_h(X)}\pass{\pgra{(i,j)\;|\;C_{ij}=C}}=\NN
	=\sum_{C\in \P_h(X)} d(C)  \ubrace{=}{(1)}  \sum_{C\in \P_h(X)}
	\lambda  = \lambda |\P_h(X)| = \lambda \binom{v}{h} \;\;(4)\NN
	(3),(4) \> |\E| \binom{r}{h} =  \lambda \binom{v}{h} \=  |\E|= \lambda\frac{\binom{v}{h}}{
        \binom{r}{h}}
	}
\end{proof}
\begin{prop}	\label{propderivatolambda}
	Sia $x\in X$. Si ha
	\eal{&\H=(X,\E) \in S_\l(h,r,v) \> \H_x'=(X\-\pgra{x}, \E_x')\in
	S_\l(h-1,r-1,v-1)
	}
Dove 	$\H_x'$ e' l'ipergrafo derivato di $\H$ secondo $x$.
\end{prop}
\def\l{{\lambda}}
\begin{proof}
	Anche qui generalizziamo quello che abbiamo fatto in
	\see{propderivato}.\\
Sia $Y\in \P_{h-1}(X\-\pgra{x})$.
Se per assurdo $d_x'(Y) >\l$, si avrebbe:
\eal{&d_x'(Y) >\l \> \exists C_1,C_2,\dots,C_{\l+1}\in \E_x'\;\T{ distinti
t.c. }Y\( \bigcap_{i=1}^{\l+1}C_i
\> Y\U\pgra{x}\( \bigcap_{i=1}^{\l+1} (C_i\U\pgra{x})
\> 
d(Y\U\pgra{x}) > \l
}
ma questo e' assurdo contro $d(Z)=\l\;\;\forall Z\in \P_h(X)$.\\
Infine,  $d_x'(Y) \ge \l$, infatti,
\eal{&d(Y\U\pgra{x})=\l \> \exists E_1,E_2,\dots,E_{\l}\in \E\T{ distinti
t.c. }Y\U\pgra{x}\( \bigcap_{i=1}^{\l}E_i
\ubrace{\>}{x\notin Y}  Y \(  \bigcap_{i=1}^{\l}E_i\-\pgra{x}\NN
i \neq j\>E_i \neq E_j \> E_i\-\pgra{x} \neq E_j\-\pgra{x}
}
Quindi gli $E_i\-\pgra{x}$ sono $\l$ spigoli distinti di $\E_x'$ che
contengono $Y$, percio' $d_x'(Y)\ge \l$.
\eal{&\l\le d_x'(Y) \le \l \>d_x'(Y) =\l}
\end{proof}
\begin{prop}
		\label{Slambdahrgradox}
		Sia $\H=(X,\E) \in S_\l(h,r,v) $, allora
	\eal{& \H \T{ e' regolare di grado  }
\lambda\frac{\binom{v-1}{h-1}}{\binom{r-1}{h-1}}
= \lambda\frac{(v-1)!(r-h)!}{(r-1)!(v-h)!} 
	}
	ovvero
	\eal{&d(x)=|\E_x|=\lambda\frac{(v-1)!(r-h)!}{(r-1)!(v-h)!}\;\;\forall
	x\in V}
\end{prop}
\begin{proof}
	Fissiamo  $x\in X$ e sia $\H_x'$ il derivato di $\H$. Per la prop
	\see{propderivatolambda}
	 si ha
	 \eal{&\H_x'\in S_\l(h-1,r-1,v-1) \;\;(1)\NN
	 d(x)=|\E_x|  \ubrace{=}{\see{cardESlambdahrv}} 
\lambda\frac{\binom{v-1}{h-1}}{\binom{r-1}{h-1}}
= \lambda\frac{(v-1)!(r-1-(h-1))!}{(r-1)!(v-1-(h-1))!} 
= \lambda\frac{(v-1)!(r-h)!}{(r-1)!(v-h)!} 
	 }
\end{proof}
\begin{prop}
	\eal{&1.\;\;\H=(X,\E)\in S_2(2,3,v) \>
	|\E|=
	 \frac{v(v-1)}{3} 
	\NN
	2.\;\;S_2(2,3,v) \neq 0\> v=0,1\;\;\Z_3\NN
	3.\;\;d(x)=v-1
	}
\end{prop}
\begin{proof}
	Basta applicare la \see{cardESlambdahrv}.
	Per la $2.$:
	\eal{&\frac{v(v-1)}{3} = |\E|\in \N \> v(v-1)=0\;\;\Z_3
	\ubrace{\=}{3\T{ e' primo, $\Z_3$ e' un campo, quindi vale la legge dell'annullamento del
	prodotto }} \NN
	\=v=0\;\;\Z_3  \;\| \;v=1\;\;\Z_3
	}
	Per la $3.$, usando la \see{Slambdahrgradox} si ha
	\eal{&d(x)
= 2\frac{(v-1)!}{2!(v-2)!} 
= \frac{(v-1)!}{(v-2)!} = v-1
	}
\end{proof}
\subsection{Costruzioni}
Vediamo adesso come possiamo combinare sistemi di steiner per formarne altri
di ordine superiore (con qualche parametro piu' alto).
\begin{prop}
	\eal{&\sist{\H_1=(X,\E_1),\H_2=(X,\E_2)\in S_{\l}(h,r,v)\\
	\E_1\^\E_2=\0}
	\> (X,\E_1\U\E_2)\in S_{2\l}(h,r,v)
	}
\end{prop}
\begin{proof}
Chiaramente $\H=(X,\E_1\U\E_2)$ e' un ipergrafo uniforme di rango $r$ ed ha
$v$ vertici. Verifichiamo che
\eal{&\forall Y \in \P_h(X)\;\;d(Y)=2\l}
Allora,
\eal{&
Y\in \P_h(X),\;\H_i\in S_\l(h,r,v) \> \pass{\pgra{E_i\in\E_i\;|\;Y\(E_i}} =
\l\;\;\forall i=1,2\NN
2\l=\pass{\pgra{E_1\in\E_1\;|\;Y\(E_1}}
+\pass{\pgra{E_2\in\E_2\;|\;Y\(E_2}}
\ubrace{=}{
\E_1\^\E_2=\0  
}  \pass{\pgra{E\in \E_1\U\E_2\;|\;Y\(E}} =d(Y)
}
\end{proof}
\begin{thm} di Lindner-Rosa.\\
	\eal{&v=1,3\;\;\Z_6,\;\;v\ge 7 \> \exists \H_1,\H_2\in \STS(v):\;\;\E_1\^\E_2=\0}
	DA VERIFICARE!
\end{thm}

\begin{prop}\label{costruzione2v1}
	Costruzione di un $\STS(2v+1)$ a partire da un $\STS(v)$.\\

Nota\footnote{Per una costruzione piu' generale, vedi \see{costruzioner1v1}}.
Sia $\H=(X,\E)\in\STS(v)$ il sistema di partenza.
Sia $\H'=(X',\E')$ l'STS che dobbiamo costruire.\\
	Poniamo $X\(X'$, $|X'|=2v+1$ e 
	\eal{&
	Y\definizione{=} X'\-X\NN
\T{Sia }\pgra{C_{i}}_{i=1}^{v} \T{ una 1-fattorizzazione
	del grafo completo }(Y,\P_2(Y))
	}
	Numeriamo $X$:  $X=\pgra{x_1,\dots,x_v}$.\\
	Numeriamo $C_i$: $C_i=\pgra{C_{i1},C_{i2},\dots,C_{it}}$, 
	dove $t=\frac{v}{2},\;C_{ij}\(Y,\;|C_{ij}|=2$.\\
	Numeriamo $C_{ij}$: $C_{ij}=\pgra{C_{ij1},C_{ij2}}$, dove
	$C_{ijk}\in Y$.\\
	Preso $C_{ij}$, costruiamo il seguente $3$-oggetto:
	\eal{&E_{ij}\definizione{=}\pgra{x_i,C_{ij1},C_{ij2}}
	}
	Poniamo
	\eal{&\E'=\E\U\pgra{E_{ij}\;|\;i=1,\dots,v,\;j=1,\dots,t}
	}
	Si ha che $\H'=(X',\E')\in \STS(2v+1)$
\end{prop}
\begin{proof}
	Sia $\H=(X,\E)\in\STS(v)$. Per il thm \see{thmspettri} si deve avere
	\eal{&v=1,3\;\;\Z_6,\;\;v\ge 3
	}
	anche $2v+1$ rispetta questa condizione, infatti,
	\eal{&v=1\;\;\Z_6 \> 2v+1=3\;\;\Z_6\NN
	v=3\;\;\Z_6\> 2v+1=7=1\;\;\Z_6
	}
	Inoltre,
	\eal{&\H\in \STS(v)  \ubrace{\>}{\see{STSprop2}}v\T{ dispari } }
	Sia $\H'=(X',\E')$ l'STS che dobbiamo costruire.\\
	Poniamo $X\(X'$, e $|X'|=2v+1$, quindi:
	\eal{&|X'|=2v+1\NN
	Y\definizione{=} X'\-X\NN
	|Y|=2v+1-v = v+1\NN
	v\T{ dispari } \> v+1 \T{ pari}
	\ubrace{\>}{\T{ thm \see{thmesistefattorizzazione} }} 
	\exists \pgra{C_{i}}_{i=1}^{v} \T{ 1-fattorizzazione
	del grafo completo }(Y,\P_2(Y))\;\;(1)
	}
	Numeriamo $X$:  $X=\pgra{x_1,\dots,x_v}$.\\
	Numeriamo $C_i$: $C_i=\pgra{C_{i1},C_{i2},\dots,C_{it}}$, 
	dove $t=\frac{v}{2},\;C_{ij}\(Y,\;|C_{ij}|=2$ (\vedi{prop1fatt}).\\
	Numeriamo $C_{ij}$: $C_{ij}=\pgra{C_{ij1},C_{ij2}}$, dove
	$C_{ijk}\in Y$.\\
	Preso $C_{ij}$, costruiamo il seguente $3$-oggetto:
	\eal{&E_{ij}\definizione{=}\pgra{x_i,C_{ij1},C_{ij2}}
	}
	Poniamo
	\eal{&\E'=\E\U\pgra{E_{ij}\;|\;i=1,\dots,v,\;j=1,\dots,t}
	}
	Notiamo che
	\eal{&E_{ij}\notin \E\;\;\forall i,j\;\;(2)
	}
	Infatti,
	\eal{&C_{ij}\( Y,\;\;Y\^X=\0\> E_{ij}=\pgra{x_i,C_{ij1},C_{ij2}}
\notin \E\(\P_3(X)
	}
	\step{}{Dimostriamo che $\H'=(X',\E')\in \STS(2v+1)$}
	\begin{prova}
	Per costruzione $|X'|=2v+1$.\\
	$\H'$ e'  un ipergrafo uniforme di rango $3$, perche' 
	\eal{&\forall E\in \E\;\;|E|=3\NN
	\forall E_{ij}\;\;|E_{ij}|=3
	}
	Resta da provare che
	\eal{&\forall Y\in \P_2(X')\;\;d'(Y)=1
	}
	dove $d'$ e' il grado in $\H'$.\\
	Sia $T=\pgra{x,y}$. I casi sono tre, e sono disgiunti perche'
	$X\^Y=\0$.
	\case{$x,y\in X$}
	\begin{prova}
		\eal{&\pgra{x,y}\in \P_2(X) \> 
		d(\pgra{x,y})=1\= \exists ! E\in \E:\;\pgra{x,y}\(E\NN
		}		
		Se per assurdo:
		\eal{&
		\exists E_{ij}:\;\pgra{x,y} \( E_{ij}=
		\pgra{x_i,C_{ij1},C_{ij2}} 
		\> \pgra{x,y}\^\pgra{C_{ij1},C_{ij2}} \neq \0\;\;(3)
		}
		La $(3)$ e' in assurdo con 
		\eal{&\sist{{x,y}\( X\\
		C_{ij1},C_{ij2} \in Y\\
		Y\^X=\0
		}
		}
		In conclusione, non ci sono spigoli $E_{ij}$ per $T$, e ne
		esiste solo uno in $\E$, quindi
		\eal{&d'(Y)=1}
	\end{prova}
	\case{$x,y\in Y$}
	\begin{prova}
		\eal{&\pgra{C_i}_{i=1}^{v}\T{ e' una partizione di } \P_2(Y)
		\ubrace{\>}{\pgra{x,y}\in \P_2(Y)} 
		\exists !i:\;\;\pgra{x,y} \in
		C_i=\pgra{C_{i1},\dots,C_{it}} \> 
		\exists!j:\;C_{ij}=\pgra{x,y}
		}
		Abbiamo quindi,
		\eal{&\exists !E_{ij}:\;\;E_{ij}=\pgra{x_i,x,y}}
		$E_{ij}$ e' anche l'unico $3$-oggetto di $\E'$ che contiene
		$\pgra{x,y}$, infatti, come abbiamo visto prima:
		\eal{&
		x,y\in Y \>  E_{ij} \notin \E}
	\end{prova}
	\case{$x\in X,\;y\in Y$}
	\begin{prova}
		Poiche' $y\in Y$, non puo' esistere un $E\in
		\E:\;\pgra{x,y}\(E$. Quindi resta da cercare in
		$\pgra{E_{ij}}$.\\
		\eal{&x\in X \> \exists !i:\;x=x_i
		\ubrace{\>}{\T{per costruzione}} 
		x_i\in E_{ih}\;\;\forall h
		}
		Notiamo che
		\eal{&C_{i}=\pgra{C_{i1},\dots,C_{it}}\T{ partizione di }Y \> 
		\exists !j:\;y\in C_{ij}
		}
		Quindi
		\eal{&E_{ij}=\pgra{x_i,y,C_{ijk}}}
		Abbiamo cosi' determinato l'unico $3$-oggetto contenente
		$x,y$.
	\end{prova}
	\end{prova}
\end{proof}
\begin{exemp}
	Consideriamo il sistema $\STS(3)$
	\eal{&X=\pgra{1,2,3}\NN
	\E=\pgra{\pgra{1,2,3}}
	}
	E da questo costruiamo un $\STS(7)$.\\
	$|X'|=7$, quindi ci servono gli elementi $Y=\pgra{4,5,6,7}$,
	$|Y|=4$.\\
	Una $1$-fattorizzazione di $Y$ e':
	\begin{center}
	\begin{tabular}[h]{c|c|c}
		4 5 & 4 6 & 4 7 \\  
		6 7 & 5 7 & 5 6
	\end{tabular}
	\end{center}
	e da questa formiamo le nuove terne:
	\eal{&
	\pgra{1,4,5}, \pgra{1,6,7}\NN
	\pgra{2,4,6}, \pgra{2,5,7}\NN
	\pgra{3,4,7}, \pgra{3,5,6}
	}
	Infine abbiamo:
	\eal{&\E'=\E\U \pgra{\T{nuove terne}}:\;\;\NN
	\qq\qq\pgra{1,2,3}\NN
\qq\qq	\pgra{1,4,5}, \pgra{1,6,7}\NN
\qq\qq	\pgra{2,4,6}, \pgra{2,5,7}\NN
\qq\qq	\pgra{3,4,7}, \pgra{3,5,6}
		}
\end{exemp}
\def\s{{\sigma}}
\begin{prop}\label{costruzionev3v}
	Costruzione di un $\STS(3v)$ a partire da un $\STS(v)$.\\
Sia $\H=(X,\E)\in\STS(v)$ il sistema di partenza.
%Siano $\H_i=(X,\E_i)\in\STS(v)\;\;\forall i=1,\dots,4$ i sistemi di partenza,
%con $\E_i\^\E_j=\0\;\;\forall i \neq j$.\\
Poniamo
\eal{&X'=\bigcup_{i=1,2,3}X\*\pgra{i}
}
Sia $\E'$ l'insieme composto dall'unione dei seguenti tre insiemi:
\eal{&R=\bigcup_{i=1,2,3} \pgra{\pgra{(x,i),\;(y,i),\;(z,i)}\;|\;\pgra{x,y,z}\in\E}\NN
C=\pgra{\pgra{(x,1),\;(x,2),\;(x,3)}\;|\;x\in X}\NN
D=\pgra{\pgra{(x,{\s(1)}),\;(y,{\s(2)}),\;(z,{\s(3)})}\;|\;\pgra{x,y,z}\in
\E,\;\;\s\T{ permutazione di }\pgra{1,2,3} }
}
ovvero, $\E'=R\U C \U D$.\\
Allora,
\eal{&(X',\E')\in \STS(3v)}
\end{prop}
\begin{proof}
	Possiamo visualizzare $X'$ cosi':
		\begin{center}
			\includegraphics[scale=0.5]{fig/out1}
		\end{center}
	$R$ e' quindi l'insieme delle terne prese da ogni riga.\\
	$C$ e' l'insieme delle colonne, ad esempio contiene la colonna
	$(x,1),(x,2),(x,3)$.\\
	Chiaramente $|X'|=3v$ e inoltre, $(X',\E')$ e' un ipergrafo uniforme
	di rango $3$.
	\step{p0}{$\STS(3v) \neq \0$}
	\begin{prova}
		\eal{&\H \in \STS(v)  \ubrace{\>}{\see{thmspettri} }
		v=1,3\;\;\Z_6\NN
		v=1 \;\;\Z_6 \> 3v=3\;\;\Z_6  \ubrace{\>}{\see{thmspettri}} \STS(3v) \neq 0\NN
		v=3 \;\;\Z_6 \> 3v=9=3\;\;\Z_6 \ubrace{\>}{\see{thmspettri}} \STS(3v) \neq 0	}
	\end{prova}
	\step{p1}{Dimostriamo che $\forall Y\in \P_2(X')\;\;d'(Y)=1$}
	\begin{prova}
		Sia $Y=\pgra{(x,i),\;(y,j)}$, con $i,j\le 3$.
		\eal{&Y\in \P_2(X') \> (x,i) \neq (y,j)}
		\case{$i=j,\;x \neq y$ }
		\begin{prova}
			In questo caso ci troviamo nella riga $i$ e per
			costruzione di $R$ riusciamo a trovare una terna
			opportuna:
			\eal{&x,y\in X \> \exists ! \pgra{a,b,c}\in \E:\;\;
			x,y\in \pgra{a,b,c}
			\> (x,i),\;(y,i)\in\pgra{(a,i),\;(b,i),\;(c,i)}\in R\(
			\E'
			}
		\end{prova}
		\case{$i \neq j,\;x=y$}
		\begin{prova}
			In questo caso ci troviamo in una colonna, quindi
			usiamo $C$:
			\eal{&(x,i),\;(x,j)\in \pgra{(x,i),\;(x,j),\;(x,h)}\in
			C\( \E'
			}
		\end{prova}
		\case{$i \neq j,\;x \neq y$}
		\begin{prova}
		Adesso sfruttiamo $D$.
			\eal{&x,y\in X \> \exists ! \pgra{a,b,c}\in \E:\;\;
			x,y\in \pgra{a,b,c}}
			Supponiamo ad esempio che $a=x,\;y=b$, allora
			\eal{&
			i \neq j,\;1\le i,j\le 3 \> \exists !\s\T{
			permutazione di }\pgra{1,2,3}\T{ t.c. }
			\s(1)=i,\;\s(2)=j\>\NN
\>
			(x,i),\;(y,j)\in\pgra{(a,\s(1)),\;(b,\s(2)),\;(c,\s(3))}\in D
			}
		\end{prova}
\qq\\
		In ognuno dei tre casi, notiamo il $3$-oggetto contenente $Y$ e'
		unico. Alternativamente, si puo' verificare che la seguente
		espressione
		\eal{&|\E'| = |R|+|C|+|D| = 3|\E|+|X|+|\E|6 
		=9|\E|+v
		\ubrace{=}{
		\see{STSprop1}} 9\frac{v(v-1)}{6}+v=\frac{9v^2-9v+6v}{6}=
		\frac{3v(3v-1)}{6} 
		}
		e' proprio quella data dalla prop { \see{STSprop1}} per un
		$\STS(3v)$, quindi applicando il lemma \see{lemmaconteggio} la tesi e' acquisita.
	\end{prova}
%	\step{}{Dim.
%	$\forall Y\in \P_2(X')\;\;d'(Y)= 1$}
%	\begin{prova}
%		\pfsketch{
%		In questa dimostrazione utilizzeremo una tecnica generale:
%		contiamo tutti gli spigoli che abbiamo incluso in $\E'$,
%		considerando anche possibili ripetizioni. Se il contaggio da'
%		esattamente 
%		\eal{&|\E''|
%		\ubrace{=}{\see{STSprop1}}\frac{3v(3v-1)}{6}\;\;(1)
%		}
%		dove $(X,\E'')\in \STS(3v)$ e' un qualsiasi $\STS(3v)$,
%		allora, grazie al passo \sref{p1}, siamo sicuri che $d'(Y)=1$,
%		ovvero che non ci possono essere ``spigoli in piu' ''. \\
%		Nota: $(X,\E'')$ esiste per il \sref{p0}
%		}
%
%		Procediamo:
%\eal{&R,C,D\T{ sono disgiunti: }\;\;(2)\NN
%\qq \T{gli elementi di R sono del tipo
%}\pgra{(x,i),\;(y,i),\;(z,i)},\;\;x,y,z\T{ distinti}\;\;(2.1)\NN
%\qq \T{gli elementi di C sono del tipo }\pgra{(x,1),\;(x,2),\;(x,3)}\;\;(2.2)\NN
%\qq \qq \> \T{ due elementi di R,C differiscono almeno in due vertici e due indici }\NN
%\qq \T{gli elementi di D sono del tipo
%}\pgra{(x,\s(1)),\;(y,\s(2)),\;(z,\s(3))}\;\;(2.3)\NN
%\qq \qq \> \T{ due elementi di R,D differiscono almeno in due indici }\NN
%\qq \qq \> \T{ due elementi di C,D differiscono almeno in due vertici e due indici }\NN
% \qq \> R\^C=\0,\;D\^C=\0,\;\;R\^D=\0\NN
%|R|=
%\pass{\bigcup_{i=1,2,3} \pgra{\pgra{(x,i),\;(y,i),\;(z,i)}\;|\;\pgra{x,y,z}\in\E}} =\NN 
%%\ubrace{=}{\E_i\^\E_j=\0\;\;\forall i \neq j} 
%=
%\sum_{i=1,2,3} \pass{\pgra{\pgra{(x,i),\;(y,i),\;(z,i)}\;|\;\pgra{x,y,z}\in\E}}
% = \sum_{i=1,2,3} |\E| \ubrace{=}{\see{STSprop1}} 
%\sum_{i=1,2,3} \frac{v(v-1)}{6} =  \frac{v(v-1)}{2}\NN
%|C|=\pass{\pgra{\pgra{(x,1),\;(x,2),\;(x,3)}\;|\;x\in X}}=
%|X|=v\NN
%|D|=\pass{\pgra{\pgra{(x,{\s(1)}),\;(y,{\s(2)}),\;(z,{\s(3)})}\;|\;\pgra{x,y,z}\in
%\E,\;\;\s\T{ permutazione di }\pgra{1,2,3} }}=\NN
%= |\E\*\pgra{\s\T{ permutazione di }\pgra{1,2,3}}|
%=6|\E|\ubrace{=}{\see{STSprop1}} v(v-1)\NN
%|\E'|  =|R\U C\U D|=\ubrace{=}{R,C,D\T{ sono disgiunti}} |R|+|C|+|D|= \frac{v(v-1)}{2} +v + v(v-1) =
%\frac{3v(v-1)+2v}{2}=\NN
%=
%\frac{v(3(v-1)+2))}{2}=
%\frac{v(3v-1)}{2}=
%\frac{3v(3v-1)}{6}=|\E''|
%}
%Consideriamo la seguente mappa:
%\eal{&f:\E'\longrightarrow \E''\\
%f(E)
%}
%	\end{prova}
\end{proof}
\begin{exemp}
	Vedi \see{expsts9}.
\end{exemp}
\subsection{Kirkman}
\def\l{{\lambda}}
\begin{defn}
	Sia $\H=(X,\E)\in S_{\l}(h,r,v)$, $E_1,E_2\in \E$.
	\eal{&E_1\parallel E_2\definizione{\=} E_1\^E_2=\0}
	$E_1,E_2$ si diranno paralleli.\\
	\eal{&C\(\P(\E)\T{ e' una classe di parallelismo di }\H\definizione{\=}
	C\T{ e' una partizione di }X
	}
	Infine,
	\eal{&\H\T{ e' di Kirkman (o risolubile) }\definizione{\=}
	\exists \pi\T{ partizione di }\E:\;\;\forall C\in \pi\;\; C\T{ e'
	una classe di parallelismo di }\H}
	$\pi$ verra' chiamata \iemph{risoluzione} di $\H$.
\end{defn}
\begin{exemp}\label{expsts9}
Il seguente	$\STS(9)$ e' risolubile:
	\begin{center}
	\begin{tabular}[h]{c|c|c|c}
		123 & 147 & 159& 168\\
		456 & 258 & 267& 249\\
		789 & 369 & 348& 357
	\end{tabular}
	\end{center}
	Nota: abbiamo costruito questo $\STS(9)$ utilizzando la costruzione
	\see{costruzionev3v}, partendo dall'$\STS(3)$
	$X=\pgra{1,2,3},\E=\pqua{\pgra{1,2,3}}$ e ponendo
	\eal{&
	1\leftrightarrow (1,1),\;2\leftrightarrow (2,1),\;3\leftrightarrow(3,1)\NN
	4\leftrightarrow(1,2),\;5\leftrightarrow(2,2),\;6\leftrightarrow(3,2)\NN
	7\leftrightarrow(1,3),\;8\leftrightarrow(2,3),\;9\leftrightarrow(3,3)
	}
\end{exemp}
\begin{prop}\label{KcardC}
	Sia $ \H=(X,\E)\in S_\l(h,r,v)\T{ risolubile }$ e sia $\pi$  una
	qualsiasi partizione di $\E$ che risolve $\H$. Sia $C\in \pi$. Allora
	\eal{&	
	|C| = \frac{v}{r}
	}
\end{prop}
\begin{proof}
		\eal{&\H \T{ risolubile } \>
	\exists \pi\T{ partizione di }\E:\;\;\forall C\in \pi\;\; C\T{ e' una
	partizione di }X\NN
	C\T{ partizione  di X} \> 
	\bigcup_{c\in C}c=X \> v=|X|=\pass{ \bigcup_{c\in C}c}
	\ubrace{=}{C\T{ partizione }} \sum_{c\in C}|c|  =\NN
	\ubrace{=}{
	c\in C\in\pi\(\P(\E)}  \sum_{c\in C}r = |C|r
	}
\end{proof}
\begin{prop}\label{Krdivv}
	\eal{&
		\H=(X,\E)\in S_\l(h,r,v)\T{ risolubile } \> r \div v 
	}
\end{prop}
\begin{proof}
	Dalla prop \see{KcardC}, 
	\eal{&
		|C|  = \frac{v}{r} \in \mathbb{N} \> r \div v
	}
\end{proof}
\begin{prop}\label{cardinalitapirisoluzione}
	\eal{&\H=(X,\E)\in S_\l(h,r,v)\T{ risolubile } \> |\pi| = 
	\lambda\frac{\binom{v-1}{h-1}}{\binom{r-1}{h-1}}
	=  \lambda\frac{(v-1)!(r-h)!}{(r-1)!(v-h)!}
	}
	dove $\pi$ e' una qualsiasi partizione di $\E$ che risolve $\H$.
\end{prop}
\begin{proof}
	\eal{&\bigcup_{C\in \pi} C = \E  \ubrace{\>}{{\pi\T{ partizione di
	}\E}}  |\E| = \sum_{C\in \pi} |C|
	\ubrace{=}{\see{KcardC}}  \sum_{C\in \pi} \frac{v}{r} = 
	 \frac{v}{r} |\pi|
	 \> |\pi| = |\E|\frac{r}{v}  =\NN
	 \ubrace{=}{\see{cardESlambdahrv}} 
	\lambda\frac{\binom{v}{h}}{\binom{r}{h}}\frac{r}{v} 
	= \lambda\frac{v!(r-h)!}{r!(v-h)!}\frac{r}{v} 
	=  \lambda\frac{(v-1)!(r-h)!}{(r-1)!(v-h)!} =
	\lambda\frac{\binom{v-1}{h-1}}{\binom{r-1}{h-1}}
	}
\end{proof}
\begin{prop}\label{dxeqpieqEx}
	\eal{&\H=(X,\E)\in S_\l(h,r,v)\T{ risolubile } \> |\pi| = 
	|d(x)|  = |\E_x|\;\;\;\forall x\in X
	}
	dove $\pi$ e' una qualsiasi partizione di $\E$ che risolve $\H$.
\end{prop}
\begin{proof}
	Basta confrontare la \see{cardinalitapirisoluzione}
	 con la \see{Slambdahrgradox}.
\end{proof}
\subsubsection{KTS}
\def\KTS{{\oname{KTS}}}
\begin{defn}
	Poniamo
	\eal{&\KTS(v)=\pgra{\H\in \STS(v)\;|\;\H\T{ e' risolubile }}
	}
\end{defn}
\begin{thm}
	\eal{&\KTS(v) \neq \0 \= v=3\;\;\Z_6
	}	
\end{thm}
\begin{proof}
	Dimostriamo solo la condizione necessaria.
	\BEGINpnecessaria
	\eal{&\H \in \KTS(v)   \ubrace{\>}{\see{Krdivv}} r\div v
	\ubrace{\=}{\KTS(v)\( \STS(v)} 3\div v \= v=0\;\;\Z_3\;\;(1)\NN
	\H \in \STS(v)  \ubrace{\>}{\see{thmspettri}}  
	v = 1,3\;\;\Z_6  \NN
	\sist{v=0\;\;\Z_3\\
	v=1,3\;\;\Z_6 
	}  \ubrace{\>}{\AI{sistemcongrm1divm2divmn}} v=3\;\;\Z_6
	}
	\eal{&3k=1\;\;\Z_6 \= 3k=1+6j \= 3(k-2j)=1 \> 3\div 1\T{ assurdo }
	}
	Quindi l'unico caso valido e' 
	\eal{&v=3\;\;\Z_6
	}
	\END
	\BEGINsufficiente
	DA VERIFICARE!
	\END
\end{proof}
\begin{prop}
	Una $1$-fattorizzazione di $(X,\P_2(X))\in \K_n$ e' equivalente ad una
	risoluzione di $S(2,2,|X|)$, infatti,
	\eal{&S(2,2,v)=\K_v}
\end{prop}
\subsection{Altre costruzioni}
\def\b{{\beta}}
\def\B{{\mathcal{B}}}
\begin{lem}\label{lemmaconteggio}
Sia $\H=(X,\E)\in S(h,r,v)$, e sia $\B\(\P_r(X)$ tale che 
\eal{&\forall Y \in \P_h(X) \;\;\exists\;\;\b\in \B:\;\;Y\(\b
}
allora
\eal{&|\B|=|\E| \> (X,\B)\in S(h,r,v)
}
\end{lem}
\begin{proof}
	Basta  dimostrare l'unicita', cioe':
	\eal{&\forall Y \in \P_h(X) \;\;\exists!\;\b\in \B:\;\;Y\(\b\;\;(1)
	}
Supponiamo per assurdo che la $(1)$ sia falsa. Poiche' l'esistenza e'
garantita per Hp, si ha
\eal{&\exists Y \in \P_h(X):\;\;|\pgra{\b\in \B\;|\;Y\( \b}| >1\;\;(2)
}
e inoltre, sempre per l'esistenza, si ha
\eal{& \P_h(X) = \bigcup_{\b\in \B}\P_h(\b)\;\;(3)\NN
\T{Tuttavia, per la $(2)$ si ha che }  \pgra{\P_h(\b)\;|\;\b\in \B}\T{ non e'
una partizione } \;\;(3.1)\NN
|P_h(X)|  \ubrace{=}{(3)} \pass{\bigcup_{\b\in \B}\P_h(\b)}
\ubrace{<}{(3.1)} \sum_{\b\in \B}|\P_h(\b)|  = |\B|c\T{ dove
}c=|\P_h(\b)|\;\;\forall \b\in \B\NN
|P_h(X)|  < |\B|c  \ubrace{=}{\T{per Hp}} |\E|c\;\;(3.2)
}
Poiche' $\H\in S(h,r,v)$, come gia' visto altre volte (\vedi{Shh+1prop1}), abbiamo che
\eal{&\pgra{\P_h(E) \;|\;E\in \E}\T{ e' una partizione di } \P_h(X)\;\;(4)\NN
|\P_h(X)|  \ubrace{=}{(4)} \pass{\bigcup_{E\in \E}\P_h(E)} \ubrace{=}{(4)} 
\sum_{E\in \E}|\P_h(E)|  \ubrace{=}{|E|=|\b|}  \sum_{E\in \E} c = 
c|\E|  \ubrace{>}{(3.2)}   |P_h(X)| \NN
\qq \> |\P_h(X)|  >  |P_h(X)|\NN
\T{ assurdo}
}
\end{proof}
\begin{prop}\label{costruzioner1v1}
	Costruzione di un $S(2,r,(r-1)v+1)$ a partire da un $S(2,r,v)$ e
	da un $S(2,r-1,(r-2)v+1)$ \uline{risolubile}.\\

Sia $\H=(X,\E)\in S(2,r,v)$ il sistema di partenza.
Sia $\H'=(X',\E')$ il sistema che dobbiamo costruire.\\
Sia $\pi=\pgra{C_{i}}_{i=1}^{|\pi|}$ una risoluzione di
un $(Y,\E_Y)\in S(2,r-1,(r-2)v+1)$, con $Y\^X =\0$\\

	Numeriamo $X$:  $X=\pgra{x_1,\dots,x_v}$.\\
	Poiche' si ha $|\pi|=v$, per ogni $x\in X$, possiamo porre la seguente
	biezione:
	\eal{&C_{\cdot}:X\longrightarrow \pi\NN
	C_x = C_i\;\;\;\T{ dove }x_i=x
	}
	Numeriamo $C_x$: $C_x=\pgra{C_{x1},C_{x2},\dots,C_{xt}}$.\\
	Costruiamo il seguente $r$-oggetto:
	\eal{&E_{xj}\definizione{=}\pgra{x} \U C_{xj} }
	Poniamo
	\eal{&\E'=\E\U \pgra{E_{xj}\;|\;x\in X,\;\;j=1,\dots,t}\NN
	X'=X\U Y
	}
	Si ha che $\H'=(X',\E')\in S(2,r,(r-1)v+1)$
\end{prop}
\begin{proof}
	\pfsketch{
Questa proposizione e' semplicemente una generalizzazione della prop
\see{costruzione2v1}. Infatti, stiamo considerando  tutte le classi di
parallelismo che formano $\pi$ e stiamo completando ogni suo elemento
aggiungendo al suo interno il
relativo elemento di $X$,  ovvero otteniamo un $E_{ij}$.

\step{}{Analizziamo l'idea di fondo di questa costruzione}
\begin{prova}
	Supponiamo di avere un $\H=(X,\E) \in S(2,r,v)$ e un $(Y,\E_Y)\in S(2,r-1,w)$
	risolubile. Possiamo costruire a partire da questi un sistema piu'
	grande?\\
	Poiche' $(Y,\E_Y)$ e' risolubile, possiamo considerare una partizione
	$\pi$ che lo risolve.\\
	A questo punto, il trucco consiste nell'associare ogni elemento $x\in
	X$ ad una classe $C\in \E_Y$: prendiamo tutti gli $(r-1)$-oggetti della 
	classe $C$ e li estendiamo aggiungendoci l'elemento $x$. Otteniamo
	cosi' degli $r$-oggetti.\\
	Affinche' questa associazione sia possibile, il numero $|X|$ deve
	essere uguale a $|\pi|$ e quindi:
	\eal{&v=|X|= |\pi|  \ubrace{=}{\see{cardinalitapirisoluzione}}
	\frac{(w-1)!(r-1-2)!}{(r-1-1)!(w-2)!} 
	=
	\frac{(w-1)!(r-3)!}{(r-2)!(w-2)!} 
	= \frac{w-1}{r-2} \> v(r-2)= w-1 \=  w=v(r-2)+1
	}
	E' proprio per questo motivo che richiediamo 
	$(Y,\E_Y)\in S(2,r-1,(r-2)v+1)$.
\end{prova}
}
\step{}{Passiamo alla dimostrazione}
\begin{prova}
Sia $w=(r-2)v+1$.\\
Per quanto detto nel passo precedente, abbiamo:
\eal{&v=|X|=|\pi|}
quindi la biezione $C_{\cdot}$ e gli oggetti $E_{x}$ sono tutti ben definiti.
Inoltre,
\eal{&t=|C_{x}|  \ubrace{=}{\see{KcardC}} \frac{w}{r-1}\;\;\forall x\in
X\;\;(1)
}
A questo punto, per verificare che $\forall A=\pgra{a,b}\in \P_2(X')\;\;d'(A)= 1$,
basta procedere come nella dimostrazione di \see{costruzione2v1}: poiche'
$X'=X\U Y$ abbiamo i seguenti casi disgiunti tra loro:
\case{$a\in X,\;b\in Y$}
\begin{prova}
	Basta prendere un opportuno $E_{aj}$:
	\eal{&a\in E_{aj}\;\;\forall j=1,\dots,t\NN
	E_{aj}=\pgra{a}\U C_{aj}\NN
	C_a\in \pi , \;\pi\T{ risoluzione di } (Y,\E_Y) \> 
	\pgra{C_{a1},\dots,C_{at}}\T{ e' una partizione di }Y\>
	\exists! j:\;\; b\in C_{aj}\NN
	a,b\in E_{aj}
	}
	Infine, non puo' esistere una terna in $\E$ che contenga $b$, perche'
	$Y \^X=\0$.\\
	Quindi la terna che contiene $a,b$ esiste ed e' unica.
\end{prova}
\case{$a,b\in X$}
\begin{prova}
	\eal{&(X,\E)\in S(2,r,v)
	}
	quindi qui non abbiamo alcun problema: $\exists! E\in
	\E:\;\;\pgra{a,b}\(E$.
	E poiche' $X,Y$ sono disgiunti, $E$ e' unica
	anche in $\E'$.
\end{prova}
\case{$a,b\in Y$}
\begin{prova}
	\eal{&(Y,\E_Y)\in S(2,r-1,(r-2)v+1)}
	quindi anche qui non abbiamo problemi: $\exists! E\in
        \E_Y:\;\;\pgra{a,b}\(E$. 
	\eal{&
\pi\T{ risoluzione di } (Y,\E_Y) \> 
\exists ! C_x\in \pi:\;E\in C_x \NN
C_x\T{ partizione di } Y \> \exists !j:\;\;C_{xj}=E\NN
a,b \( E \( E_{xj}=\pgra{x}\U C_{xj}
	}
	E poiche' $X,Y$ sono disgiunti, non esistono elementi di $\E$ che
	contengano $a,b$.
\end{prova}
\end{prova}
%Per dimostrare $d'(Y)=1$, sfruttiamo la prop \see{lemmaconteggio}. Contiamo
%quindi $|\E'|$:
%\eal{&Y\^ X = \0 \> \E\^\pgra{\E_{xj}\;|\;x\in X,\;j=1,\dots,t}=\0\NN
%|\E|  \ubrace{=}{\see{cardESlambdahrv}} 
%\frac{v!(r-h)!}{r!(v-h)!}\NN
%|\pgra{\E_{xj}\;|\;x\in X,\;j=1,\dots,t}| 
%\ubrace{=}{\E_{xj} \neq \E_{x'j'}\;\;\forall (x,j) \neq (x',j')}  |X| t=vt
%\ubrace{=}{(1)} v\frac{w}{r-1} = v\frac{(r-2)v+1}{r-1}\NN
%\qq \> |\E'| = |\E\U \pgra{\E_{xj}\;|\;x\in X,\;j=1,\dots,t}| =  \frac{v!(r-h)!}{r!(v-h)!}
%+v\frac{(r-2)v+1}{r-1}
%}
\end{proof}
\begin{exemp}
	Usiamo la costruzione \see{costruzioner1v1}.\\

	A partire da $(\pgra{A,B,C,D},\pgra{\pgra{A,B,C,D}})\in S(2,4,4)$
	costruiamo $S(2,4,13)$.

	Per la costruzione abbiamo bisogno di un $S(2,3,9)$ risolubile. Usiamo
	quello dell'esempio \see{expsts9} e otteniamo:
	\begin{center}
	\begin{tabular}[h]{cccc}
		ABCD  \\
		A123 & B147 & C159& D168\\
		A456 & B258 & C267& D249\\
		A789 & B369 & C348& D357
	\end{tabular}
	\end{center}
	Notiamo che questo sistema e' un modello del piano proiettivo:
	$\pgra{A,B,C,D}$  e' la retta impropria e tutte le altre rette hanno
	un punto in comune della retta impropria.
\end{exemp}
\pagebreak
\begin{prop}\label{costruzionegeometrica}
	Costruzione di un $S(2,q^n,q^{mn})$ risolubile.\\

	Sia $q$ un primo, $m,n>0$, allora
	\eal{&\exists \H =(X,\E) \in S(2,q^n,q^{mn})\T{ risolubile }
	}
\end{prop}
\def\a{{\alpha}}
\begin{proof}
	\step{}{Costruiamo un campo con $q^n$ elementi}
	\begin{prova}
	Dalla teoria dei campi e' noto che
	\eal{&q\T{ primo, } n\in \N^*  \ubrace{\>}{\AC{esistecampopn}} \exists K\T{ campo: }|K|=q^n}
	In particolare, un tale campo e' dato da
	\eal{&K=\pgra{\a\;|\;\a\T{ radice di }x^{q^n}-x\in \Z_q[x]}\NN
	\T{dove le radici si prendono dal campo di spezzamento di
	}x^{q^n}-x\in \Z_q[x]
	}
	Un altro metodo per costruire $K$ e' considerare la prop
	\AC{esistefirriducibileinZpdigradon} che afferma:
	\eal{&\exists f(x)\in \Z_q[x]:\;\;\deg f=n,\;f(x)\T{ irriducibile in
	}\Z_q[x]
	}
	e quindi
	possiamo scegliere
	\eal{&
	K=\Z_q(\a),\T{ dove } f(\a)=0
	}
	e avremo
	\eal{&|K|=q^n}
	\end{prova}
	\step{}{Costruiamo una geometria affine di $q^{mn}$ elementi}
	\begin{prova}
	Poniamo $V=K^m$. Poiche' $K$ e' un campo, $V$ e' uno spazio
	vettoriale di dimensione $m$. Su $V$ possiamo costruire una geometria affine
	considerando gli elementi di $V$ come punti e ponendo:
	\eal{&\vec{vw}=w-v
	}
	Osserviamo che una retta
	passante per un punto $P\in V$, con giacitura $w\in V\-\pgra{0}$ e':
	\eal{&r=\pgra{P+\lambda w\;|\;\;\;\lambda\in K}
	}
	Notiamo che:
	\eal{&|V|=|K^m|=|K|^m=q^{mn}}
	\step{}{Se $r$ e' una retta, allora $|r|=|K|$}
	\begin{prova}
	Poiche' il campo e' finito, una retta $r$  avra' esattamente $|K|$ punti
	distinti:
	\eal{&P+\lambda w = P+\lambda' w \= (\lambda -\lambda')w=0
	\ubrace{\=}{w \neq 0} \lambda=\lambda'\;\;(*)\NN
	|r|=|{\pgra{P+\lambda w\;|\;\;\;\lambda\in K}}|  \ubrace{=}{(*)}
	|K|\;\;(1)}
	\end{prova}
	\step{partiz}{
	La classe $C_w$ di parallelismo, formata dalla rette con giacitura
	$w$ e' una partizione di $V$.
	}
	\begin{prova}
	\eal{&\T{Siano }r,s\in C_w\NN
	P\in r\^s,\;\;r\parallel s
	\ubrace{\>}{\GII{cordims1eqdims2sses1eqs2}} r=s\;\;(2)\NN
	r \neq s,\;\;r\parallel s  \ubrace{\>}{(2)} r\^s=\0\NN
	\bigcup C_w = \bigcup_{P\in V} \pgra{P+\lambda w\;|\;\lambda\in K} 
	\ubrace{=}{\T{scegliendo }\lambda=0}  V
	}
	L'implicazione $(2)$ si puo' anche ottenere utilizzando il postulato
	delle rette parallele di Euclide.
	\end{prova}
	\step{cw}{$|C_w|=\frac{|V|}{|K|}$}
	\begin{prova}
		\eal{&V\; \ubrace{=}{\sref{partiz}} \;\bigcup_{r\in C_w}r
		\>q^{mn} = |V|=\pass{\bigcup_{r\in C_w}r }
		\ubrace{=}{\sref{partiz}} 
	\sum_{r\in C_w}|r|  \ubrace{=}{(1)} |K| |C_w| \=\NN
	\=
	|C_w| = \frac{|V|}{|K|}= \frac{q^{mn}}{q^n} = q^{n(m-1)}\;\;\;(3)
	}
	\end{prova}
	\end{prova}
	
	\step{}{Posto $R=\pgra{r\;|\;r\T{ retta di $V$}}$ si ha $(V,R)\in
	S(2,q^n,q^{mn})$}
	\begin{prova}
		Per costruzione, $(X,V)$ e' un ipergrafo uniforme di rango
		$|r|=|K|=q^n$ con $|V|=q^{mn}$ punti.
		
		E poiche' $V$ e' una geometria affine e stiamo includendo tutte le rette, si ha:
		\eal{&\forall \pgra{P,Q}\in \P_2(V)\;\;\exists!
		r\in R:\;\;\pgra{P,Q}}
	\end{prova}
	\step{}{Una risoluzione di $(V,R)$ e' $\pgra{C_w\;|\;w\in V}$}
	\begin{prova}
		Abbiamo gia' visto che ogni $C_w$ e' una partizione di $V$.\\
		Dimostriamo che $\pgra{C_w\;|\;w\in V}$ e' una partizione di
		$R$.
		\eal{&r\in R \> \exists w\in V,\;P\in V:\;\;r=\pgra{P+\lambda
		w\;|\;\lambda\in K} \> r\in C_w\NN
		\T{Quindi, } \bigcup_{w\in V}C_w=R\NN
		C_w \neq C_v \> \nexists \lambda\in K:\;\;w=\lambda v
		\> C_w\^C_v=\0
		}
	\end{prova}
	\step{pdx}{Sia $d(P)$ il grado di $P\in V$ rispetto al sistema $(V,R)$. E
	sia $R_P=\pgra{r\in R\;|\;P\in r}$. Allora si ha
	\eal{&|\pgra{C_w\;|\;w\in V}| = d(P)= |R_P|= \frac{q^{mn}-1}{q^n-1} }
	}
	\begin{prova}
		Poiche' $(V,R)$ e' un $S(2,q^n,q^{mn})$ e' sufficiente
		applicare la proposizione \see{cardinalitapirisoluzione} e la
		\see{dxeqpieqEx}:
		\eal{&|\pgra{C_w\;|\;w\in V}|
		\ubrace{=}{\see{cardinalitapirisoluzione}} 
		\frac{(q^{mn}-1)!(q^n-2)!}{(q^n-1)!(q^{mn}-2)!}
		= \frac{q^{mn}-1}{q^n-1}  \ubrace{=}{\see{dxeqpieqEx} }
		 d(P)= |R_P|
		}
	\end{prova}
	Diamo adesso un metodo per scrivere efficientemente tutti i $C_w$ e
	tutte le loro rette.
	\case{$m=1$}
	\begin{prova}
		Se $m=1$, per il \sref{pdx} abbiamo:
		\eal{&|\pgra{C_w\;|\;w\in V}|  = \frac{q^{n}-1}{q^n-1} =1
		}
		Quindi esiste una sola classe $C_1$.\\
		\eal{&|C_1|  \ubrace{=}{(3)}q^{n(m-1)}  \ubrace{=}{m=1}  1 }
		quindi esiste una sola retta che concide con tutto $V$.
	\end{prova}
	\case{$m=2$}
	\begin{prova}
		Sia $r_0$ la seguente retta:
		\eal{&r_0=\pgra{\lambda (1,0)\;|\;\lambda\in K}
		=\pgra{(\lambda,0)}_{\lambda\in K}
		}
		Sia $C_{w_0}$ la  classe di parallelismo di rette con
		giacitura $w_0=(1,0)$ (e quindi $r_0\in C_{w_0}$).\\
		Sia $P\in V\-r_0$ e sia data la seguente retta $r_1\in C_{w_0}$:
		\eal{&r_1=\pgra{P+\lambda (1,0)\;|\;\lambda\in K}
		}
		$r_1 \neq r_0$ in quanto $P\notin r_0$. Nota: $r_1$ deve esistere perche' $m>1 \ubrace{\>}{(3)}  |C_{w_0}| >1$\\
		Poniamo $D=\pgra{w_0}\U r_1$.
\step{}{Dimostriamo che $\pgra{C_w\;|\;w\in V}= \pgra{C_w\;|\;w\in D}$}
\begin{prova}
Spiegazione (non formalizzata): sia $Kw_0$ la retta passante per 
l'origine e di vettore $w_0$, cioe'
$\pgra{\lambda w_0\;|\;\lambda\in K }$, sia $P\in V\-Kw_0$ un punto
fuori dalla retta e sia  $P+Kw_0$ la retta di vettore $w_0$ e
passante per $P$. Questa retta e' parallela a $Kw_0$ e stanno nella
stessa classe di parallelismo $C_{w_0}$. 
Se $C$ e' una classe di parallelismo, distinta da $C_{w_0}$, dato che
copre il piano, esistera' una retta $r_C\in C$ passante per
l'origine. Questa retta si incontra con $P+Kw_0$ in un qualche punto
$P+\lambda_Cw_0$, altrimenti sarebbe parallela ad essa. Allora un vettore di questa retta e'
$v=(P+\lambda_Cw_0) - \ove 0=P+\lambda_C w_0$. Le rette in $C$ sono
parallele a $r_C$ e quindi un loro vettore sara' il vettore $v$ di $r_C$.
%Il vettore di $r_C$ e' ottenuto normalizzando un suo qualsiasi vettore. $v/ \norm{v}$ e' il normalizzato di $v$. ; esiste sqrt() nel campo? ; 
Viceversa, un vettore $v=P+\lambda w_0$ definisce una classe di
parallelismo $C_v$,
$C_v= \pgra{r\;|\; r\T{ retta con vettore $v$ }}$. Quindi,
\eal{&\pgra{C\;|\;C \T{ classe di parallelismo }} = \pgra{C_{w_0}} \U \pgra{C_v\;|\;v\in P+Kw_0} = \pgra{ C_w\;|\; w\in \pgra{w_0}\U (P+Kw_0)}}\\

	Dimostrazione:\\

	chiaramente l'inclusione $\)$ e' vera.\\
	Contiamo gli elementi del secondo insieme.\\
	Presi $w,v\in D$ distinti, si ha $C_w\^C_v=\0$. Per dimostrarlo
Supponiamo per
	assurdo $C_w\^C_v \neq \0$
	\eal{&C_w\^C_v \neq \0  \ubrace{\>}{\pgra{C_w\;|\;w\in V}\T{
	partizione di }R}  C_w=C_v \> 
	\exists \mu\in K^*:\;\;w=\mu v \;\;(4)\NN
\qq \> \pgra{\lambda w\;|\;\lambda\in K} = \pgra{\lambda v\;|\;\lambda\in
K} =  \pgra{\lambda(v-w)\;|\;\lambda\in K}\;\;(4.1)
	}
Distinguiamo due casi:
	\case{$w,v\in D\-\pgra{w_0}$}
	\begin{prova}
		\eal{&w,v\in D\-\pgra{w_0=(1,0)}=r_1
		\> w=P+\lambda' w_0,\;\;v=P+\lambda''w_0
		\> v-w = (\lambda''-\lambda')w_0 \>\NN
		\ubrace{\>}{(4.1)} \pgra{\lambda w\;|\;\lambda\in K} =
		\pgra{\lambda(\lambda''-\lambda')w_0\;|\;\lambda\in K}=
		\pgra{\lambda w_0\;|\;\lambda\in K} = r_0\NN
		\qq \> w \in r_0 \> r_0\^r_1 \neq \0
	}
	e questo e' assurdo in quanto $r_0,r_1\in C_{w_0}$ e $r_0 \neq r_1$.
	\end{prova}
	\case{$w\in D\-\pgra{w_0},\;\;v=w_0$}
	\begin{prova}
		\eal{&w \in D\-\pgra{w_0}=r_1\NN
		(4.1) \> \pgra{\lambda w\;|\;\lambda\in K}
		=  \pgra{\lambda v\;|\;\lambda\in K}  \ubrace{=}{v=w_0} 
		\pgra{\lambda w_0\;|\;\lambda\in K}=r_0\NN
		\qq \> w\in r_0\> r_0\^r_1 \neq \0
		}
		ed anche qui si arriva allo stesso assurdo di prima.
	\end{prova}
	
	Possiamo cosi' affermare che
	\eal{& |\pgra{C_w\;|\;w\in D}| = |D|= |\pgra{w_0}|+ |r_1|=1+
	|K|\;\;(5)
	}
	Infine,
	\eal{&
	|\pgra{C_w\;|\;w\in V}|
	\ubrace{=}{\sref{pdx}} 
	= \frac{q^{mn}-1}{q^n-1}   \ubrace{=}{m=2}  \frac{q^{2n}-1}{q^n-1}
	=\frac{(q^n-1)(q^n+1)}{q^n-1}=q^n+1  \ubrace{=}{(5)} |\pgra{C_w\;|\;w\in D}| 
	}
	Poiche' vale l'inclusione $\($, abbiamo cosi' dimostrato che
	\eal{&\pgra{C_w\;|\;w\in V} = \pgra{C_w\;|\;w\in D}
	}

	\step{}{
	Sia $w\in D\-\pgra{w_0}=r_1$. Le rette di $C_{w}$ sono
\eal{&C_{w} =\pgra{ \pgra{A+\lambda w\;|\;\lambda\in K}\;|\;A\in r_0}
}
Infatti,
	}
	\begin{prova}
Chiaramente vale l'inclusione $\)$.\\
Confrontiamo  la cardinalita' dei due insiemi per stabilire l'uguaglianza.\\
	Se $A,B\in r_0$ sono distinti, allora anche le rette $ r=\pgra{A+\lambda
	w},\;\; s=\pgra{B+\lambda w}$ sono distinte, perche' altrimenti si
	avrebbe:
	\eal{&
	A,B\in r_0 \> \exists
	\lambda_A,\;\lambda_B:\;\;A=\lambda_Aw_0,\;\;B=\lambda_Bw_0\NN
	w\in D\-\pgra{w_0}=r_1 \> w=P+\lambda_ww_0\NN
	A,B\in r=s \> 	s=r=\pgra{A+\lambda \vec{BA}\;|\;\lambda\in K}=\NN
	=
	\pgra{A+\lambda(A-B)=\lambda_Aw_0+\lambda
	\pton{\lambda_Aw_0 -\lambda_Bw_0}
	= (\lambda_A+(\lambda_A -\lambda_B)\lambda)w_0
	\;|\;\lambda \in K} = r_0 \NN
\sist{	r=s=r_0\\
r_0\in C_{w_0}
r\in C_w} \> C_{w}\^C_{w_0} \neq \0 \> C_w=C_{w_0} \> \exists k:\;w=kw_0\> w\in r_0
	}
	ma questo e' assurdo contro $w\in r_1$.

	Abbiamo quindi:
	\eal{&|\pgra{ \pgra{A+\lambda w\;|\;\lambda\in K}\;|\;A\in r_0}  
	|= |r_0| = |K|\NN
	|C_w|  \ubrace{=}{(3)} q^{n(m-1)} \ubrace{=}{m=2}  q^n=|K|
	}
	L'uguaglianza e' cosi' provata.
	\end{prova}
\step{}{
	Le rette di $C_{w_0}$ sono
\eal{&C_{w_0} =\pgra{ \pgra{A+\lambda w_0\;|\;\lambda\in K}\;|\;A\in 
\pgra{(0,\mu)\;|\;\mu\in K}
}
= \pgra{\pgra{(\lambda,\mu) \;|\;\lambda\in K}\;|\;\mu\in K}
}
Infatti,
	}
	\begin{prova}
		Procediamo come prima.\\
Le rette nel secondo insieme sono distinte per $\mu,\mu'$ distinti:
\eal{&\pgra{(\lambda,\mu) \;|\;\lambda\in K} =
\pgra{(\lambda,\mu') \;|\;\lambda\in K} 
(0,\mu)=(\lambda,\mu') \> \mu=\mu'
}
Quindi nel secondo insieme ci sono $|K|$ rette. E poiche' $|K|=|C_{w_0}|$
abbiamo la tesi.
	\end{prova}
	\end{prova}
\end{prova}
\end{proof}
\begin{exemp}
	Costruzione di $S(2,4,16)$ risolubile con l'uso della prop
	\see{costruzionegeometrica}.\\
	\def\w{{\T{$\omega$}}}
	\def\ww{{\T{$\ove\omega$}}}
	\def\.{{\cdot}}

	In questo caso i parametri sono:
	\eal{&q=2,\;n=2,\;m=2}

	Come campo scegliamo $K=\pgra{0,1,\w,\ww}$ che sono tutte le radici
	di $x^{4}-x=x(x^3-1)\in \Z_2[x]$.

	E' facile vedere che le tabelle delle operazioni $+$ e $\.$ su $K$
	sono:
	\begin{center}
	\begin{tabular}[h]{c|cccc}
		+  & 0 & 1 & \w & \ww\\
		\hline\\
		0  & 0 & 1 & \w & \ww\\
		1  & 1 & 0 & \ww & \w\\
		\w & \w & \ww & 0 & 1\\
		\ww&\ww & \w & 1  & 0
	\end{tabular}
	\end{center}

	\begin{center}
	\begin{tabular}[h]{c|cccc}
		$\.$  & 0 & 1 & \w & \ww\\
		\hline\\
		0  & 0 & 0 & 0 & 0\\
		1  & 0 & 1 & \w & \ww\\
		\w & 0 & \w & \ww & 1\\
		\ww& 0 & \ww & 1 & \w
	\end{tabular}
	\end{center}

	La retta $r_0=\pgra{\lambda (1,0)\;|\;\lambda\in K}$ e' data dai  punti:
\eal{&r_0:\;\;(0,0),\;(1,0),\;(\w,0),\;(\ww,0)
}
Scelto $P=(0,1)\notin r_0$, la retta $r_1=\pgra{P+\lambda(1,0)\;|\;\lambda\in
K}$ diventa:
\eal{&r_1:\;\;(0,1),\;(1,1),\;(\w,1),\;(\ww,1)
}
Quindi l'insieme $D$ di vettori non paralleli e' dato da:
\eal{&w_0=(1,0),\;w_1=(0,1),\;w_2=(1,1),\;w_3=(\w,1),\;w_4=(\ww,1)
}

A questo punto abbiamo trovato tutte le $5$ classi di parallelismo che
risolvono $(V,R)$. Dobbiamo solamente scrivere i punti delle loro rette usando
le loro equazioni e le tabelle delle operazioni di $K$. In particolare, per
quanto visto in \see{costruzionegeometrica},
le rette di $C_{w_i}$ sono
\eal{&C_{w_i} =\pgra{ \pgra{A+\lambda w_i\;|\;\lambda\in K}\;|\;A\in r_0}
}

Calcoliamo $C_{w_2}$:
\eal{&\pgra{\lambda w_2\;|\;\lambda\in K}:\NN
\qq 0w_2=(0,0)\NN
\qq 1w_2=(1,1)\NN
\qq \w w_2 = (\w,\w)\NN
\qq \ww w_2  = (\ww, \ww)\NN
\pgra{(1,0)+\lambda w_2\;|\;\lambda\in K}:\NN
\qq (1,0)\NN
\qq (1,0)+(1,1)=(0,1)\NN
\qq (1,0)+(\w,\w) = (\ww,\w)\NN
\qq (1,0)+(\ww, \ww) = (\w,\ww)\NN
\pgra{(\w,0)+\lambda w_2\;|\;\lambda\in K}:\NN
\qq (\w,0)\NN
\qq (\w,0)+(1,1)=(\ww,1)\NN
\qq (\w,0)+(\w,\w) = (0,\w)\NN
\qq (\w,0)+(\ww, \ww) = (1,\ww)\NN
\pgra{(\ww,0)+\lambda w_2\;|\;\lambda\in K}:\NN
\qq (\ww,0)\NN
\qq (\ww,0)+(1,1)=(\w,1)\NN
\qq (\ww,0)+(\w,\w) = (1,\w)\NN
\qq (\ww,0)+(\ww, \ww) = (0,\ww)\NN
}

Per quanto visto in \see{costruzionegeometrica}, 
le rette di $C_{w_0}$ sono
\eal{&C_{w_0} =
 \pgra{\pgra{(\lambda,\mu) \;|\;\lambda\in K}\;|\;\mu\in K}
}
Quindi
\eal{&
\pgra{(\lambda,0) \;|\;\lambda\in K} = r_0:\NN
\qq r_0:\;\;(0,0),\;(1,0),\;(\w,0),\;(\ww,0)\NN
\pgra{(\lambda,1) \;|\;\lambda\in K}:\NN
\qq (0,1),\;(1,1),\;(\w,1),\;(\ww,1)\NN
\pgra{(\lambda,\w) \;|\;\lambda\in K}:\NN
\qq (0,\w),\;(1,\w),\;(\w,\w),\;(\ww,\w)\NN
\pgra{(\lambda,\ww) \;|\;\lambda\in K}:\NN
\qq (0,\ww),\;(1,\ww),\;(\w,\ww),\;(\ww,\ww)
}

Procedendo analogamente a prima si ha:
\eal{&C_{w_1}:\NN
\qq (0,0),\;(0,1),\;(0,\w),\;(0,\ww)\NN
\qq (1,0),\;(1,1),\;(1,\w),\;(1,\ww)\NN
\qq (\w,0),\;(\w,1),\;(\w,\w),\;(\w,\ww)\NN
\qq (\ww,0),\;(\ww,1),\;(\ww,\w),\;(\ww,\ww)\NN
C_{w_3}:\NN
\qq (0,0),\;(\w,1),\;(\ww,\w),\;(1,\ww)\NN
\qq (1,0),\;(\ww,1),\;(\w,\w),\;(0,\ww)\NN
\qq (\w,0),\;(0,1),\;(1,\w),\;(\ww,\ww)\NN
\qq (\ww,0),\;(1,1),\;(0,\w),\;(\w,\ww)\NN
C_{w_4}:\NN
\qq (0,0),\;(\ww,1),\;(1,\;\w),\;(\w,\ww)\NN
\qq (1,0),\;(\w,1),\;(0,\;\w),\;(\ww,\ww)\NN
\qq (\w,0),\;(1,1),\;(\ww,\;\w),\;(0,\ww)\NN
\qq (\ww,0),\;(0,1),\;(\w,\;\w),\;(1,\ww)
}

Infine, adoperando la biezione tra l'insieme $\pgra{1,2,\dots,16}$ e $V$ che
trasforma la classe $C_{w_0}$ nella seguente:
\eal{&
\pgra{(\lambda,0) \;|\;\lambda\in K} = r_0:\NN
\qq r_0:\;\;1,\;2,\;3,\;4\NN
\pgra{(\lambda,1) \;|\;\lambda\in K} = r_0:\NN
\qq 5,\;6,\;7,\;8\NN
\pgra{(\lambda,\w) \;|\;\lambda\in K} = r_0:\NN
\qq 9,\;10,\;11,\;12\NN
\pgra{(\lambda,\ww) \;|\;\lambda\in K} = r_0:\NN
\qq 13,\;14,\;15,\;16
}
concludiamo con la seguente risoluzione:
\eal{&
C_{w_0}:\NN
\qq 1,\;2,\;3,\;4\NN
\qq 5,\;6,\;7,\;8\NN
\qq 9,\;10,\;11,\;12\NN
\qq 13,\;14,\;15,\;16\NN
C_{w_1}:\NN
\qq 1,\;5,\;9,\;13\NN
\qq 2,\;6,\;10,\;14\NN
\qq 3,\;7,\;11,\;15\NN
\qq 4,\;8,\;12,\;16\NN
C_{w_2}:\NN
\qq 1,\; 6,\; 11,\;16\NN
\qq 2,\; 5,\; 12,\; 15\NN
\qq 3,\; 8,\; 9,\; 14\NN
\qq 4,\; 7,\; 10,\; 13\NN
C_{w_3}:\NN
\qq 1,\;7,\;12,\;14\NN
\qq 2,\;8,\;11,\;13\NN
\qq 3,\;5,\;10,\;16\NN
\qq 4,\;6,\;9,\;15\NN
C_{w_4}:\NN
\qq 1,\;8,\;10,\;15\NN
\qq 2,\;7,\;9,\;16\NN
\qq 3,\;6,\;12,\;13\NN
\qq 4,\;5,\;11,\;14
}
\end{exemp}
\def\SQS{\oname{SQS}}
\begin{prop}
	Costruzione di un $\SQS(2v)$ a partire da un $\SQS(v)$.\\
	Siano $\H_1=(X_1,\E_1) ,\H_2=(X_2,\E_2)\in \SQS(v)$, con
	$X_1\^X_2=\0$, poniamo:
	\eal{&X:=X_1\U X_2\NN
	F=\pgra{F_1,\dots,F_{v-1}} \T{ una $1$-fattorizzazione di }
	(X_1,\P_2(X_1))\NN
	G=\pgra{G_1,\dots,G_{v-1}} \T{ una $1$-fattorizzazione di }
	(X_2,\P_2(X_2))\NN
	\alpha\T{ permutazione di }\pgra{1,\dots,v-1}\NN
	\Gamma = \pgra{\pgra{x,y,z,t}\in \P_4(X)\;|\;
	\pgra{x,y} \in F_{\a(i)},\;\;\pgra{z,t}\in G_{i},\;\;i=1,\dots,v-1
	}\NN
	\E:=\Gamma \U \E_1\U\E_3
	}
	allora si ha
	\eal{&(X,\E)\in \SQS(2v)
	}
\end{prop}
\begin{proof}
	Per verficare che $(X,\E)$ sia un $\SQS(2v)=S(3,4,2v)$, consideriamo
	$\pgra{x,y,z}\in \P_3(X)$ e dimostriamo che $\exists !\;\;E\in
	\E:\;\;\pgra{x,y,z}\( \E$.\\
	Distinguiamo $4$ casi:
	\case{$x,y,z\in X_1$}
	\begin{prova}
In $\Gamma$ non possiamo trovare alcun $4$-oggetto perche' negli oggetti di
$\Gamma$ ci sono almeno due elementi di $X_2$:
\eal{&E\in \Gamma \> |E\^X_2|=2 \> \pgra{x,y,z}\nsubseteq E
}
Neanche in $\E_2$ possiamo trovare oggetti buoni, perche' $X_1\^X_2=\0$.\\
Quindi l'unico oggetto dovra' trovarsi in $\E_1$.
	\end{prova}
\case{$x,y\in X_1,\;z\in X_2$}
	\begin{prova}
Per questo caso basta osservare la seguente figura per capire come funziona
$\alpha$:
\begin{center}
	\includegraphics[scale=0.5]{fig/tmp.4IpqLztkkV/out1}
\end{center}
	\end{prova}
\case{$x\in X_1,\;y,z\in X_2$}
	\begin{prova}
Analogamente a prima, ma usando $\inv \a$.
	\end{prova}
\case{$x,y,z\in X_2$}
	\begin{prova}
		Analogamente al primo caso.
	\end{prova}
\end{proof}
\begin{exemp}\label{expSQS8}
	Consideriamo il seguente $\SQS(4)$:
	\eal{&(\pgra{1,2,3,4},\pgra{\pgra{1,2,3,4}}) }
	e quest'altro $\SQS(4)$:
	\eal{&(\pgra{5,6,7,8},\pgra{\pgra{5,6,7,8}}) }
Una $1-$fattorizzazione di $X_1$ e' 
	\begin{center}
	\begin{tabular}[h]{c|c|c}
		12&13&14\\
		34&24&23
			\end{tabular}
	\end{center}
	e quella di $X_2$ e'
	\begin{center}
	\begin{tabular}[h]{c|c|c}
		56&57&58\\
		78&68&67
	\end{tabular}
	\end{center}
	Se come $\a$ scegliamo l'identita', $\Gamma$ sara' dato da:
	\eal{&1256 \NN
	1278\NN
	3456\NN
	3478\NN
	1357\NN
	1368\NN
	2457\NN
	2468\NN
	1458\NN
	1467\NN
	2358\NN
	2367
	}
	E aggiungendoci $1234,5678$ otterremo l'$\E$ dell'$\SQS(8)$:
	\eal{&1234\NN
	5678\NN
	1256 \NN
	1278\NN
	3456\NN
	3478\NN
	1357\NN
	1368\NN
	2457\NN
	2468\NN
	1458\NN
	1467\NN
	2358\NN
	2367
	}
\end{exemp}

\subsection{Blocking set}
\begin{prop}\label{nobsetinSTS}
	Sia $\H=(X,\E)\in \STS(v)$, si ha
	\eal{&v \neq  3 \> \T{Non esistono blocking set per  $\H$}
	}
	In pratica, gli $\STS(v)$ non banali non hanno blocking set.
\end{prop}
\begin{proof}
	Supponiamo che $B$ sia un blocking set di $\H$. Sia $p=|B|$.
	Possiamo partizionare $\E$ in due tipi di spigoli:
	\eal{&
	\E_1=\pgra{E\in \E \;|\;\;|B\^E|=1}\NN
	\E_2=\pgra{E\in \E \;|\;\;|B\^E|=2}\NN
	\E_1\U\E_2=\E,\;\;\E_1\^\E_2=\E
	}
	Graficamente:
	\begin{center}
		\includegraphics[scale=0.4]{fig/bset2}
	\end{center}
Possiamo associare una coppia in $B$ ad uno spigolo $E\in \E_2$:
\eal{&\pgra{x,y}\in \P_2(B)  \ubrace{\>}{B\(X,\;\H\in \STS(v)} 
\> \exists!\;\;E\in \E:\;\;\pgra{x,y}\(
E  \ubrace{\>}{\pgra{x,y}\(B}  |B\^E|=2 \> E\in \E_2\NN
\T{Quindi } \pgra{x,y}\in \P_2(B) \> \exists !  E\in \E_2:\;\;\pgra{x,y}\( E\NN
\T{Viceversa, } E\in \E_2 \> B\^E \in \P_2(B)\NN
\T{Otteniamo quindi una corrispondenza biunivoca tra } \E_2 \T{ e }
\P_2(B):\NN
\qq |\E_2|=|\P_2(B)| = \binom{p}{2}
}
Analogamente, associando le coppie in $X\-B$ a spigoli in $\E_1$ abbiamo:
\eal{&|\E_1|= \binom{|X\-B|}{2} = \binom{v-p}{2}
}
In definitiva:
\eal{&\binom{p}{2}
+\binom{v-p}{2}  = |\E_1|+|\E_2| = |\E|  \ubrace{=}{\see{STSprop1}}
\frac{v(v-1)}{6} \= \NN
\= \frac{p(p-1)+(v-p)(v-p-1)}{2}  = \frac{v(v-1)}{6} 
\= 
{p}^{2}+\frac{1}{2}{v}^{2}-vp-\frac{1}{2}v=\frac{1}{6}v \left( v-1 \right)\;\;(1)
}
La $(1)$ ammette soluzioni in $p$ se e solo se il suo discriminante $\Delta
\ge 0$:
\eal{&\Delta=-\frac{1}{3}\,{v}^{2}+\frac{4}{3}\,v \ge  0 \= 
0\le v\le 4\;\;(2)\NN
\H \in \STS(v)  \ubrace{\>}{\see{thmspettri}} 
v=1,3\;\;\Z_6,\;v\ge 3  \ubrace{\>}{(2)} v=3
}
assurdo contro ipotesi $v \neq 3$.
\end{proof}
\begin{cor}
	Sia $\H\in \STS(v)$
	\eal{&v>3 \> \chi(\H) >2}
\end{cor}
\begin{proof}
	Basta applicare la \see{nobsetinSTS} e la \see{equivalenzabsetchi}
\end{proof}
\begin{prop}\label{SQSbset}
Sia $\H=(X,\E)\in \SQS(8)=S(3,4,8)$, allora
\eal{&B\in \P_4(X)\-\E \> B\T{ e' un blocking set di }\H
}
\end{prop}
\begin{proof}
Poiche' $|X|=8$, avremo (a meno di rinominare gli elementi di $X$):
\eal{&B=\pgra{1,2,3,4}\NN
X\-B=\pgra{5,6,7,8}
}
Supponiamo per assurdo che $B$ non sia un blocking set. Distinguiamo due casi
\case{$X\-B$ non e' un trasversale.}
\begin{prova}
	Quindi $\exists E\in \E:\;\;$
\eal{&E\^(X\-B)=\0 \= E\( B  \ubrace{\=}{|E|=|B|=4}  B=E\in \E}
assurdo contro $B\in \P_4(X)\-\E $
\end{prova}
\case{$B$ non e' un trasversale}
\begin{prova}
	Quindi $\exists E\in \E:\;\;$
\eal{&E\^B=\0 \= E\(X\-B  \ubrace{\=}{|E|=|B|=4}  X\-B=E\in \E\NN
X\-B=\pgra{5,6,7,8}\in \E\;\;(0)}
Poiche' $\H\in \SQS(8)$, scelto $\pgra{1,2,3}$ esiste un sono elemento $m$ tale
che $\pgra{1,2,3,m}\in \E$.\\
$m$ non puo'essere $4$ perche' altrimenti $B\in\E$. Quindi $m\in X\-B$.\\
Supponiamo che sia $m=6$ (e' indifferente quale elemento di $X\-B$ scegliamo,
perche' possiamo ancora rinominare gli elementi di $X\-B$).\\
Quindi:
\eal{&\pgra{1,2,3,6}\in \E\;\;(1)}
Analogamente, scleto $\pgra{2,3,4}$, possiamo porre $m=5$:
\eal{&\pgra{2,3,4,5} \in \E\;\;(2)
}
Nota: $m \neq 6$ perche' altrimenti, $\pgra{2,3,6}$ sarebbe contenuto in due
spigoli. Assurdo contro $\H\in \SQS$.\\
Consideriamo $\pgra{5,6,4,m}$. $m$ non puo' essere $2,3$ (altrimenti siamo
in contrasto con la $(2)$). $m$ non puo' essere $7,8$ (contrasto con la
$(0)$). $m$ non puo' neanche essere $5,6,4$. Come
alternativa  rimane solo $1$. Quindi,
\eal{&\pgra{5,6,4,1}\in \E\;\;(3)}
Consideriamo $\pgra{1,4,3,m}$. Per evitare contrasti, le uniche possibilita'
sono $7,8$. Scegliamo $m=7$ (anche qui la scelta e' indifferente: possiamo
rinominare $7$ con $8$ e la dimostrazione rimarrebbe valida). Quindi,
\eal{&\pgra{1,4,3,7}\in \E\;\;(4)
}
Consideriamo $\pgra{1,4,2,m}$, si deve avere $m=8$:
\eal{&\pgra{1,4,2,8}\in \E\;\;(5)
}
Adesso cambiamo metodo. Consideriamo $\pgra{3,4}$. Gli unici elementi che non
abbiamo accoppiato con $3,4$ sono $6,8$, quindi si deve avere:
\eal{&\pgra{3,4,6,8}\in \E\;\;(6)
}
Analogamente considerando $\pgra{2,4}$ si deve avere:
\eal{&\pgra{2,4,6,7}\in \E\;\;(7)
}
Infine, considerando $\pgra{6,7,3}$, per non andare in contrasto si deve
avere:
\eal{&\pgra{6,7,3,1}\in \E\;\;(8)}
Ma  allora $\pgra{6,3,1}$ e' contenuta sia nella $(8)$ che nella $(1)$.
Assurdo contro $\H\in \SQS$.
\end{prova}
\end{proof}
\begin{exemp}\label{expSQSbset}
	Consideriamo l'$\SQS(8)$ visto in \see{expSQS8}:
	\eal{&\E:\;\;1234,\;\;
	5678,\;\;
	1256 ,\;\;
	1278,\;\;
	3456,\;\;
	3478,\;\;
	1357,\;\;
	1368\NN
	\qq 2457,\;\;
	2468,\;\;
	1458,\;\;
	1467,\;\;
	2358,\;\;
	2367
	}
	$\pgra{1,2,3,5}$ non e' un elemento di $\E$ (altrimenti $\pgra{1,2,3}$
	sarebbe contenuto sia da $\pgra{1,2,3,5}$ che da $\pgra{1,2,3,4}$).
	Allora, per la prop \see{SQSbset}, $\pgra{1,2,3,5}$ e' un blocking
	set.
\end{exemp}
\begin{prop}\label{bsetperSQS}
	Sia $\H=(X,\E)\in \SQS(v)$.
	\eal{&B\T{ blocking set per } \H,\;\;v>4
	\> |B|=\frac{v}{2}
	}
\end{prop}
\begin{proof}
	\pfsketch{
	Procedendo analogamente alla prop \see{nobsetinSTS}, conteremo $|\E_2|$ in due modi diversi e confrontando i risultati
	ottenuti otterremo una nuova equazione.}

	Sia
	\eal{& \E_i=\pgra{E\in \E \;|\;\;|B\^E|=i},\;\;i=1,2,3}
	si ha
	\eal{&\E_i\^\E_j=\0\;\;\forall i \neq j\NN
	\E_1\U\E_2\U\E_3=\E
	}

%	Analogamente a quanto visto in \see{nobsetinSTS}, possiamo mettere in
%	biezione $\P_3(B)$ con $\E_3$:
%\eal{&\pgra{x,y,z}\in \P_3(B)  \ubrace{\>}{B\(X,\;\H\in S(3,4,v)} 
%\> \exists!\;\;E\in \E:\;\;\pgra{x,y,z}\(
%E  \ubrace{\>}{\pgra{x,y,z}\(B}  |B^E|=3 \> E\in \E_3\NN
%\T{Quindi } \pgra{x,y,z}\in \P_3(B) \> \exists !  E\in \E_3:\;\;\pgra{x,y,z}\( E\NN
%\T{Viceversa, } E\in \E_3 \> B\^E \in \P_3(B)\NN
%\T{Otteniamo quindi una corrispondenza biunivoca tra } \E_3 \T{ e }
%\P_3(B):\NN
%\qq |\E_3|=|\P_3(B)| = \binom{p}{3}
%}
%Analogamente, associando le terne in $X\-B$ a spigoli in $\E_1$ abbiamo:
%\eal{&|\E_1|= \binom{|X\-B|}{3} = \binom{v-p}{3}
%}
%Adesso 
%
Contiamo  $|\E_2|$.
\step{p2}{Sia 
\eal{&\E_T=\pgra{E\in \E\;|\;T\( E}\NN
\E_{3T}=\pgra{ E\in \E_3\;|\;T\( E } 
}
Dim che 
\eal{&\pgra{\E_T\-\E_{3T}\;|\;T\in \P_2(B)}\T{ e' una partizione di }\E_2}}
\begin{prova}
	\step{}{
	\eal{&
\E_2=\bigcup_{T\in \P_2(B)}(\E_T\-\E_{3T})
}
	}
	\begin{prova}
	\step{}{Dim $\)$}
	\begin{prova}
Sia $T\in \P_2(B)$, e sia $E\in \E_T\-\E_{3T}
$, si ha
\eal{&T\( E \> |E\^B| \ge |T| = 2 \> E\notin \E_1\NN
E\notin \E_3\NN
\qq \> E\in \E_2
}
	\end{prova}
	\step{}{Dim $\($}
	\begin{prova}
		\eal{&E\in \E_{2}\> |E\^B|=2
		}
		quindi basta porre $T=E\^B$.
	\end{prova}
	\end{prova}
	\step{}{$(\E_T\-\E_{3T})\^(\E_S\-\E_{3S})=\0\;\;\forall T \neq
	S,\;T,S\in \P_2(B)$}
	\begin{prova}
\eal{&E\in (\E_T\-\E_{3T})\^(\E_S\-\E_{3S})
\> E\in \E_T\^\E_S \> T\U S \( E\;\;(0)\NN
T\^S=\0  \ubrace{\>}{T,S\in \P_2(B)}   |E\^B| \ge |T|+|S|= 4 \T{ assurdo
}\;\;(1)\NN
(1),\;T \neq S \> T\U S=\pgra{x,y,z}\T{ con $x,y,z$ distinti, $y\in T\^S$
}\;\;(2)\NN
(0),(2) \> |E\^B|=3 \> E\in \E_3
}
assurdo contro $E\notin \E_{3T}\U\E_{3S}$.
	\end{prova}
\end{prova}
Notiamo che
\eal{&|\E_T|=d(T) \ubrace{=}{\see{SQSprop3}} \frac{v-2}{2}\;\;(3)\NN
T=\pgra{x,y},\;x \neq y\NN
\E_{3T}=\pgra{E\in \E_3\;|\;\pgra{x,y}\(E}=
\pgra{E\in \E\;|\;E\^B=\pgra{x,y,z},\;z\in B,\;z\notin\pgra{x,y}} \>\NN
\ubrace{\>}{\T{corrispondenza biunivoca tra }\P_3(B),\;\E_3}
|\E_{3T}|=|\pgra{\pgra{x,y,z}\;|\;z\in B\-\pgra{x,y}}| =|B|-2\;\;(4)
}
Quindi,
\eal{&
|\E_2|  \ubrace{=}{\sref{p2}} \sum_{T\in \P_2(B)}|\E_T\-\E_{3T}|
=  \sum_{T\in \P_2(B)}|\E_T\-\E_{3T}|
\ubrace{=}{(3),(4)} 
\sum_{T\in \P_2(B)} \pton{ \frac{v-2}{2} - (|B|-2)}
= |\P_2(B)| \pton{ \frac{v-2}{2} - (|B|-2)}
}
Analogamente, possiamo considerare la seguente partizione di $\E_2$:
\eal{&\pgra{\E_T\-\E_{1T}\;|\;T\in\P_2(X\-B)}
}
e otteniamo:
\eal{&|\E_2|=  |\P_2(X\-B)| \pton{ \frac{v-2}{2} - (|X\-B|-2)}\;\;(5)
}
Quindi confrontando le due espressioni ottenute per $|\E_2|$ abbiamo:
\eal{&0=|\P_2(B)| \pton{ \frac{v-2}{2} - (|B|-2)} - |\P_2(X\-B)| \pton{
\frac{v-2}{2} - (|X\-B|-2)}=\NN
=
\binom{p}{2}\pton{\frac{v-2}{2}-(p-2)}
-\binom{v-p}{2}\pton{\frac{v-2}{2}-(v-p-2)} = \NN
=
p(p-1)(v-2-2p+4) - (v-p)(v-p-1)(v-2-2v+2p+4)
=  \NN
=
p(p-1)(v-2p+2) - (v-p)(v-p-1)(-v+2p+2) 
= -4 p ^{3} + 6 p ^{2} v + -4 p v ^{2} + 6 p v - 4 p + v ^{3} - 3 v ^{2} + 2
v\=\NN
\= 
-4{p}^{3}+6v{p}^{2}+ \left( -4{v}^{2}+6v-4 \right) p+{v}^{3}-3
{v}^{2}+2v
=0\;\;\;\;(6)\NN
}
La $(6)$ ammette $v/2$ come radice nell'incognita $p$, quindi dividendo per
$(p-v/2)$ abbiamo:
\eal{&2\pton{p-\frac{v}{2}}
\pton{-2p^2+2vp-v^2+3v-2} =0
}
Vediamo se $-2p^2+2vp-v^2+3v-2$ ammette soluzioni:
\eal{&\frac{\Delta}{4}= v^2+2(-v^2+3v-2)=-v^2+6v-4\NN
\frac{\Delta}{4}=-v^2+6v-4 \ge   0\=
 3-\sqrt{5}  \le v\le  3+\sqrt{5}
 \ubrace{\=}{v=|X|\in \mathbb{N}} 
0\le v\le  \floor{3+\sqrt{5}} = 5\;\;(*)\NN
\H\in \SQS(v)  \ubrace{\>}{\see{thmspettri}}  
v=2,4\;\;\Z_6,\;\;v\ge 4\;\;(**)\NN
(*),(**) \> v=4
}
Ma per ipotesi $v>4$, quindi l'unica radice e' data da
$\pton{p-\frac{v}{2}}$
\end{proof}
\begin{prop}
	Sia $\H=(X,\E)\in S(2,4,v)$.
	\eal{&B\T{ blocking set per } \H,\;\;|B|=p
	\>
	\frac{v-\sqrt{v}}{2} \le p \le \frac{v+\sqrt{v}}{2},\;\;p\in
	\mathbb{N}^{*}
	}
\end{prop}
\begin{proof}
	Analogamente a quando visto in \see{nobsetinSTS}, \see{bsetperSQS},
	si ha
	\eal{& \E_i=\pgra{E\in \E \;|\;\;|B\^E|=i},\;\;i=1,2,3\NN
	\E_i\^\E_j=\0\;\;\forall i \neq j\NN
	\E_1\U\E_2\U\E_3=\E\NN
}
Poniamo
\eal{&x=|\E_1|\NN
y=|\E_2|\NN
z=|\E_3|
}
Cerchiamo adesso di ricavare delle espressioni per $x,y,z$.
\eal{&\pgra{\E_i}_{i=1,2,3}\T{ partizione di }\E \> 
x+y+z=|\E|  \ubrace{=}{\see{cardESlambdahrv} }
	 \frac{v!(4-2)!}{4!(v-2)!}
	 = \frac{v(v-1)}{12}\;\;(1)
}
Abbiamo:
\eal{&
T\in \P_2(B)  \ubrace{\>}{\H\in S(2,4,v)} 
\exists !  E\in \E=\E_1\U\E_2\U\E_3:\;\;T\(E  \NN
|T|=2,\;T\(B \> |E\^B| \ge 2 \> E\in \E_2\U\E_3\NN
\qq \forall T\in \P_2(B)\;\exists !E\in \E_2\U\E_3:\;\;T\in \P_2( E\^B)\NN
\T{Viceversa }, E\in \E_2\U\E_3 \> \exists T\in \P_2(E\^B) \(\P_2(B)\NN
\T{esiste quindi una biezione tra } \P_2(B),\;\bigcup_{E\in
\E_2\U\E_3}\P_2(E\^B) \> \NN
\> \binom{|B|}{2} =\pass{\bigcup_{E\in
\E_2\U\E_3}\P_2(E\^B)}\;\;
\ubrace{=}{\H\in S(2,4,v)\>\P_2(E)\^\P_2(E')=\0\;\;\forall E \neq
E',\;\;E,E'\in \E}\;\;
\sum_{E\in \E_2\U\E_3} \binom{|E\^B|}{2}  =\NN
\ubrace{=}{\E_2\^\E_3=\0} 
\sum_{E\in \E_2} \binom{|E\^B|}{2} +
\sum_{E\in \E_3} \binom{|E\^B|}{2}
= 
\sum_{E\in \E_2} \binom{2}{2} +
\sum_{E\in \E_3} \binom{3}{2}
= |\E_2|+|\E_3|3 = 3z+y \= \NN
\= \binom{|B|}{2} = 3z+y  \=p(p-1) =6z+2y\;\;(1)
}
Analogamente, considerando la biezione tra
\eal{&\P_2(X\-B)\T{ e } \bigcup_{E\in \E_2\U\E_1}\P_2(E\^(X\-B)) 
}
abbiamo:
\eal{& \binom{|X\-B|}{2} = 3x+y\= (v-p)(v-p-1)=6x+2y\;\;(3)
}
In definitiva, dalla $(1),(2),(3)$ abbiamo il seguente sistema:
\eal{&\sist{
	 x+y+z=  \frac{v(v-1)}{12}\\
	 6z+2y=p(p-1)\\
	 6x+2y=(v-p)(v-p-1)
}
}
che risolto da':
\eal{&z=
\frac{1}{12}{v}^{2}-\frac{1}{3}vp-\frac{1}{12}v-\frac{1}{6}p+\frac{1}{2}{p}^{2}\NN
y=
-\frac{1}{4}{v}^{2}+vp+\frac{1}{4}v-{p}^{2}\;\;(4)\NN
x=
\frac{1}{2}{p}^{2}+\frac{1}{4}{v}^{2}-\frac{2}{3}vp-\frac{1}{4}v+\frac{1}{6}p
}
Poiche' $y =|\E_2| \ge 0$, si deve avere:
\eal{&y\ge 0 \ubrace{\=}{(4)} 
\frac{v-\sqrt {v}}{2}\le p\le \frac{v+\sqrt {v}}{2}
}
\end{proof}
\begin{thm}
	Sia $\H\in S(2,4,v)$,
	\eal{&v=1\;\Z_{12} \> p=\frac{v\pm 1}{2}\NN
	v=4\;\Z_{12} \> p =\frac{v}{2}  \|  p\T{ e' dispari}
	}
\end{thm}
\begin{proof}
	DA VERIFICARE!
\end{proof}

\section{Disposizioni vincolate}
\def\k{{\uline{k}}}
\begin{defn}
Sia dato un insieme $X$ di $n$ elementi e, fissato $k\le n$, sia 
\eal{&D(X,k,E)=\pgra{\ove x\in X^k\;|\; \pgra{i,j}\in E \> x_i \neq x_j}
}
dove $E$ e' un qualsiasi sottoinsieme $E\(\P_2(\pgra{1,2,\dots,k})$.
In altre parole, $E$ specifica quali posti dei vettori di $D$ devono essere
distinti.\\
Chiameremo $D(X,k,E)$ l'insieme di tutte le k-disposizioni di $X$ vincolate a
$E$.\\

Per convenienza, poniamo $\k=\pgra{1,2,\dots,k}$
\end{defn}
\begin{exemp}
	Scegliendo $X=\pgra{a,b,c}$, $k=2$,
$E=\pgra{\pgra{1,2}}$, abbiamo che 
\eal{&(a,b,c),\;(a,c,b),\;(b,a,c),\;(b,c,a),\;(c,b,a) \in D
}
sono elementi di $D$, invece,
\eal{&(a,a,c)\notin D 
}
\end{exemp}
\begin{prop}\label{disposizionivincolatebanali}
	Sia dato $X$ con $|X|=n$,
	\eal{&1.\;\;D(X,k,\P_2(\k))\T{ e' l'insieme di tutte le $k$-disposizioni di
	$X$}\NN
	1.1\;\;\pass{D(X,k,\P_2(\k))}  = \binom{n}{k}k!\NN
	2.\;\;D(X,k,\0) \T{ e' l'insieme di tutte le $k$-disposizioni semplici
	du $X$}\NN
	2.1\;\; \pass{D(X,k,\0)} = n^k
	}
\end{prop}
\def\C{{\mathcal{C}}}
\begin{prop}\label{colorazionidisposizionivincolate}
	Indichiamo con $\C_X(G)$ l'insieme di tutte le colorazioni del grafo
	$G=(V,E)$ utillando i colori $X$, ovvero
	\eal{&f\in \C_X(G) \= f:V\rightarrow X,\;f\T{ colorazione di }G }
	Sia $E\in \P_2(\k)$, con $k\le n=|X|$, allora si ha,
	\eal{&|\C_X((\k,E))| = |D(X,k,E)|
	}
	Ovvero, le colorazioni del grafo $(\k,E)$, tramire i colori $X$, sono
	in biezione con le $k$-disposizioni vincolate a $E$.\\
	
	Quindi, per contare $ |D(X,k,E)| $, basta saper calcolare $|\C_X(G)|$.
\end{prop}
\begin{proof}
	Graficamente e' immediato: basta osservare che il grafo
	$(\k,E)$ stabilisce i vincoli delle disposizioni, ovvero, 
	preso $\ove x\in D$, se $i,j$ sono vertici adiacenti in $(\k,E)$,
	allora si deve avere $x_i \neq x_{j}$. Ma questa condizione e' proprio la
	definizione di colorazione di $(\k,E)$, secondo i colori $X$. Quindi, $\ove x$ e'
	la colorazione:
	\eal{&\ove x:\k \longrightarrow X\NN
		\invisible{\ove x:}i\mapsto x_i
	}
	Viceversa, se abbiamo la colorazione $f:\k\longrightarrow X$, allora
	possiamo porre
	\eal{&\ove x = (f(1),f(2),\dots,f(k)) \in D
	}
\end{proof}
Vediamo adesso come e' possibile calcolare $|\C_X(G)|$.
\begin{prop}\label{CXgrafocompleto}
	Sia $G=(V,E)$ un grafo completo, allora
	\eal{&|\C_X(G)|= \binom{|X|}{|V|}|V|!  
	}
	Ovvero, il numero di colorazioni di un grafo completo con $v$ vertici, tramite
	$t$ colori, e' 
	\eal{& \binom{t}{v}v!
	}
\end{prop}
\begin{proof}
	Per la prop \see{colorazionidisposizionivincolate} si ha
	\eal{&|\C_X((V,E))|= |D(X,|V|,E)|
	}
Inoltre,
\eal{&G\T{ completo} \> E=\P_2(V)\NN
|D(X,|V|,E)| = |D(X,|V|,\P_2(V))|
\ubrace{=}{\see{disposizionivincolatebanali}}  \binom{|X|}{|V|}|V|!
}
	Poiche' il grafo e' completo, tutti i vertici sono adiacenti tra loro,
	quindi per qualsiasi $f\in \C_X(G)$ si deve avere:
	\eal{&f(x) \neq f(y)\;\;\forall x,y\in V:\;x \neq y
	}
\end{proof}

\begin{defn}
	Sia dato un grafo $G=(V,E)$ e siano $x,y\in V$. Definiamo il
	\iemph{grafo di connessione}:
	\eal{&G_{xy} = (V, E\U\pgra{\pgra{x,y}})
	}
	$G_{xy}$ e' il grafo $G$ in cui i vertici $x,y$ sono adiacenti, in $G$ potevano non
	esserlo.

	Definiamo il \iemph{grafo di contrazione}:
	\eal{&G_{x=y} =G/_{\sim}\NN
	\T{dove $\sim$ e' la seguente relazione d'equivalenza: }
	\sim = \pgra{(x,y),\;(y,x)}\U\pgra{(z,z)\;|\;z\in V\-\pgra{x,y}}
	}
 $G_{x=y}$ e' il grafo $G$ in cui i vertici $x,y$ sono stati identificati come
 un unico vertice.
\begin{center}
	\includegraphics[scale=0.5]{fig/tmp.52UkaK4cO7/out1}
\end{center}
\end{defn}

\begin{prop}\label{numerocolorazioni}
Sia $G=(V,E)$ un grafo e siano $x,y\in G$ due vertici non adiacenti, allora
\eal{&|\C_X(G)| = |\C_X(G_{xy})|+|\C_{X}(G_{x=y})|
	}
\end{prop}
\begin{proof}
	Sia $f\in \C_X(G)$, poiche' $x,y$ non sono adiacenti, si possono avere
	due casi
	\case{$f(x)=f(y)$}
	\begin{prova}
		In questo caso, $f\in \C_X(G_{x=y})$
	\end{prova}
	\case{$f(x) \neq f(y)$}
	\begin{prova}
		In questo caso, possiamo connettere $x,y$ e $f$ sara' ancora
		una colorazione valida: $f\in \C_X(G_{xy})$
	\end{prova}
	Quindi,
	\eal{&\C_X(G)= \C_X(G_{xy})\U \C_{X}(G_{x=y})
	}
	(nota\footnote{stiamo considerando gli elementi di $\C_{X}(G_{x=y})$
	come delle colorazioni di $G$ che assegnano lo stesso colore a $x$ e
	$y$.})
	Inoltre, \eal{&
	f\in \C_X(G_{xy})  \ubrace{\=}{\pgra{x,y}\in E}  f(x) \neq f(y) \=
	f\notin \C_{X}(G_{x=y})\NN
	\qq \> \C_X(G_{xy})\^ \C_{X}(G_{x=y})=\0
	}
	In conclusione:
	\eal{&|\C_X(G)|=  |\C_X(G_{xy})|+|\C_{X}(G_{x=y})|
	}
\end{proof}
\begin{prop}\label{completoricursivo}
	Consideriamo la seguente procedura:
	\eal{&1.\;\;\T{Sia $G=(V,E)$ un grafo}\NN
	2.\;\;\T{Se $G$ e' un grafo completo, allora fermati}\NN
	3.\;\;\T{Siano $x,y\in V$ vertici non adiacenti }\NN
	4.\;\;\T{Poni $G:=G_{xy}$ oppure $G:=G_{x=y}$}\NN
	5.\;\;\T{Continua dal punto $1.$}
	}
	La procedura termina in un numero finito di passi.
\end{prop}
\begin{proof}
	Supponiamo che inizialmente $G$ non sia completo, ovvero, i seguenti
	spigoli 
	\eal{&
	\pgra{x_{1},y_{1}} \notin E \NN
	\pgra{x_{2},y_{2}} \notin E\NN
	\vdots\NN
	\pgra{x_{h},y_{h}} \notin E
	}
	non stanno in $E$.\\
	Nel passo $4.$ viene scelta una coppia $\pgra{x_{m},y_{m}}$ e
	viene aggiunta nel nuovo $E$ ($G:=G_{x_{m},y_{m}}$), oppure viene eliminata da
	$\P_{2}(V)$ perche' $x_{m},y_{m}$ vengono identificati in
	$G_{x_m=y_m}$. In ogni caso, $\P_{2}(V)\-E$ diventa strettamente piu'
	piccolo, quindi prima o poi, dovra' essere
	\eal{&\P_{2}(V)\-E=\0
	}
	ovvero
	\eal{&E=\P_2(V)}
	e quindi $G$ sara' un grafo completo.
\end{proof}
\begin{rem}
La procedura precedente puo' essere utilizzata per calcolare tutte le
possibili colorazioni, e quindi anche il numero cromatico. Infatti, la scelta
$G:=G_{x=y}$ corrisponde a dare lo stesso colore sia a $x$ che $y$, la scelta
$G:=G_{xy}$ corrisponde a dare colori distinti a $x$ e $y$. Quando si arriva a
un grafo completo, si ha una fissata colorazione. Da questa si devono
considerare anche le colorazioni isomorfe.\\
Compiendo ad ogni iterazione tutte le possibili scelte, ($G_{x=y}$ oppure
$G_{xy}$), si ottengono tutti i possibili grafi completi che corrispondono a
tutte le colorazioni non isomorfe tra loro.
\end{rem}
\begin{prop}
	Utilizzando le proposizioni \see{numerocolorazioni},
	\see{completoricursivo}, \see{CXgrafocompleto} e' possibile calcolare
	$|\C_X(G)|$, per qualunque grafo $G$:
	\begin{enumerate}
		\item Si utilizza ricursivamente la formula
			\see{numerocolorazioni}. La procedura di ricorsione
			dovra' arrestarsi per la  \see{completoricursivo}.
		\item La formula cosi' ottenuta sara' del tipo:
		\eal{&
		|\C_X(G)|=
		|\C_X(G_1)|+
		|\C_X(G_2)|+\dots+
		|\C_X(G_m)|
			}
			dove $G_i$ sono tutti grafi completi.
		\item  Per la prop \see{CXgrafocompleto} sara' quindi
			possibile calcolare esplicitamente ogni $|\C_X(G_i)|$
	\end{enumerate}
\end{prop}
\begin{prop}\label{colorazionialbero}
	Sia $G=(V,E)$ un albero, ovvero un grafo connesso privo di cicli, con $|V|=v$,
	$|X|=t$, allora 
	\eal{&|\C_X(G)|=t(t-1)^{v-1}
	}
	Vale anche il vicersa: se $|\C_X(G)|=t(t-1)^{v-1}$  allora $G$ e' un
	albero.
\end{prop}
\begin{proof}
	Per induzione su $v$.
	\case{$v=1$}
	\begin{prova}
		Il grafo e' formato da un solo vertice, a cui possiamo
		assegnare $t$ colori differenti.
	\end{prova}
	\case{$v>1$, $v\>v+1$}
	\begin{prova}
		Poiche' $G$ e' un albero, esiste almeno un vertice $x\in V$ di
		grado $1$, ovvero adiacente ad un solo altro vertice $y$. Allora,
		il grafo $G_{x=y}$ e' ancora un albero (e' come se avessimo
		rimosso il vertice $x$). Per Hp induttiva si ha:
		\eal{&|\C_X(G_{x=y})|=t(t-1)^{v-1}
		}
		Per avere un colorazione di $G$, basta prendere una
		colorazione $f\in \C_X(G_{x=y})$ e associare un qualsiasi colore a $x$,
		cioe' fissare $f(x)$, con l'unica condizione che $f(x) \neq
		f(y)$ (perche' $x,y$ sono adiacenti in $G$).\\
		Viceversa, una colorazione di $G$ si puo' pensare come
		una colorazione di $G_{x=y}$ estesa, come prima, a $x$.\\
		Tutti i colori disponibili per $x$, sotto la condizione $f(x)
		\neq f(y)$, sono in numero $t-1$,
		Quindi
		\eal{&|\C_X(G)| = (t-1)|\C_X(G_{x=y})| = t(t-1)^{(v+1)-1}  
		}
	\end{prova}
	\step{}{Dim. Viceversa}
	\begin{prova}
		DA VERIFICARE!
	\end{prova}
\end{proof}

\begin{prop}
Sia $G=(V,E)$ un grafo, con $|V|=v$, e sia $|X|=t$, allora
\eal{&|\C_X(G)|
}
si puo' esprimere come un polinomio $P(t)$ nella variabile $t$, e valgono le seguenti
proprieta':
\eal{&1.\;\;P(t)=t^v-mt^{n-1}+a_2t^{n-2}+\dots+a_{\crom}t^{\crom}\NN
2.\;\;P(t)=0\;\;\forall t=0,1,\dots,\crom-1\NN
3.\;\;a_{i}a_{i+1}<0\;\;\forall i=1,2,\dots,\crom-1
}
dove $m=|E|$, e $\crom $ e' il numero cromatico di $G$
\end{prop}
\begin{proof}
	\step{}{$|\C_X(G)| $ e' un polinomio in $t$}
	\begin{prova}
		DA VERIFICARE!
	\end{prova}
	\step{}{Dim. 1.}
	\begin{prova}
		DA VERIFICARE!
	\end{prova}
	\step{}{Dim 2.}
	\begin{prova}
		Se $i<\crom$, allora per definizione di $\crom$, non esistono
		colorazioni di $G$ con $i$ colori, quindi
		\eal{&P(i)=|\C_X(G)|=0
		}
	\end{prova}
	\step{}{Dim. 3.}
	\begin{prova}
		DA VERIFICARE!
	\end{prova}
\end{proof}
\begin{prop}
	Sia $C_n=(V,E)$ un ciclo, ovvero un grafo connesso regolare di grado
	2, con $|V|=n>1$, e sia $|X|=t$, allora
	\eal{&|\C_X(C_n)| = (t-1)^n +(-1)^n(t-1)
	}
\end{prop}
\begin{proof}
	Sia $V=\pgra{v_1,\dots,v_n}$ e consideriamo l'albero $A$ ottenuto da
	$C_n$ rimuovendo lo spigolo $\{v_1,v_n\}$, ovvero
	$A=(V,E\-\pgra{v_1,v_n})$. Da $A_n$, adoperando la contrazione e
	connessione abbiamo (vedi anche figura):
	\eal{&A_{v_1v_n} = C_n\NN
	A_{v_1=v_n}=C_{n-1}
	}
\begin{center}
	\includegraphics[scale=0.5]{fig/tmp.ex78VersnH/out1}
\end{center}
	dove $C_{n-1}$ e' un ciclo di $n-1$ nodi.
	Quindi, per la prop \see{numerocolorazioni}, si ha
	\eal{&|\C_X(A)| = |\C_X(C_n)| + |\C_X(C_{n-1})| \;\;(1)
	}
	Inoltre, per la \see{colorazionialbero}, abbiamo
	\eal{&|\C_X(A)|= t(t-1)^{n-1}\;\;(2)
	}
	Posto $a_n=|\C_X(C_n)|$, dalla $(1),(2)$, si ha
	\eal{&a_n=t(t-1)^{n-1} -a_{n-1} \;\;(3)\NN
	a_2=|\C_{X}(C_2)|  \ubrace{=}{C_2\T{ e' un albero con due nodi}} 
	t(t-1)\NN
	a_n=t(t-1)^{n-1} - \pton{
	t(t-1)^{n-2} -
	\pton{t(t-1)^{n-3} -
	\pton{\dots -\pton{t(t-1)^{2} -\ubrace{a_{2}}{=t(t-1)}
	}}
	}
	}
	= \sum_{i=1}^{n-1} (-1)^{i+1}t(t-1)^{n-i} 
	}
%	Per induzione dimostriamo che $a_n=(t-1)^n +(-1)^n(t-1)$
%	\eal{&n=2:\NN
%	\qq \sum_{i=1}^{2-1} (-1)^{i+1}t(t-1)^{2-i}
%	= t(t-1) \NN
%	\qq (t-1)^2 +(-1)^2(t-1) = (t-1)^2+(t-1)=(t-1)((t-1)+1)= t(t-1)\NN
%	n\> n+1:\NN
%	\qq  \sum_{i=1}^{n} (-1)^{i+1}t(t-1)^{n+1-i}
%	= 
%	}
	Per induzione dimostriamo che $a_n=(t-1)^n +(-1)^n(t-1)$:
	\eal{&n=2:\NN
	\qq a_2 \ubrace{=}{C_2\T{ e' un albero }} = t(t-1)\NN
	\qq (t-1)^2 +(-1)^2(t-1) = (t-1)^2+(t-1)=(t-1)((t-1)+1)= t(t-1)\NN
	n\>n+1:\NN
	\qq 
	a_{n+1}=t(t-1)^{n} -a_{n} 
	\ubrace{=}{\T{Hp induttiva}} 
	t(t-1)^{n} -\pton{(t-1)^n +(-1)^n(t-1)}
	= (t-1)^{n}(t-1) - (-1)^n(t-1)=\NN
	= (t-1)^{n+1}+(-1)^{n+1}(t-1)
	}
\end{proof}

%%%%%%%
\printindex
\end{document}