Search

Your search keyword '"graph immersions"' showing total 4 results
Start Over Descriptor "graph immersions" Topic 010102 general mathematics
4 results on '"graph immersions"'

1. Graph immersions with parallel cubic form

Author

Roland Hildebrand, Données, Apprentissage et Optimisation (DAO), Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Calculs Algébriques et Systèmes Dynamiques (CASYS), and Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)

Subjects
Mathematics - Differential Geometry, parallel cubic form, Jordan algebras, affine differential geometry, 01 natural sciences, graph immersion, cubic form, Combinatorics, 0103 physical sciences, Immersion (mathematics), FOS: Mathematics, Cubic form, 0101 mathematics, Mathematics, Connected component, Jordan algebra, improper affine hyperspheres, graph immersions, 010102 general mathematics, Complete graph, MSC 53A15, 17C36, 17C37, MSC 53A15, Nilpotent, Hypersurface, Computational Theory and Mathematics, Differential Geometry (math.DG), [MATH.MATH-DG]Mathematics [math]/Differential Geometry [math.DG], 53A15, 17C36, 17C37, 010307 mathematical physics, Geometry and Topology, Affine transformation, Mathematics::Differential Geometry, Analysis
Abstract

We consider non-degenerate graph immersions into affine space $\mathbb A^{n+1}$ whose cubic form is parallel with respect to the Levi-Civita connection of the affine metric. There exists a correspondence between such graph immersions and pairs $(J,\gamma)$, where $J$ is an $n$-dimensional real Jordan algebra and $\gamma$ is a non-degenerate trace form on $J$. Every graph immersion with parallel cubic form can be extended to an affine complete symmetric space covering the maximal connected component of zero in the set of quasi-regular elements in the algebra $J$. It is an improper affine hypersphere if and only if the corresponding Jordan algebra is nilpotent. In this case it is an affine complete, Euclidean complete graph immersion, with a polynomial as globally defining function. We classify all such hyperspheres up to dimension 5. As a special case we describe a connection between Cayley hypersurfaces and polynomial quotient algebras. Our algebraic approach can be used to study also other classes of hypersurfaces with parallel cubic form., Comment: some proofs have been simplified with respect to the first version

Published
2021
Full Text
View/download PDF

2. Forcing clique immersions through chromatic number

Author

Paul Wollan, Gregory Gauthier, and Tien-Nam Le

Subjects
Simple graph, 010102 general mathematics, Graph Immersions, Hadwiger’s conjecture, graph coloring, chromatic number, 0102 computer and information sciences, 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, chromatic number, Independent set, Graph Immersions, FOS: Mathematics, Immersion (mathematics), Hadwiger’s conjecture, graph coloring, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Combinatorics (math.CO), Chromatic scale, 0101 mathematics, Mathematics
Abstract

Building on recent work of Dvo\v{r}\'ak and Yepremyan, we show that every simple graph of minimum degree $7t+7$ contains $K_t$ as an immersion and that every graph with chromatic number at least $3.54t + 4$ contains $K_t$ as an immersion. We also show that every graph on $n$ vertices with no stable set of size three contains $K_{2\lfloor n/5 \rfloor}$ as an immersion., Comment: 26 pages, 1 figure

Published
2019

3. Recent techniques and results on the Erdős-Pósa property

Author

Jean-Florent Raymond, Dimitrios M. Thilikos, Algorithmes, Graphes et Combinatoire ( ALGCO ), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier ( LIRMM ), Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ), Faculty of Mathematics, Informatics, and Mechanics [Warsaw], University of Warsaw ( UW ), Department of Mathematics [Athens], National and Kapodistrian University of Athens, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), and National and Kapodistrian University of Athens (NKUA)

Subjects
Current (mathematics), Property (philosophy), tree partitions, G.2.1, G.2.2, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO], 01 natural sciences, girth, min-max theorems, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Erdős–Pósa property, 0101 mathematics, tree decompositions, graph minors, Mathematics, Discrete mathematics, Erd˝ os–Pósa property, graph immersions, 05C70, Applied Mathematics, 010102 general mathematics, Covering problems, Graph theory, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], State (functional analysis), Girth (graph theory), 16. Peace & justice, Connection (mathematics), 010201 computation theory & mathematics, topological minors, min–max theorems, MathematicsofComputing_DISCRETEMATHEMATICS, Computer Science - Discrete Mathematics
Abstract

International audience; Several min–max relations in graph theory can be expressed in the framework of the Erdős–Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic.

Published
2017
Full Text
View/download PDF

4. Packing and Covering Immersion Models of Planar subcubic Graphs

Author

Dimitrios M. Thilikos, Jean-Florent Raymond, O-joung Kwon, Archontia C. Giannopoulou, Institut für Softwaretechnik und Theoretische Informatik [EECS-TUB], Fakultät Elektrotechnik und Informatik [TUB], Technical University of Berlin / Technische Universität Berlin (TU)-Technical University of Berlin / Technische Universität Berlin (TU), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), National and Kapodistrian University of Athens (NKUA), (Polish) National Science Centre grant PRELUDIUM 2013/11/N/ST6/02706, European Project: 280152,EC:FP7:ERC,ERC-2011-StG_20101014,PARAMTIGHT(2012), Technische Universität Berlin ( TUB ) -Technische Universität Berlin ( TUB ), Faculty of Mathematics, Informatics, and Mechanics [Warsaw], University of Warsaw ( UW ), Computer and Automation Research Institute [Budapest] ( MTA SZTAKI ), Algorithmes, Graphes et Combinatoire ( ALGCO ), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier ( LIRMM ), Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ), National and Kapodistrian University of Athens, European Project : 280152,EC:FP7:ERC,ERC-2011-StG_20101014,PARAMTIGHT ( 2012 ), Technische Universität Berlin (TU)-Technische Universität Berlin (TU), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
Graph immersions, 0102 computer and information sciences, G.2.2, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, law.invention, Combinatorics, Planar, Graph power, law, Line graph, Graph minor, FOS: Mathematics, Mathematics - Combinatorics, Erdős–Pósa property, 0101 mathematics, Mathematics, Discrete mathematics, 010102 general mathematics, QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], Graph, Vertex (geometry), Packings and coverings in graphs, 010201 computation theory & mathematics, 05C75, Path graph, Combinatorics (math.CO)
Abstract

A graph $H$ is an immersion of a graph $G$ if $H$ can be obtained by some sugraph $G$ after lifting incident edges. We prove that there is a polynomial function $f:\Bbb{N}\times\Bbb{N}\rightarrow\Bbb{N}$, such that if $H$ is a connected planar subcubic graph on $h>0$ edges, $G$ is a graph, and $k$ is a non-negative integer, then either $G$ contains $k$ vertex/edge-disjoint subgraphs, each containing $H$ as an immersion, or $G$ contains a set $F$ of $f(k,h)$ vertices/edges such that $G\setminus F$ does not contain $H$ as an immersion.

Published
2016
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results