Una caratterizzazione delle indicizzazioni quando il source è lineare

Problemi enumerativi, teoria dei grafi ...

Moderatore: Moderatori

Una caratterizzazione delle indicizzazioni quando il source è lineare

Messaggioda salvo.tringali il gio 4 dic 2014, 23:09

Siano $\mathcal X = (X, \le_X)$ un preset lineare finito (i.e., se $x,y \in X$ allora $x \le_X y$ oppure $y \le_X x$) e $\mathcal Y = (Y, \le_Y)$ un preset finito. Quindi sia $\mathbf a$ una funzione $X \to \mathfrak P(Y)$ da $X$ alle parti di $Y$. Diciamo che $\mathbf a$ è una funzione di indicizzazione da $\mathcal X$ in $\mathcal Y$ se esiste un'altra funzione $\alpha: X \to Y \cup \{\infty\}$, con $\infty \notin Y$, tale che, per ogni $x \in X$, $\alpha(x)$ sia un elemento $\le_Y$-minimale di $\mathbf a(x) \setminus \{\alpha(\xi): \xi <_X x\}$.

Provate che $\mathbf a$ è una funzione di indicizzazione da $\mathcal X$ in $\mathcal Y$ sse per ogni $S \subseteq X$ risulta $|\{\mathbf a(x): x \in S\}| \le \big|\bigcup_{x \in S} \mathbf a(x)\big|$.
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5354
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)

Torna a Combinatoria

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti

cron