Tesis para optar al grado de Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / The main focus of this thesis is the study of monochromatic cycle partitions in uniform hypergraphs. The first part deals with Berge-cycles. Extending a result of Rado to hypergraphs, we prove that for all $r,k \in \N$ with $k \geq 2$, the vertices of every $r(k-1)$-edge-coloured countably infinite complete $k$-uniform hypergraph can be core-partitioned into at most $r$ monochromatic Berge-cycles of different colours. We further describe a construction showing that this result is best possible. The second part deals with $\ell$-cycles. We show that for all $\ell, k, n \in \N$ with $\ell \leq k/2$ the following hypergraph-variant of Lehel's conjecture is true. Every $2$-edge-colouring of the $k$-uniform complete graph on $n$ vertices has at most two disjoint monochromatic $\ell$-cycles in different colours that together cover all but a constant number of vertices, where the constant depends on $k$ and $\ell$. Furthermore, we can cover all vertices with at most $4$ ($3$ if $\ell \leq k/3$) disjoint monochromatic $\ell$-cycles. The third part deals with tight-cycles in $2$-edge-colourings of complete $3$-uniform hypergraphs. We show that for every $\eta > 0$ there exists an integer $n_0$ such that every $2$-edge-colouring of the $3$-uniform complete hypergraph on $n \geq n_0$ vertices contains two disjoint monochromatic tight cycles of distinct colours that together cover all but at most $\eta n$ vertices. Finally, the fourth part deals with tight-cycles in a more general setting. We prove that for every $k,r \in \N$, the vertices of every $r$-edge-coloured complete $k$-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles, confirming a conjecture of Gy\'arf\'as. We further prove that for every $r,p \in \N$, the vertices of every $r$-edge-coloured complete graph can be partitioned into a bounded number of $p$-th powers of cycles, settling a problem of Elekes, D. Soukup, L. Soukup and Szentmikl\'ossy. In fact we prove a common generalisation of both theorems which further extends these results to all host hypergraphs with bounded independence number. / CONICYT/Doctorado Nacional/2014-21141116, CMM-Conicyt PIA AFB170001

Ingeniero Civil Matemático / La presente memoria tiene como objetivo un estudio general sobre componentes monocromáticas en multicoloreos de aristas de grafos completos, o dicho de otro modo, un coloreo de aristas de multigrafos completos. En particular, el tema de mayor importancia consiste en una generalización de una importante clase de problemas relacionados con la Conjetura de Ryser, la cual habla de una cota universal para el número de componentes conexas monocromáticas necesarias para cubrir todos los vértices de un grafo con sus aristas coloreadas, y donde tal cota solo depende del número de colores utilizados. Los resultados presentes en la memoria son fruto de distintas formas de abordar determinados problemas relacionados con la generalización mencionada y que, por fortuna, resultaron no solo ser útiles para los propósitos para los que fueron ideados, sino que algunos de ellos poseen interés por sí mismos. En primer lugar el motivo de estudio se centra en la cantidad de vértices que podemos asegurar para alguna de las componentes monocromáticas inducidas en un multicoloreo de aristas arbitrario en grafos bipartitos, para luego extender el resultado a grafos completos. Posteriormente se estudia una cota de vértices para multicoloreos de grafos tales que pueden ser cubiertos con tres componentes conexas monocromáticas y no pueden ser cubiertos con dos componentes conexas monocromáticas, pero si aislamos cualquiera de sus vértices entonces el resto de ellos pueden ser cubiertos por dos componentes monocromáticas. Este tipo de multicoloreos será llamado 3-crítico. Finalmente se introduce la generalización de un caso particular de la Conjetura de Ryser, que consiste en encontrar cotas, dependientes del número de colores utilizados, para multicoloreos de aristas de grafos completos. En particular, se restringe el estudio para multicoloreos de aristas uniformes, los cuales se definen como multicoloreos donde todas las aristas tienen el mismo número de colores. Primero se muestran cotas superiores generales, luego cotas inferiores, para finalmente estudiar determinados casos de manera particular y concluir cotas de manera estricta.

Made available in DSpace on 2014-06-12T17:40:54Z (GMT). No. of bitstreams: 2 arquivo7085_1.pdf: 5617751 bytes, checksum: 13b747395cadea3f73a525d5b1fd2004 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2005 / A digitalização de documentos originariamente em papel é a maneira mais eficiente que dispomos hoje como meio de preservar o seu conteúdo para as gerações futuras, bem como possibilitar o acesso e disseminação às informações via redes de computadores. A natureza do documento impõe técnicas diferentes para a digitalização e armazenagem destes. Em geral, objetivando possibilidades futuras, os documentos são digitalizados em cores (true color) e alta resolução (chegando hoje até mais de 1.000 pontos por polegada). Visando o acesso via redes, tais documentos são geralmente disponibilizados em sua versão monocromática, com 200 dpi de resolução e comprimidos em formato conveniente, geralmente TIFF (G4). Tal processo de diminuição do número de cores de documentos, no caso de conversão para monocromático conhecido como binarização, possui dificuldades para ser efetuado de maneira automática, caso o documento tenha sido escrito ou impresso em ambos os lados de papel translúcido, situação conhecida como interferência frenteverso. Os algoritmos de binarização hoje existentes nas ferramentas comerciais geram imagem onde as porções referentes à tinta na frente e no verso ficam sobrepostas, impossibilitando a leitura da imagem obtida. Embora tal problema tenha sido apresentado há mais de uma década, ainda hoje busca-se soluções melhores para ele. No caso de documentos históricos, a complexidade do problema é ainda maior, uma vez que há o escurecimento causado pelo envelhecimento do papel como fator complicador. Esta dissertação propõe um novo algoritmo baseado na entropia do histograma da imagem para a binarização da imagem de documentos históricos com interferência frente-verso. O algoritmo proposto é comparado com os seus antecessores descritos na literatura, gerando imagens de melhor qualidade que os seus congêneres

Submitted by Eduarda Figueiredo (eduarda.ffigueiredo@ufpe.br) on 2015-03-06T13:53:56Z No. of bitstreams: 2 Dissertação Ednardo Jerônimo Mariano.pdf: 6874063 bytes, checksum: 791258ac65e7483a77dc6e6d559019f6 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-06T13:53:56Z (GMT). No. of bitstreams: 2 Dissertação Ednardo Jerônimo Mariano.pdf: 6874063 bytes, checksum: 791258ac65e7483a77dc6e6d559019f6 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-01-31 / A digitalização de grandes quantidades de documentos através de scanners de linha de produção geralmente incorpora na imagem defeitos que acarretam dificuldades desde a sua leitura até sua transcrição automática. Tais defeitos devem ser removidos, obtendo imagens de documentos com melhor qualidade, através de técnicas de processamento de imagens digitais. Devido à grande quantidade de documentos, essas técnicas devem ser rápidas e capazes de abranger a maior parte das falhas nessas imagens. Esta dissertação apresenta um novo algoritmo para remoção de bordas ruidosas cujo tempo de processamento chegou a ser reduzido em até 62% em relação ao algoritmo de Ávila-Lins, com qualidade semelhante, quando testado num conjunto de cinco mil imagens.