¿Cuál es el trabajo y

Question

Unos 4 minutos en su video sobre acordes gráficos, Donald Knuth menciona una variante de la función de Möbius para gráficos. ¿Era curioso lo que entiende fuera del contexto de teoría de números?

Answer 1

La función de Möbius en la teoría de los números, aunque más antiguo, es en realidad un caso especial de una noción más general de la función de Möbius. Si $\langle P,\preceq\rangle$ es un poset, un intervalo cerrado de a $P$ es un conjunto de la forma

$$[a,b]=\{x\in P:a\preceq x\preceq b\}\;;$$

$P$ es localmente finito si cada uno de sus cerrado intervalos es finito. Deje $\mathscr{I}$ el conjunto de no-vacío cerrado intervalos de $P$, y fijar un anillo conmutativo $R$ con la unidad, el anillo de escalares; $\mathscr{I}$ $R$ en conjunto dan lugar a una incidencia de álgebra $A$ cuyos elementos son las funciones de $f:\mathscr{I}\to R$. Para $f,g\in A$ $r\in R$ suma $f+g$ y escalar múltiples $rf$ se definen pointwise en la manera obvia; un producto se define por

$$(f\mathrel{*}g)\big([a,b]\big)=\sum_{a\preceq x\preceq b}f\big([a,x]\big)g\big([x,b]\big)\;.$$

$A$ tiene una identidad multiplicativa $\delta$:

$$\delta\big([a,b]\big)=\begin{cases} 1,&\text{if }a=b\\ 0,&\text{otherwise}\;. \end{casos}$$

Finalmente, $A$ tiene una función de Möbius $\mu$, que se puede definir de forma recursiva de la siguiente manera:

$$\mu\big([a,b]\big)=\begin{cases} 1,&\text{if }a=b\\ -\sum\limits_{a\preceq x\prec b}\mu\big([a,x]\big),&\text{if }a\prec b\\ 0,&\text{otherwise}\;. \end{casos}$$

Si $P=\Bbb Z^+$ $\preceq$ $\mid$ ('divide'), $\mu\big([m,n]\big)$ resulta ser el número de la teoría de la $\mu\left(\frac{n}m\right)$. Encontrará otros ejemplos en el enlace que figura más arriba. Este PDF da más detalles, pero es todavía muy elementales. Richard P. Stanley notas "Una Introducción a la Hyperplane Arreglos', que se puede encontrar aquí, introduce también el general de Möbius función como parte de una maquinaria en general, una aplicación de la que es cordal gráficos (bajo el nombre de supersolvable gráficos).

Answer 2

Hay una Moebius función definida en cualquier conjunto parcialmente ordenado. La teoría del número uno es la función asociada a el conjunto formado por los enteros no negativos, parcialmente ordenado por la divisibilidad. Para más detalles desde este punto de vista, ver, .e.g., http://en.wikipedia.org/wiki/Incidence_algebra o http://www.sfu.ca/~mdevos/notas/comb_struct/mobius.pdf

No tengo tiempo para ir a través de Knuth de la conferencia, así que no puedo estar seguro de lo que de orden parcial que él está utilizando.