The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by J. K\"{o}rner in 1973. Although the notion of graph entropy has its roots in information theory, it was proved to be closely related to some classical and frequently studied graph theoretic concepts. For example, it provides an equivalent definition for a graph to be perfect and it can also be applied to obtain lower bounds in graph covering problems. In this thesis, we review and investigate three equivalent definitions of graph entropy and its basic properties. Minimum entropy colouring of a graph was proposed by N. Alon in 1996. We study minimum entropy colouring and its relation to graph entropy. We also discuss the relationship between the entropy and the fractional chromatic number of a graph which was already established in the literature. A graph $G$ is called \emph{symmetric with respect to a functional $F_G(P)$} defined on the set of all the probability distributions on its vertex set if the distribution $P^*$ maximizing $F_G(P)$ is uniform on $V(G)$. Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we prove that vertex transitive graphs are symmetric with respect to graph entropy. Furthermore, we show that a bipartite graph is symmetric with respect to graph entropy if and only if it has a perfect matching. As a generalization of this result, we characterize some classes of symmetric perfect graphs with respect to graph entropy. Finally, we prove that the line graph of every bridgeless cubic graph is symmetric with respect to graph entropy.

During development, cells consume energy, divide, rearrange, and die. Bulk properties such as viscosity and elasticity emerge from cell-scale mechanics and dynamics. Order appears, for example in patterns of hair outgrowth, or in the predominately hexagonal pattern of cell boundaries in the wing of a fruit fly. In the past fifty years, much progress has been made in understanding tissues as living materials. However, the physical mechanisms underlying tissue-scale behaviour are not completely understood. Here we apply theories from statistical physics and fluid dynamics to understand mechanics and order in two-dimensional tissues. We restrict our attention to the mechanics and dynamics of cell boundaries and vertices, and to planar polarity, a type of long-ranged order visible in anisotropic patterns of proteins and hair outgrowth. Our principle tool for understanding mechanics and dynamics is a vertex model where cell shapes are represented using polygons. We analytically derive the ground-state diagram of this vertex model, finding it to be dominated by the geometric requirement that cells be polygons, and the topological requirement that those polygons tile the plane. We present a simplified algorithm for cell division and growth, and furthermore derive a dynamic equation for the vertex model, which we use to demonstrate the emergence of quasistatic behaviour in the limit of slow growth. All our results relating to the vertex model are consistent with and build off past calculations and experiments. To investigate the emergence of planar polarity, we develop quantification methods for cell flow and planar polarity based on confocal microscope images of developing fly wings. We analyze cell flow using a velocity gradient tensor, which is uniquely decomposed into terms corresponding to local compression, shear, and rotations. We argue that a pattern in an inhomogeneously flowing tissue will necessarily be reorganized, motivating a hydrodynamic theory of polarity reorientation. Using such a coarse-grained theory of polarity reorientation, we show that the quantified patterns of shear and rotation in the wing are consistent with the observed polarity reorganization, and conclude that cell flow reorients planar polarity in the wing of the fruit fly. Finally, we present a cell-scale model of planar polarity based on the vertex model, unifying the themes of this thesis.

Diese Arbeit befaßt sich mit der Koppelung von Vertex-Modellen an die planaren $\phi^4$-Zufallsgraphen des Zugangs zur Quantengravitation über dynamische Polygonifizierungen. Das betrachtete System hat eine doppelte Bedeutung, einerseits als die Koppelung einer konformen Feldtheorie mit zentraler Ladung $C=1$ an zweidimensionale Euklidische Quantengravitation, andererseits als Anwendung von geometrischer, "annealed" Unordnung auf ein prototypisches Modell der statistischen Mechanik. Da das Modell mit Hilfe einer großangelegten Reihe von Monte Carlo Simulationen untersucht wird, müssen entsprechende Techniken für die Simulation von dynamischen Quadrangulierungen bzw. die dualen $\phi^4$-Graphen entwickelt werden. Hierzu werden verschiedene Algorithmen und die dazugehörigen Züge vorgeschlagen und hinsichtlich ihrer Ergodizität und Effizienz untersucht. Zum Vergleich mit exakten Ergebnissen werden die Verteilung der Koordinationszahlen bzw. bestimmte Analoga davon konstruiert. Für Simulationen des $F$-Modells auf $\phi^4$-Zufallsgraphen wird ein Ordnungsparameter für den antiferroelektrischen Phasenübergang mit Hilfe einer Plakettenspindarstellung formuliert. Ausführliche "finite-size scaling"-Analysen des Kosterlitz-Thouless-Phasenübergangs des $F$-Modells auf dem Quadratgitter und auf Zufallsgraphen werden vorgestellt und die Positionen der jeweiligen kritischen Punkte sowie die dazugehörigen kritischen Exponenten werden bestimmt. Die Rückreaktion des Vertex-Modells auf die Zufallsgraphen wird in Form der Koordinationszahlverteilung, der Verteilung der "Baby-Universen" und dem daraus resultierenden String-Suszeptibilitäts-Exponenten sowie durch die geometrische Zweipunktfunktion analysiert, die eine Schätzung der intrinsischen Hausdorff-Dimension des gekoppelten Systems liefert. / In this thesis, the coupling of ice-type vertex models to the planar $\phi^4$ random graphs of the dynamical polygonifications approach to quantum gravity is considered. The investigated system has a double significance as a conformal field theory with central charge $C=1$ coupled to two-dimensional Euclidean quantum gravity and as the application of a special type of annealed connectivity disorder to a prototypic model of statistical mechanics. Since the model is analyzed by means of large-scale Monte Carlo simulations, suitable simulation techniques for the case of dynamical quadrangulations and the dual $\phi^4$ random graphs have to be developed. Different algorithms and the associated update moves are proposed and investigated with respect to their ergodicity and performance. For comparison to exact results, the co-ordination number distribution of the dynamical polygonifications model, or certain analogues of it, are constructed. For simulations of the 6-vertex $F$ model on $\phi^4$ random graphs, an order parameter for its anti-ferroelectric phase transitions is constructed in terms of a "plaquette spin" representation. Extensive finite-size scaling analyses of the Kosterlitz-Thouless point of the square-lattice and random graph $F$ models are presented and the locations of the critical points as well as the corresponding critical exponents are determined. The back-reaction of the coupled vertex model on the random graphs is investigated by an analysis of the co-ordination number distribution, the distribution of "baby universes" and the string susceptibility exponent as well as the geometric two-point function, yielding an estimate for the internal Hausdorff dimension of the coupled system.

"A bijection mapping that assigns natural numbers to vertices and/or edges of a graph is called a labeling. In this thesis, we consider graph labelings that have weights associated with each edge and/or vertex. If all the vertex weights (respectively, edge weights) have the same value then the labeling is called magic. If the weight is different for every vertex (respectively, every edge) then we called the labeling antimagic. In this thesis we introduce some variations of magic and antimagic labelings and discuss their properties and provide corresponding labeling schemes. There are two main parts in this thesis. One main part is on vertex labeling and the other main part is on edge labeling." / Doctor of Philosophy

"A bijection mapping that assigns natural numbers to vertices and/or edges of a graph is called a labeling. In this thesis, we consider graph labelings that have weights associated with each edge and/or vertex. If all the vertex weights (respectively, edge weights) have the same value then the labeling is called magic. If the weight is different for every vertex (respectively, every edge) then we called the labeling antimagic. In this thesis we introduce some variations of magic and antimagic labelings and discuss their properties and provide corresponding labeling schemes. There are two main parts in this thesis. One main part is on vertex labeling and the other main part is on edge labeling." / Doctor of Philosophy

Thesis (Ph. D.)--University of Chicago, Department of Mathematics, June 2000. / Includes bibliographical references. Also available on the Internet.

The development and maintenance of tissues and organs depend on the careful regulation and coordinated motion of large numbers of cells. There is substantial evidence that many complex tissue functions, such as cell division, collective cell migration and gene expression, are directly regulated by mechanical forces. However, relatively little is known about how mechanical stress is distributed within a tissue and how this may guide biochemical signalling. Working in the framework of a popular vertex-based model, we derive expressions for stress tensors at the cell and tissue level to build analytic relationships between cell shape and mechanical stress. The discrete vertex model is upscaled, providing exact expressions for the bulk and shear moduli of disordered cellular networks, which bridges the gap to traditional continuum-level descriptions of tissues. Combining this theoretical work with new experimental techniques for whole-tissue stretching of Xenopus laevis tissue, we separate the roles of mechanical stress and cell shape in orienting and cueing epithelial mitosis. We find that the orientation of division is best predicted by the shape of tricellular junctions, while there appears to be a more direct role for mechanical stress as a mitotic cue.

The focus of this work is to verify the possibility of very rapid collection of accurate data that can be easily analyzed and used for planning and business purposes. For data collection was chosen method of averaging the fullest and data analysis was used new software LČRTax, ULT and set of polynomials. The data found standing crops were analyzed with data after felling. In this work were used electronic devices allowing for a very accurate data. Digitech Professional caliper and Vertex Laser Altimeter. The results are confronted with at the end of the current economic situation.

CAMPOS, Victor Almeida. Um estudo do politopo e dos limites inferiores gerados pela formulação de coloração dos representantes. 2005. 108 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2005. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:37:10Z No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:41:39Z (GMT) No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) / Made available in DSpace on 2016-07-22T12:41:39Z (GMT). No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) Previous issue date: 2005 / The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value. / O problema de coloração de vértices é considerado um dos modelos mais estudados em teoria dos grafos pela sua relevância em campos práticos e teóricos. Do ponto de vista teórico, o problema de coloração é NP - Difícil. Além disto, foi classificado entre os problemas mais difíceis de NP, no sentido de que achar uma aproximação para o número cromático também é NP - Difícil. A importância do problema de coloração tem incentivado a investigar métodos para encontrar limitantes inferiores próximos do número cromático. Historicamente, os primeiros limitantes inferiores utilizados para resolvê-lo lidavam com cliques maximais. Mais recentemente, popularizou-se a utilização de relaxações lineares de formulações de programação inteira. Uma formulação que mostrou bons limitantes inferiores foi a formulação por conjuntos independentes, cujo valor de relaxação equivale ao número cromático fracionário. No presente trabalho, fazemos uma comparação entre as formulações de programação inteira conhecidas para indicar a escolha pela formulação dos representantes. Revisamos a formulação para remover simetrias existentes e apresentamos um estudo parcial do politopo associado ao fecho convexo de suas soluções inteiras. Discutimos como é possível utilizar a formulação dos representantes para gerar limites inferiores para o número cromático fracionário. Realizamos a implementação de um método de planos de corte para aproximar o número cromático fracionário e mostramos que podemos gerar limitantes inferiores que normalmente não diferem em mais de uma unidade.

abstract: Quadratic growth curves of 2nd degree polynomial are widely used in longitudinal studies. For a 2nd degree polynomial, the vertex represents the location of the curve in the XY plane. For a quadratic growth curve, we propose an approximate confidence region as well as the confidence interval for x and y-coordinates of the vertex using two methods, the gradient method and the delta method. Under some models, an indirect test on the location of the curve can be based on the intercept and slope parameters, but in other models, a direct test on the vertex is required. We present a quadratic-form statistic for a test of the null hypothesis that there is no shift in the location of the vertex in a linear mixed model. The statistic has an asymptotic chi-squared distribution. For 2nd degree polynomials of two independent samples, we present an approximate confidence region for the difference of vertices of two quadratic growth curves using the modified gradient method and delta method. Another chi-square test statistic is derived for a direct test on the vertex and is compared to an F test statistic for the indirect test. Power functions are derived for both the indirect F test and the direct chi-square test. We calculate the theoretical power and present a simulation study to investigate the power of the tests. We also present a simulation study to assess the influence of sample size, measurement occasions and nature of the random effects. The test statistics will be applied to the Tell Efficacy longitudinal study, in which sound identification scores and language protocol scores for children are modeled as quadratic growth curves for two independent groups, TELL and control curriculum. The interpretation of shift in the location of the vertices is also presented. / Dissertation/Thesis / Doctoral Dissertation Statistics 2015