京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第21393号 / 情博第679号 / 新制||情||117(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 阿久津 達也, 教授 山本 章博, 教授 鹿島 久嗣 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Vertex algebras and strongly homotopy Lie algebras (SHLA) are extensively used in qunatum field theory and string theory. Recently, it was shown that a Courant algebroid can be naturally lifted to a SHLA. The 0-product in the de Rham chiral algebra has an identical formula to the Courant bracket of vector fields and 1-forms. We show that in general, a vertex algebra has an SHLA structure and that the de Rham chiral algebra has a non-zero l4 homotopy.

Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively new field of study. We present a survey of known results concerning vdec colorings. We also define a new matrix which may be used to study vdec colorings, and examine its properties. We find several bounds on the eigenvalues of this matrix, as well as results concerning its determinant, and other properties. We finish by examining related topics and open problems.

We present a set of approximation results for several covering problems in dense graphs. These results show that for several problems, classical algorithms with constant approximation ratios can be analyzed in a finer way, and provide better constant approximation ratios under some density constraints. In particular, we show that the maximal matching heuristic approximates VERTEX COVER (VC) and MINIMUM MAXIMAL MATCHING (MMM) with a constant ratio strictly smaller than 2 when the proportion of edges present in the graph (weak density) is at least 3/4, or when the normalized minimum degree (strong density) is at least 1/2. We also show that this result can be improved by a greedy algorithm which provides a constant ratio smaller than 2 when the weak density is at least 1/2. We also provide tight families of graphs for all these approximation ratios. We then looked at several algorithms from the literature for VC and SET COVER (SC). We present a unified and critical approach to the Karpinski/Zelikovsky, Imamura/Iwama and Bar-Yehuda/Kehat algorithms, identifying the general the general scheme underlying these algorithms. Finally, we look at the CONNECTED VERTEX COVER (CVC) problem,for which we proposed new approximation results in dense graphs. We first analyze Carla Savage's algorithm, then a new variant of the Karpinski-Zelikovsky algorithm. Our results show that these algorithms provide the same approximation ratios for CVC as the maximal matching heuristic and the Karpinski-Zelikovsky algorithm did for VC. We provide tight examples for the ratios guaranteed by both algorithms. We also introduce a new invariant, the "price of connectivity of VC", defined as the ratio between the optimal solutions of CVC and VC, and showed a nearly tight upper bound on its value as a function of the weak density. Our last chapter discusses software aspects, and presents the use of the GRAPHEDRON software in the framework of approximation algorithms, as well as our contributions to the development of this system. / Nous présentons un ensemble de résultats d'approximation pour plusieurs problèmes de couverture dans les graphes denses. Ces résultats montrent que pour plusieurs problèmes, des algorithmes classiques à facteur d'approximation constant peuvent être analysés de manière plus fine, et garantissent de meilleurs facteurs d'aproximation constants sous certaines contraintes de densité. Nous montrons en particulier que l'heuristique du matching maximal approxime les problèmes VERTEX COVER (VC) et MINIMUM MAXIMAL MATCHING (MMM) avec un facteur constant inférieur à 2 quand la proportion d'arêtes présentes dans le graphe (densité faible) est supérieure à 3/4 ou quand le degré minimum normalisé (densité forte) est supérieur à 1/2. Nous montrons également que ce résultat peut être amélioré par un algorithme de type GREEDY, qui fournit un facteur constant inférieur à 2 pour des densités faibles supérieures à 1/2. Nous donnons également des familles de graphes extrémaux pour nos facteurs d'approximation. Nous nous somme ensuite intéressés à plusieurs algorithmes de la littérature pour les problèmes VC et SET COVER (SC). Nous avons présenté une approche unifiée et critique des algorithmes de Karpinski-Zelikovsky, Imamura-Iwama, et Bar-Yehuda-Kehat, identifiant un schéma général dans lequel s'intègrent ces algorithmes. Nous nous sommes finalement intéressés au problème CONNECTED VERTEX COVER (CVC), pour lequel nous avons proposé de nouveaux résultats d'approximation dans les graphes denses, au travers de l'algorithme de Carla Savage d'une part, et d'une nouvelle variante de l'algorithme de Karpinski-Zelikovsky d'autre part. Ces résultats montrent que nous pouvons obtenir pour CVC les mêmes facteurs d'approximation que ceux obtenus pour VC à l'aide de l'heuristique du matching maximal et de l'algorithme de Karpinski-Zelikovsky. Nous montrons également des familles de graphes extrémaux pour les ratios garantis par ces deux algorithmes. Nous avons également étudié un nouvel invariant, le coût de connectivité de VC, défini comme le rapport entre les solutions optimales de CVC et de VC, et montré une borne supérieure sur sa valeur en fonction de la densité faible. Notre dernier chapitre discute d'aspects logiciels, et présente l'utilisation du logiciel GRAPHEDRON dans le cadre des algorithmes d'approximation, ainsi que nos contributions au développement du logiciel.

Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively new field of study. We present a survey of known results concerning vdec colorings. We also define a new matrix which may be used to study vdec colorings, and examine its properties. We find several bounds on the eigenvalues of this matrix, as well as results concerning its determinant, and other properties. We finish by examining related topics and open problems.

During development, organs with different shape and functionality form from a single fertilized egg cell. Mechanisms that control shape, size and morphology of tissues pose challenges for developmental biology. These mechanisms are tightly controlled by an underlying signaling system by which cells communicate to each other. However, these signaling networks can affect tissue size and morphology through limited processes such as cell proliferation, cell death and cell shape changes,which are controlled by cell mechanics and cell adhesion. One example of such a signaling system is the network of interacting proteins that control planar polarization of cells. These proteins distribute asymmetrically within cells and their distribution in each cell determines of the polarity of the neighboring cells. These proteins control the pattern of hairs in the adult Drosophila wing as well as hexagonal repacking of wing cells during development. Planar polarity proteins also control developmental processes such as convergent-extension. We present a theoretical study of cell packing geometry in developing epithelia. We use a vertex model to describe the packing geometry of tissues, for which forces are balanced throughout the tissue. We introduce a cell division algorithm and show that repeated cell division results in the formation of a distinct pattern of cells, which is controlled by cell mechanics and cell-cell interactions. We compare the vertex model with experimental measurements in the wing disc of Drosophila and quantify for the first time cell adhesion and perimeter contractility of cells. We also present a simple model for the dynamics of polarity order in tissues. We identify a basic mechanism by which long-range polarity order throughout the tissue can be established. In particular we study the role of shear deformations on polarity pattern and show that the polarity of the tissue reorients during shear flow. Our simple mechanisms for ordering can account for the processes observed during development of the Drosophila wing.

In discrete mathematics, a convex space is an ordered pair (V,M) where M is a family of subsets of a finite set V , such that: ∅ ∈M, V ∈M, andMis closed under intersection. The elements of M are called convex sets. For a set S ⊆ V , the convex hull of S is the smallest convex set that contains S. A point x of a convex set X is an extreme point of X if X\{x} is also convex. A convex space (V,M) with the property that every convex set is the convex hull of its extreme points is called a convex geometry. A graph G has a P-elimination ordering if an ordering v1, v2, ..., vn of the vertices exists such that vi has property P in the graph induced by vertices vi, vi+1, ..., vn for all i = 1, 2, ...,n. Farber and Jamison [18] showed that for a convex geometry (V,M), X ∈Mif and only if there is an ordering v1, v2, ..., vk of the points of V − X such that vi is an extreme point of {vi, vi+1, ..., vk}∪ X for each i = 1, 2, ...,k. With these concepts in mind, this thesis surveys the literature and summarizes results regarding graph convexities and elimination orderings. These results include classifying graphs for which different types of convexities give convex geometries, and classifying graphs for which different vertex ordering algorithms result in a P-elimination ordering, for P the characteristic property of the extreme points of the convexity. We consider the geodesic, monophonic, m3, 3-Steiner and 3-monophonic convexities, and the vertex ordering algorithms LexBFS, MCS, MEC and MCC. By considering LexDFS, a recently introduced vertex ordering algorithm of Corneil and Krueger [11], we obtain new results: these are characterizations of graphs for which all LexDFS orderings of all induced subgraphs are P-elimination orderings, for every characteristic property P of the extreme vertices for the convexities studied in this thesis. / Graduate / 0405 / rachela@uvic.ca

In discrete mathematics, a convex space is an ordered pair (V,M) where M is a family of subsets of a finite set V , such that: ∅ ∈M, V ∈M, andMis closed under intersection. The elements of M are called convex sets. For a set S ⊆ V , the convex hull of S is the smallest convex set that contains S. A point x of a convex set X is an extreme point of X if X\{x} is also convex. A convex space (V,M) with the property that every convex set is the convex hull of its extreme points is called a convex geometry. A graph G has a P-elimination ordering if an ordering v1, v2, ..., vn of the vertices exists such that vi has property P in the graph induced by vertices vi, vi+1, ..., vn for all i = 1, 2, ...,n. Farber and Jamison [18] showed that for a convex geometry (V,M), X ∈Mif and only if there is an ordering v1, v2, ..., vk of the points of V − X such that vi is an extreme point of {vi, vi+1, ..., vk}∪ X for each i = 1, 2, ...,k. With these concepts in mind, this thesis surveys the literature and summarizes results regarding graph convexities and elimination orderings. These results include classifying graphs for which different types of convexities give convex geometries, and classifying graphs for which different vertex ordering algorithms result in a P-elimination ordering, for P the characteristic property of the extreme points of the convexity. We consider the geodesic, monophonic, m3, 3-Steiner and 3-monophonic convexities, and the vertex ordering algorithms LexBFS, MCS, MEC and MCC. By considering LexDFS, a recently introduced vertex ordering algorithm of Corneil and Krueger [11], we obtain new results: these are characterizations of graphs for which all LexDFS orderings of all induced subgraphs are P-elimination orderings, for every characteristic property P of the extreme vertices for the convexities studied in this thesis. / Graduate / 0405 / rachela@uvic.ca

In this thesis, we investigate sigma models and algebraic structures emerging from a Hamiltonian description of their dynamics, both in a classical and in a quantum setup. More specifically, we derive the phase space structures together with the Hamiltonians for the bosonic two-dimensional non-linear sigma model, and also for the N=1 and N=2 supersymmetric models. A convenient framework for describing these structures are Lie conformal algebras and Poisson vertex algebras. We review these concepts, and show that a Lie conformal algebra gives a weak Courant–Dorfman algebra. We further show that a Poisson vertex algebra generated by fields of conformal weight one and zero are in a one-to-one relationship with Courant–Dorfman algebras. Vertex algebras are shown to be appropriate for describing the quantum dynamics of supersymmetric sigma models. We give two definitions of a vertex algebra, and we show that these definitions are equivalent. The second definition is given in terms of a λ-bracket and a normal ordered product, which makes computations straightforward. We also review the manifestly supersymmetric N=1 SUSY vertex algebra. We also construct sheaves of N=1 and N=2 vertex algebras. We are specifically interested in the sheaf of N=1 vertex algebras referred to as the chiral de Rham complex. We argue that this sheaf can be interpreted as a formal quantization of the N=1 supersymmetric non-linear sigma model. We review different algebras of the chiral de Rham complex that one can associate to different manifolds. In particular, we investigate the case when the manifold is a six-dimensional Calabi–Yau manifold. The chiral de Rham complex then carries two commuting copies of the N=2 superconformal algebra with central charge c=9, as well as the Odake algebra, associated to the holomorphic volume form.

This thesis presents a variety of work concerning the design, construction and use of the SLD's vertex detector. SLD's pioneering 120 Mpixel vertex detector, VXD2, was replaced by VXD3, a 307Mpixel CCD vertex detector in January 1996. The motivation for the up-grade detector and its subsquent construction and testing are described in some detail. This work represents the collaborative work of a large number of people. My work was mainly carried out at EEV on the testing of the CCDs and subsequent ladders. VXD3 was commissioned during the 1996 SLD run and performed very close to design specifications. Monitoring the position of VXD3 is crucial for reconstructing the data in the detector for physics analysis. This was carried out using a capacitive wire position monitoring system. The system indicated that VXD3 was very stable during the whole of the 1996 run, except for known controlled movements. VXD3 was aligned globally for each period in-between these known movements using the tracks from e+e- → Z° → hadrons. The structure of three-jet bbg events has been studied using hadronic Z° decays from the 1993-1995 SLD data. Three-jet final states were selected and the CCD-based vertex detector was used to identify two of the jets as a ь or ъ. The distributions of the gluon energy and polar angle with respect to the electron beam direction were examined and were compared with perturbative QCD predictions. If was found that the QCD Parton Shower prediction was needed to describe the data well. These distributions are potentially sensitive to an anomalous b chromomagnetic moment к. к was measured to be -0.031±0.038 0.039(Stat.)±0.003 0.004(Syst.), which is consistent with the Standard Model, with 95% confidence level limit, -0.106 < к < 0.044.