Ricardo A. Sáenz

Fecha de entrega: 4 de mayo Problema 1 Muestra que, si  G tiene un apareamiento perfecto, entonces todo apareamiento maximal (en el sentido en que no existen aristas entre U y W libres) usa al menos la mitad de los vértices de  G . Problema 2 Utiliza el algoritmo de trayectorias de aumento para, si es posible, obtener un apareamiento perfecto del siguiente grafo. Problema 3 Averigua si el siguiente grafo tiene un apareamiento perfecto. Problem 4 Dadas al menos 3 rectas genéricas en el plano, muestra que entre las regiones en que dividen al plano se encuentra al menos un triángulo. Problema 5 ¿En cuántas regiones dividen al plano dos  n -ágonos convexos? Problema 6 ¿Cuál es el mínimo y el máximo número de regiones en que dividen al plano  n círculos? Problema 7 Muestra que 6 puntos genéricos en el plano forman al menos 3 cuadriláteros convexos. Encuentra 8 puntos genéricos en el plano que no contienen un pentágono convexo.

Due May 4 Problem 1 Let  X be a set and $latex \mathcal M$ a nonempty collection of subsets of  X  closed under complements and countable unions of disjoint sets. Then $latex \mathcal M$ is a $latex \sigma$-algebra. Problem 2 Let $latex (X,\mathcal M, \mu)$ be a measure space. Its  completion is defined as the collection $latex \overline{\mathcal M}$ of sets of the form $latex E\cup N$, where $latex E\in\mathcal M$ and $latex N\subset F$ for some $latex F\in\mathcal M$ with $latex \mu(F)=0,$ and $latex \bar\mu(E\cup N) = \mu(E).$ $latex \overline{\mathcal M}$ is the smallest $latex \sigma$-algebra containing $latex \mathcal M$ and all subsets of its elements of measure 0. The function $latex \bar\mu$ is a complete measure on $latex \overline{\mathcal M}$. Problem 3 Consider the Lebesgue exterior measure. Then a set is Caratheodory measurable if and only if is Lebesgue measurable. Problem 4 Let $latex (X,\mathcal M,\mu)$ be a measure space, $latex A,B,C$ subsets of  X such that $...

Due April 27 Problem 1 Let $latex f\in L^2(\R^d), k\in L^1(\R^d)$. $latex \displaystyle (f*k)(x) = \int_{\R^d} f(x-y)k(y) dy$ converges for a.e.  x . $latex ||f*k||_{L^2} \le ||f||_{L^2} ||k||_{L^1}$. $latex \widehat{(f*k)}(\xi) = \hat k(\xi) \hat f(\xi)$ for a.e. $latex \xi$. The operator $latex Tf = f*k$ is a Fourier multiplier operator with multiplier $latex m(\xi) = \hat k(\xi)$. Problem 2 Let $latex \Omega\subset\C$ be open, and $latex \mathscr H\subset L^2(\Omega)$ be the subspace of holomorphic functions on $latex \Omega$. $latex \mathscr H$ is a closed subspace of $latex L^2(\Omega)$. If $latex \{\phi_k\}$ is an orthonormal basis of $latex \mathscr H$, then $latex \displaystyle \sum_k |\phi_k(z)|^2 \le \frac{1}{\pi d(z,\C\setminus\Omega)}$ for $latex z\in\Omega$, where $latex d(z,\C\setminus\Omega)$ is the distance from  z to the complement of $latex \Omega$. The sum $latex B(z,w) = \sum_k \phi_k(z)\overline{\phi_k(w)}$ converges absolutely for $latex z,w\in\Omeg...

Fecha de entrega: 27 de abril Problema 1 Muestra que, si los costos de todas las aristas son distintos, entonces hay un único árbol más barato. Problema 2 Describe cómo construir árboles para los cuales: el producto del costo de sus aristas es mínimo; el máximo costo de sus aristas es mínimo. Problema 3 Si la capital de un gobierno se encuentra en el vértice  r , la primer línea construida será la línea más barata que sale de  r , digamos, a  s . Después, construiremos la línea más barata que sale de  r o de  s , y así sucesivamente. Muestra que el árbol que resulta es, de nuevo, el más barato. Problema 4 Muestra que un árbol es un grafo bipartito. ¿Es cierto que todo grafo bipartito es un árbol? Problema 5 ¿Existe un grafo bipartito con vértices de grados 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 6 y 6? Un grafo bipartito tiene 16 vértices de grado 5 y cierto número de vértices de grado 8. Si sabemos que los vértices de grado 8 se encuentran en el mismo lado, ¿cuántos vértices de gra...

Fecha de entrega: 20 de abril Problema 1 Encuentra el número de árboles no etiquetados con 6 vértices. Encuentra el número de estrellas etiquetadas con  n vértices Problema 2 Considera una matriz de $latex 2\times n-1$, cuyo primer renglón está formado por los números del 1 al $latex n-1$, y el segundo por números arbitrarios entre 0 y $latex n-1$. Construye el grafo con vértices $latex 0,1,2\ldots,n-1$ y aristas descritas por las columnas de esta matriz. Muestra que este grafo no siempre es un árbol. Demuestra que, si este grafo es conexo, entonces es un árbol. Muestra que cada componente conexa tiene a lo más un ciclo. Problema 3 Construye los árboles descritos por las siguientes codificaciones de Prüfer . 4330 105200 444440 169767620 4266410 Problema 4 Construye los árboles descritos por las siguientes codificaciones planares 11110000 11100100 11010100 11010010 11001010  

Due April 20 Problem 1 Let $latex \{\phi_k\}_{1\le k<\infty}$ be a complete orthonormal system for $latex L^2(\R^d)$. Then $latex \{\phi_{k,j}\}_{1\le k,j < \infty}$ a complete orthonormal system for $latex L^2(\R^d\times\R^d)$, where $latex \phi_{k,j}(x,y) = \phi_k(x)\phi(y)$. Problem 2 Let  P be the orthogonal projection onto a closed subspace  S of a Hilbert space. Then $latex P^2 = P\text{ and } P^*=P$. Conversely, if  P is a bounded operator such that $latex P^2 = P$ and $latex P^*=P$, then it is the orthogonal projection onto some closed subspace. Let $latex P_1\text{ and }P_2$ be the orthogonal projections onto the closed subspaces $latex S_1\text{ and }S_2$, respectively. Then $latex P_1P_2$ is an orthogonal projection if and only if they conmute, in that case, it projects onto $latex S_1\cap S_2$. Problem 3 Let $latex \{u_k\}$ be a complete orthonormal system for a Hilbert space  H , and $latex (a_k)$ a sequence of positive numbers such that $latex \sum_k a_k^2 ...

Fecha de entrega: 13 de abril Problema 1 Demuestra que al conectar dos vértices  u  y  v  en un grafo  G  con una nueva arista, se crea un nuevo ciclo si y solo si  u  y  v  se encuentran en la misma componente conexa de  G . Problema 2 Sea  G  un grafo conexo y  e  una arista de  G . Muestra que  e  no es una arista de corte si y solo si  e  es parte de un ciclo en  G . Problema 3 Determina cuáles de los siguientes 4 grafos tienen una caminata euleriana, y cuáles una caminata euleriana cerrada. Dibújala, si es el caso. Problema 4 Determina cuáles de los siguientes 2 grafos tienen un ciclo hamiltoniano. Problema 5 Muestra que, en un árbol, cualquiera dos vértices pueden ser conectados por una única trayectoria. De manera inversa, muestra que si en un grafo cualquiera dos vértices pueden ser conectados por una única trayectoria, entonces el grafo es un árbol.   Problema 6 Muestra que un árbol con un vértice de grado  d  tiene al menos  d hojas.