Equações de diferenças: aplicações no ensino médio

Pós-graduação em Matemática em Rede Nacional - IBILCE

A note on permutation regularity

The existence of a small partition of a combinatorial structure into random-like subparts, a so-called regular partition, has proven to be very useful in the study of extremal problems, and has deep algorithmic consequences. The main result in this direction is the Szemeredi Regularity Lemma in graph theory. In this note, we are concerned with regularity in permutations: we show that every permutation of a sufficiently large set has a regular partition into a small number of intervals. This refines the partition given by Cooper (2006) [10], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important role in the study of convergence of a permutation sequence. (C) 2011 Elsevier B.V. All rights reserved.

Lindelof spaces which are indestructible, productive, or D

We discuss relationships in Lindelof spaces among the properties "indestructible". "productive", "D", and related properties. (C) 2011 Elsevier B.V. All rights reserved.

Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size

Let k and l be positive integers. With a graph G, we associate the quantity c(k,l)(G), the number of k-colourings of the edge set of G with no monochromatic matching of size l. Consider the function c(k,l) : N --> N given by c(k,l)(n) = max {c(k,l)(G): vertical bar V(G)vertical bar = n}, the maximum of c(k,l)(G) over all graphs G on n vertices. In this paper, we determine c(k,l)(n) and the corresponding extremal graphs for all large n and all fixed values of k and l.

Hypergraphs with many Kneser colorings

For fixed positive integers r, k and E with 1 <= l < r and an r-uniform hypergraph H, let kappa(H, k, l) denote the number of k-colorings of the set of hyperedges of H for which any two hyperedges in the same color class intersect in at least l elements. Consider the function KC(n, r, k, l) = max(H epsilon Hn) kappa(H, k, l), where the maximum runs over the family H-n of all r-uniform hypergraphs on n vertices. In this paper, we determine the asymptotic behavior of the function KC(n, r, k, l) for every fixed r, k and l and describe the extremal hypergraphs. This variant of a problem of Erdos and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erdos-Ko-Rado Theorem (Erdos et al., 1961 [8]) on intersecting systems of sets. (C) 2011 Elsevier Ltd. All rights reserved.

Self-similarities of periodic structures for a discrete model of a two-gene system

We report self-similar properties of periodic structures remarkably organized in the two-parameter space for a two-gene system, described by two-dimensional symmetric map. The map consists of difference equations derived from the chemical reactions for gene expression and regulation. We characterize the system by using Lyapunov exponents and isoperiodic diagrams identifying periodic windows, denominated Arnold tongues and shrimp-shaped structures. Period-adding sequences are observed for both periodic windows. We also identify Fibonacci-type series and Golden ratio for Arnold tongues, and period multiple-of-three windows for shrimps. (C) 2012 Elsevier B.V. All rights reserved.

Rigidity for piecewise smooth homeomorphisms on the circle

We find conditions for two piecewise 'C POT.2+V' homeomorphisms f and g of the circle to be 'C POT.1' conjugate. Besides the restrictions on the combinatorics of the maps (we assume that the maps have bounded combinatorics), and necessary conditions on the one-side derivatives of points where f and g are not differentiable, we also assume zero mean-nonlinearity for f and g.

Die Rolle von Hopfkategorien und Operaden in störungstheoretischen Quantenfeldtheorien

Die Vorhersagen störungstheoretischer Quantenfeldtheorienzeigen eine gute Übereinstimmung mit experimentellgemessenen Werten. Bei diesen störungstheoretischenBerechnungen treten allerdings Ultraviolettdivergenzen auf,die keine physikalische Interpretation der Ergebnisseermöglichen. Durch Renormierung dieser Theorien erhält manjedoch berechnbare Ergebnisse mit hoher experimentellerVorhersagekraft. Der Renormierungsvorgang kann durch eineHopfalgebra, die sogenannte 'Hopfalgebra der Wurzelbäume',beschrieben werden.Die vorliegende Arbeit leistet einen Beitrag für weitereUntersuchungen dieser Hopfalgebrenstruktur und Bestimmungneuer mathematischer Methoden zur Beschreibung desRenormierungsvorgangs. Dazu wird die algebraische Strukturvon Renormierung aus der Sicht der Kategorientheorie und derTheorie von Operaden untersucht.Aus Sicht der Kategorientheorie lassen sich die den Renormierungsprozess beschreibenden mathematischen Größen ineiner Kategorie zusammenfassen. Eine additive Strukturermöglicht dabei die Berücksichtigung beliebigerRenormierungsschemata. Auf dieser Kategorie kann einassoziativitätsverletzendes Produkt definiert werden, wobeidie Verletzung durch einen sogenannten 'Assoziator'kontrolliert werden kann. Die Struktur wird auf die einerHopfkategorie erweitert, so daß eine kategorientheoretischeUntersuchung des Renormierungsprozesses ermöglicht wird.Diese Hopfkategorie wird aus Sicht von Renormierunginterpretiert, wobei Beispielrechnungen die definierteStruktur verdeutlichen.Aus algebraischer Sicht kann aufgrund der graphischenDarstellung des Operadenproduktes eine Bijektivität zwischenWurzelbäumen und Operaden gezeigt werden. Auf diesenOperaden kann wiederum eine Hopfalgebrenstruktur definiertwerden. Beispiele verdeutlichen diese Bijektivität.

Biliardi Circolari con Trappole

Sistemi dinamici.

Geometric and Combinatorial Aspects of NonEquilibrium Statistical Mechanics

Non-Equilibrium Statistical Mechanics is a broad subject. Grossly speaking, it deals with systems which have not yet relaxed to an equilibrium state, or else with systems which are in a steady non-equilibrium state, or with more general situations. They are characterized by external forcing and internal fluxes, resulting in a net production of entropy which quantifies dissipation and the extent by which, by the Second Law of Thermodynamics, time-reversal invariance is broken. In this thesis we discuss some of the mathematical structures involved with generic discrete-state-space non-equilibrium systems, that we depict with networks in all analogous to electrical networks. We define suitable observables and derive their linear regime relationships, we discuss a duality between external and internal observables that reverses the role of the system and of the environment, we show that network observables serve as constraints for a derivation of the minimum entropy production principle. We dwell on deep combinatorial aspects regarding linear response determinants, which are related to spanning tree polynomials in graph theory, and we give a geometrical interpretation of observables in terms of Wilson loops of a connection and gauge degrees of freedom. We specialize the formalism to continuous-time Markov chains, we give a physical interpretation for observables in terms of locally detailed balanced rates, we prove many variants of the fluctuation theorem, and show that a well-known expression for the entropy production due to Schnakenberg descends from considerations of gauge invariance, where the gauge symmetry is related to the freedom in the choice of a prior probability distribution. As an additional topic of geometrical flavor related to continuous-time Markov chains, we discuss the Fisher-Rao geometry of nonequilibrium decay modes, showing that the Fisher matrix contains information about many aspects of non-equilibrium behavior, including non-equilibrium phase transitions and superposition of modes. We establish a sort of statistical equivalence principle and discuss the behavior of the Fisher matrix under time-reversal. To conclude, we propose that geometry and combinatorics might greatly increase our understanding of nonequilibrium phenomena.

Comparing skew Schur functions: a quasisymmetric perspective

Reiner, Shaw and van Willigenburg showed that if two skew Schur functions sA and sB are equal, then the skew shapes $A$ and $B$ must have the same "row overlap partitions." Here we show that these row overlap equalities are also implied by a much weaker condition than Schur equality: that sA and sB have the same support when expanded in the fundamental quasisymmetric basis F. Surprisingly, there is significant evidence supporting a conjecture that the converse is also true. In fact, we work in terms of inequalities, showing that if the F-support of sA contains that of sB, then the row overlap partitions of A are dominated by those of B, and again conjecture that the converse also holds. Our evidence in favor of these conjectures includes their consistency with a complete determination of all F-support containment relations for F-multiplicity-free skew Schur functions. We conclude with a consideration of how some other quasisymmetric bases fit into our framework.

Contribución al estudio del criptoanálisis y diseño de los criptosistemas caóticos

The extraordinary increase of new information technologies, the development of Internet, the electronic commerce, the e-government, mobile telephony and future cloud computing and storage, have provided great benefits in all areas of society. Besides these, there are new challenges for the protection of information, such as the loss of confidentiality and integrity of electronic documents. Cryptography plays a key role by providing the necessary tools to ensure the safety of these new media. It is imperative to intensify the research in this area, to meet the growing demand for new secure cryptographic techniques. The theory of chaotic nonlinear dynamical systems and the theory of cryptography give rise to the chaotic cryptography, which is the field of study of this thesis. The link between cryptography and chaotic systems is still subject of intense study. The combination of apparently stochastic behavior, the properties of sensitivity to initial conditions and parameters, ergodicity, mixing, and the fact that periodic points are dense, suggests that chaotic orbits resemble random sequences. This fact, and the ability to synchronize multiple chaotic systems, initially described by Pecora and Carroll, has generated an avalanche of research papers that relate cryptography and chaos. The chaotic cryptography addresses two fundamental design paradigms. In the first paradigm, chaotic cryptosystems are designed using continuous time, mainly based on chaotic synchronization techniques; they are implemented with analog circuits or by computer simulation. In the second paradigm, chaotic cryptosystems are constructed using discrete time and generally do not depend on chaos synchronization techniques. The contributions in this thesis involve three aspects about chaotic cryptography. The first one is a theoretical analysis of the geometric properties of some of the most employed chaotic attractors for the design of chaotic cryptosystems. The second one is the cryptanalysis of continuos chaotic cryptosystems and finally concludes with three new designs of cryptographically secure chaotic pseudorandom generators. The main accomplishments contained in this thesis are: v Development of a method for determining the parameters of some double scroll chaotic systems, including Lorenz system and Chua’s circuit. First, some geometrical characteristics of chaotic system have been used to reduce the search space of parameters. Next, a scheme based on the synchronization of chaotic systems was built. The geometric properties have been employed as matching criterion, to determine the values of the parameters with the desired accuracy. The method is not affected by a moderate amount of noise in the waveform. The proposed method has been applied to find security flaws in the continuous chaotic encryption systems. Based on previous results, the chaotic ciphers proposed by Wang and Bu and those proposed by Xu and Li are cryptanalyzed. We propose some solutions to improve the cryptosystems, although very limited because these systems are not suitable for use in cryptography. Development of a method for determining the parameters of the Lorenz system, when it is used in the design of two-channel cryptosystem. The method uses the geometric properties of the Lorenz system. The search space of parameters has been reduced. Next, the parameters have been accurately determined from the ciphertext. The method has been applied to cryptanalysis of an encryption scheme proposed by Jiang. In 2005, Gunay et al. proposed a chaotic encryption system based on a cellular neural network implementation of Chua’s circuit. This scheme has been cryptanalyzed. Some gaps in security design have been identified. Based on the theoretical results of digital chaotic systems and cryptanalysis of several chaotic ciphers recently proposed, a family of pseudorandom generators has been designed using finite precision. The design is based on the coupling of several piecewise linear chaotic maps. Based on the above results a new family of chaotic pseudorandom generators named Trident has been designed. These generators have been specially designed to meet the needs of real-time encryption of mobile technology. According to the above results, this thesis proposes another family of pseudorandom generators called Trifork. These generators are based on a combination of perturbed Lagged Fibonacci generators. This family of generators is cryptographically secure and suitable for use in real-time encryption. Detailed analysis shows that the proposed pseudorandom generator can provide fast encryption speed and a high level of security, at the same time. El extraordinario auge de las nuevas tecnologías de la información, el desarrollo de Internet, el comercio electrónico, la administración electrónica, la telefonía móvil y la futura computación y almacenamiento en la nube, han proporcionado grandes beneficios en todos los ámbitos de la sociedad. Junto a éstos, se presentan nuevos retos para la protección de la información, como la suplantación de personalidad y la pérdida de la confidencialidad e integridad de los documentos electrónicos. La criptografía juega un papel fundamental aportando las herramientas necesarias para garantizar la seguridad de estos nuevos medios, pero es imperativo intensificar la investigación en este ámbito para dar respuesta a la demanda creciente de nuevas técnicas criptográficas seguras. La teoría de los sistemas dinámicos no lineales junto a la criptografía dan lugar a la ((criptografía caótica)), que es el campo de estudio de esta tesis. El vínculo entre la criptografía y los sistemas caóticos continúa siendo objeto de un intenso estudio. La combinación del comportamiento aparentemente estocástico, las propiedades de sensibilidad a las condiciones iniciales y a los parámetros, la ergodicidad, la mezcla, y que los puntos periódicos sean densos asemejan las órbitas caóticas a secuencias aleatorias, lo que supone su potencial utilización en el enmascaramiento de mensajes. Este hecho, junto a la posibilidad de sincronizar varios sistemas caóticos descrita inicialmente en los trabajos de Pecora y Carroll, ha generado una avalancha de trabajos de investigación donde se plantean muchas ideas sobre la forma de realizar sistemas de comunicaciones seguros, relacionando así la criptografía y el caos. La criptografía caótica aborda dos paradigmas de diseño fundamentales. En el primero, los criptosistemas caóticos se diseñan utilizando circuitos analógicos, principalmente basados en las técnicas de sincronización caótica; en el segundo, los criptosistemas caóticos se construyen en circuitos discretos u ordenadores, y generalmente no dependen de las técnicas de sincronización del caos. Nuestra contribución en esta tesis implica tres aspectos sobre el cifrado caótico. En primer lugar, se realiza un análisis teórico de las propiedades geométricas de algunos de los sistemas caóticos más empleados en el diseño de criptosistemas caóticos vii continuos; en segundo lugar, se realiza el criptoanálisis de cifrados caóticos continuos basados en el análisis anterior; y, finalmente, se realizan tres nuevas propuestas de diseño de generadores de secuencias pseudoaleatorias criptográficamente seguros y rápidos. La primera parte de esta memoria realiza un análisis crítico acerca de la seguridad de los criptosistemas caóticos, llegando a la conclusión de que la gran mayoría de los algoritmos de cifrado caóticos continuos —ya sean realizados físicamente o programados numéricamente— tienen serios inconvenientes para proteger la confidencialidad de la información ya que son inseguros e ineficientes. Asimismo una gran parte de los criptosistemas caóticos discretos propuestos se consideran inseguros y otros no han sido atacados por lo que se considera necesario más trabajo de criptoanálisis. Esta parte concluye señalando las principales debilidades encontradas en los criptosistemas analizados y algunas recomendaciones para su mejora. En la segunda parte se diseña un método de criptoanálisis que permite la identificaci ón de los parámetros, que en general forman parte de la clave, de algoritmos de cifrado basados en sistemas caóticos de Lorenz y similares, que utilizan los esquemas de sincronización excitador-respuesta. Este método se basa en algunas características geométricas del atractor de Lorenz. El método diseñado se ha empleado para criptoanalizar eficientemente tres algoritmos de cifrado. Finalmente se realiza el criptoanálisis de otros dos esquemas de cifrado propuestos recientemente. La tercera parte de la tesis abarca el diseño de generadores de secuencias pseudoaleatorias criptográficamente seguras, basadas en aplicaciones caóticas, realizando las pruebas estadísticas, que corroboran las propiedades de aleatoriedad. Estos generadores pueden ser utilizados en el desarrollo de sistemas de cifrado en flujo y para cubrir las necesidades del cifrado en tiempo real. Una cuestión importante en el diseño de sistemas de cifrado discreto caótico es la degradación dinámica debida a la precisión finita; sin embargo, la mayoría de los diseñadores de sistemas de cifrado discreto caótico no ha considerado seriamente este aspecto. En esta tesis se hace hincapié en la importancia de esta cuestión y se contribuye a su esclarecimiento con algunas consideraciones iniciales. Ya que las cuestiones teóricas sobre la dinámica de la degradación de los sistemas caóticos digitales no ha sido totalmente resuelta, en este trabajo utilizamos algunas soluciones prácticas para evitar esta dificultad teórica. Entre las técnicas posibles, se proponen y evalúan varias soluciones, como operaciones de rotación de bits y desplazamiento de bits, que combinadas con la variación dinámica de parámetros y con la perturbación cruzada, proporcionan un excelente remedio al problema de la degradación dinámica. Además de los problemas de seguridad sobre la degradación dinámica, muchos criptosistemas se rompen debido a su diseño descuidado, no a causa de los defectos esenciales de los sistemas caóticos digitales. Este hecho se ha tomado en cuenta en esta tesis y se ha logrado el diseño de generadores pseudoaleatorios caóticos criptogr áficamente seguros.

Estudio teórico de propiedades termodinámicas y optoelectronicas de nuevos materiales fotovoltaicos de banda intermedia = Theoretical study of thermodynamic and optoelectronic properties of new intermediate band photovoltaic materials

Los materiales de banda intermedia han atraido la atención de la comunidad científica en el campo de la energía solar fotovoltaica en los últimos años. Sin embargo, con el objetivo de entender los fundamentos de las células solares de banda intermedia, se debe llevar a cabo un estudio profundo de la características de los materiales. Esto se puede hacer mediante un modelo teórico usando Primeros Principios. A partir de este enfoque se pueden obtener resultados tales como la estructura electrónica y propiedades ópticas, entre otras, de los semiconductores fuertemente dopados y sus precursores. Con el fin de desentrañar las estructuras de estos sistemas electrónicos, esta tesis presenta un estudio termodinámico y optoelectrónico de varios materiales fotovoltaicos. Específicamente se caracterizaron los materiales avanzados de banda intermedia y sus precursores. El estudio se hizo en términos de caracterización teórica de la estructura electrónica, la energética del sistema, entre otros. Además la estabilidad se obtuvo usando configuraciones adaptadas a la simetría del sistema y basado en la combinatoria. Las configuraciones de los sitios ocupados por defectos permiten obtener información sobre un espacio de configuraciones donde las posiciones de los dopantes sustituidos se basan en la simetría del sólido cristalino. El resultado puede ser tratado usando elementos de termodinámica estadística y da información de la estabilidad de todo el espacio simétrico. Además se estudiaron otras características importantes de los semiconductores de base. En concreto, el análisis de las interacciones de van der Waals fueron incluidas en el semiconductor en capas SnS2, y el grado de inversión en el caso de las espinelas [M]In2S4. En este trabajo además realizamos una descripción teórica exhaustiva del sistema CdTe:Bi. Este material de banda-intermedia muestra características que son distintas a las de los otros materiales estudiados. También se analizó el Zn como agente modulador de la posición de las sub-bandas prohibidas en el material de banda-intermedia CuGaS2:Ti. Analizándose además la viabilidad termodinámica de la formación de este compuesto. Finalmente, también se describió el GaN:Cr como material de banda intermedia, en la estructura zinc-blenda y en wurtztite, usando configuraciones de sitios ocupados de acuerdo a la simetría del sistema cristalino del semiconductor de base. Todos los resultados, siempre que fue posible, fueron comparados con los resultados experimentales. ABSTRACT The intermediate-band materials have attracted the attention of the scientific community in the field of the photovoltaics in recent years. Nevertheless, in order to understand the intermediate-band solar cell fundamentals, a profound study of the characteristics of the materials is required. This can be done using theoretical modelling from first-principles. The electronic structure and optical properties of heavily doped semiconductors and their precursor semiconductors are, among others, results that can be obtained from this approach. In order to unravel the structures of these crystalline systems, this thesis presents a thermodynamic and optoelectronic study of several photovoltaic materials. Specifically advanced intermediate-band materials and their precursor semiconductors were characterized. The study was made in terms of theoretical characterization of the electronic structure, energetics among others. The stability was obtained using site-occupancy-disorder configurations adapted to the symmetry of the system and based on combinatorics. The site-occupancy-disorder method allows the formation of a configurational space of substitutional dopant positions based on the symmetry of the crystalline solid. The result, that can be treated using statistical thermodynamics, gives information of the stability of the whole space of symmetry of the crystalline lattice. Furthermore, certain other important characteristics of host semiconductors were studied. Specifically, the van der Waal interactions were included in the SnS2 layered semiconductor, and the inversion degree in cases of [M]In2S4 spinels. In this work we also carried out an exhaustive theoretical description of the CdTe:Bi system. This intermediate-band material shows characteristics that are distinct from those of the other studied intermediate-band materials. In addition, Zn was analysed as a modulator of the positions of the sub-band gaps in the CuGaS2:Ti intermediate-band material. The thermodynamic feasibility of the formation of this compound was also carried out. Finally GaN:Cr intermediate-band material was also described both in the zinc-blende and the wurtztite type structures, using the symmetry-adapted-space of configurations. All results, whenever possible, were compared with experimental results.

Planar point sets with large minimum convex decompositions

We show the existence of sets with n points (n ? 4) for which every convex decomposition contains more than (35/32)n?(3/2) polygons,which refutes the conjecture that for every set of n points there is a convex decomposition with at most n+C polygons. For sets having exactly three extreme pointswe show that more than n+sqr(2(n ? 3))?4 polygons may be necessary to form a convex decomposition.