Search

Showing total 6 results
Start Over Search Limiters Full Text Topic 010102 general mathematics Topic combinatorics
6 results

1. Enclosings of decompositions of complete multigraphs in 2-edge-connected r -factorizations

Author

John Asplund, Pierre Charbit, Carl Feghali, Dalton State College, University System of Georgia (USG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Bergen (UIB), This paper received partial support his paper received partial support by Fondation Sciences Mathématiques de Paris and the Research Council of Norway via the project CLASSIS, Grant Number 249994., and University of Bergen (UiB)

Subjects
Discrete mathematics, 010102 general mathematics, Multigraph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Theoretical Computer Science, Combinatorics, Factorization, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Partition (number theory), Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, 05B99
Abstract

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1), \ldots , G(k)$. It is called an $r$-factorization if every $G(i)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1 \leq i \leq k$, $G(i)$ is a subgraph of $H(i)$. Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu>\lambda$ and either $m \geq 2n-1$, or $m=2n-2$ and $\mu = 2$ and $\lambda=1$, or $n=3$ and $m=4$. We generalize their result to every $r \geq 2$ and $m \geq 2n - 2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for every $r \geq 3$ and $m = (2 - C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and~$\mu$., Comment: 17 pages; fixed the proof of Theorem 1.4 and other minor changes

Published
2019

2. Towards a symplectic version of the Chevalley restriction theorem

Author

Ronan Terpereau, Manfred Lehn, Christian Lehn, Michael Bulois, Algèbre, géométrie, logique ( AGL ), Institut Camille Jordan [Villeurbanne] ( ICJ ), École Centrale de Lyon ( ECL ), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Institut National des Sciences Appliquées de Lyon ( INSA Lyon ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Jean Monnet [Saint-Étienne] ( UJM ) -Centre National de la Recherche Scientifique ( CNRS ) -École Centrale de Lyon ( ECL ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Jean Monnet [Saint-Étienne] ( UJM ) -Centre National de la Recherche Scientifique ( CNRS ), Fakultät für Mathematik der Technischen Universität Chemnitz, Fakultaet fuer Mathematik der Technischen Universitaet Chemnitz, Institut für Mathematik ( MI ), Johannes Gutenberg - Universität Mainz ( JGU ), Institut de Mathématiques de Bourgogne [Dijon] ( IMB ), Université de Bourgogne ( UB ) -Centre National de la Recherche Scientifique ( CNRS ), Max Planck Institute for Mathematics ( Bonn ), The second-named author gratefully acknowledges the support by the DFG through the research grant Le 3093/2-1. The thirdnamed author is supported by the SFB Transregio 45 'Periods, Moduli Spaces and Arithmetic of Algebraic Varieties'. The fourth-named author is grateful to the Max-Planck-Institut für Mathematik of Bonn for the warm hospitality and support provided during the writing of this paper. Part ofthe genesis of this paper occurred during the half semester Algebraic Groups and Representations supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program 'Investissements d'Avenir' (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR)., ANR-11-IDEX-0007-02/10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon ( 2011 ), ANR-15-CE40-0012,GeoLie,GeoLie, Algèbre, géométrie, logique (AGL), Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Chemnitz University of Technology / Technische Universität Chemnitz, Institut für Mathematik (MI), Johannes Gutenberg - Universität Mainz (JGU), Institut de Mathématiques de Bourgogne [Dijon] (IMB), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), Max Planck Institute for Mathematics (MPIM), Max-Planck-Gesellschaft, ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), and ANR-15-CE40-0012,GéoLie,Méthodes géométriques en théorie de Lie(2015)

Subjects
Polar representation, Symplectic variety, [ MATH.MATH-SG ] Mathematics [math]/Symplectic Geometry [math.SG], 01 natural sciences, Combinatorics, Mathematics - Algebraic Geometry, symbols.namesake, Morphism, 0103 physical sciences, FOS: Mathematics, 14L30, 53D20, 20G05, 20G20, 13A50, Representation Theory (math.RT), 0101 mathematics, MSC: 14L30, 53D20, 20G05, 20G20, 13A50, Mathematics::Representation Theory, Symplectic reduction, Algebraic Geometry (math.AG), Moment map, Mathematics, Weyl group, Algebra and Number Theory, Conjecture, [MATH.MATH-RT]Mathematics [math]/Representation Theory [math.RT], Reductive group, 010102 general mathematics, [MATH.MATH-SG]Mathematics [math]/Symplectic Geometry [math.SG], [ MATH.MATH-RT ] Mathematics [math]/Representation Theory [math.RT], [ MATH.MATH-AG ] Mathematics [math]/Algebraic Geometry [math.AG], Mathematics - Symplectic Geometry, symbols, Symplectic Geometry (math.SG), 010307 mathematical physics, Isomorphism, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Mathematics - Representation Theory, Symplectic geometry
Abstract

If $(G,V)$ is a polar representation with Cartan subspace $\mathfrak c$ and Weyl group $W$, it is shown that there is a natural morphism of Poisson schemes $\mathfrak c \oplus {\mathfrak c}^*/W \to V\oplus V^*/\!\!/\!\!/ G$. This morphism is conjectured to be an isomorphism of the underlying reduced varieties if $(G,V)$ is visible. The conjecture is proved for visible stable locally free polar representations and certain further examples., Comment: 18 pages, final version

Published
2017

3. Convergence regions for the Chebyshev–Halley family

Author

B. Campos, Jordi Canela, P. Vindel, and The authors would like to thank the anonymous referees for their suggestions and comments, which improved this paper. The first and third authors were supported by the Spanish project MTM2014-52016-C02-2-P, the Generalitat Valenciana Project PROMETEO/2016/089 and UJI project P1.1B20115-16. The second author was supported by RedIUM and MINECO (Spain) through the research network MTM2014-55580-REDT and by the mathematics institute IMAC (Castellon, Spain).

Subjects
roots, Numerical Analysis, Pure mathematics, Chebyshev–Halley family, Iterative method, polynomials, Applied Mathematics, Chebyshev systems, 010102 general mathematics, 010103 numerical & computational mathematics, dynamics, Parameter space, Fixed point, 01 natural sciences, Attraction, Chebyshev filter, Critical point (mathematics), Combinatorics, Quadratic equation, Modeling and Simulation, Polinomis, 0101 mathematics, Sistemes de Chebyshev, Mathematics
Abstract

In this paper we study the dynamical behavior of the Chebyshev–Halley methods on the family of degree n polynomials z n + c . We prove that, despite increasing the degree, it is still possible to draw the parameter space by using the orbit of a single critical point. For the methods having z = ∞ as an attracting fixed point, we show how the basins of attraction of the roots become smaller as the value of n grows. We also demonstrate that, although the convergence order of the Chebyshev–Halley family is 3, there is a member of order 4 for each value of n. In the case of quadratic polynomials, we bound the set of parameters which correspond to iterative methods with stable behaviour other than the basins of attraction of the roots.

Published
2018

4. Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces

Author

David Ilcinkas, Nicolas Hanusse, Nicolas Bonichon, Cyril Gavoille, Gavoille, Cyril, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest

Subjects
spanner, 0102 computer and information sciences, Delaunay triangulation, Computer Science::Computational Geometry, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, law.invention, Combinatorics, symbols.namesake, law, Line graph, 0101 mathematics, Beta skeleton, Mathematics, Forbidden graph characterization, Block graph, orthogonal surface, 010102 general mathematics, theta-graph, 1-planar graph, Geometric graph theory, Planar graph, realizability, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, symbols, Topological graph theory
Abstract

International audience; $\Theta_k$-graphs are geometric graphs that appear in the context of graph navigation. The shortest-path metric of these graphs is known to approximate the Euclidean complete graph up to a factor depending on the cone number $k$ and the dimension of the space. TD-Delaunay graphs, a.k.a.~triangular-distance Delaunay triangulations, introduced by Chew, have been shown to be plane $2$-spanners of the 2D Euclidean complete graph, i.e., the distance in the TD-Delaunay graph between any two points is no more than twice the distance in the plane. Orthogonal surfaces are geometric objects defined from independent sets of points of the Euclidean space. Orthogonal surfaces are well studied in combinatorics (orders, integer programming) and in algebra. From orthogonal surfaces, geometric graphs, called geodesic embeddings can be built. In this paper, we introduce a specific subgraph of the $\TG$-graph defined in the 2D Euclidean space, namely the $\DTG$-graph, composed of the even-cone edges of the $\TG$-graph. Our main contribution is to show that these graphs are exactly the TD-Delaunay graphs, and are strongly connected to the geodesic embeddings of orthogonal surfaces of coplanar points in the 3D Euclidean space. Using these new bridges between these three fields, we establish: \begin{itemize} \item Every $\TG$-graph is the union of two spanning TD-Delaunay graphs. In particular, $\TG$-graphs are $2$-spanners of the Euclidean graph, and the bound of~$2$ on the stretch factor is the best possible. It was not known that $\Theta_6$-graphs are $t$-spanners for some constant $t$, and $\Theta_7$-graphs were only known to be $t$-spanners for $t \approx 7.562$. \item Every plane triangulation is TD-Delaunay realizable, i.e., every combinatorial plane graph for which all its interior faces are triangles is the TD-Delaunay graph of some point set in the plane. Such realizability property does not hold for classical Delaunay triangulations. \end{itemize}

Published
2010

5. Euler Tour Lock-In Problem in the Rotor-Router Model

Author

Adrian Kosowski, Ralf Klasing, Evangelos Bampas, David Ilcinkas, Leszek Gąsieniec, Nicolas Hanusse, School of of Electrical and Computer Engineering [Athens] (School of E.C.E), National Technical University of Athens [Athens] (NTUA), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Liverpool], University of Liverpool, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Router, 010102 general mathematics, Eulerian path, Topology (electrical circuits), 0102 computer and information sciences, Random walk, 01 natural sciences, Complete bipartite graph, Numbering, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, Bounded function, symbols, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0101 mathematics, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics, Rotor (mathematics)
Abstract

International audience; The rotor-router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. It is known that the route in an undirected graph G=(V,E), where |V|=n and |E|=m, adopted by an agent controlled by the rotor-router mechanism forms eventually an Euler tour based on arcs obtained via replacing each edge in G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem. In recent work [Yan03] Yanovski et al. proved that independently of the initial configuration of the rotor-router mechanism in G the agent locks-in in time bounded by 2m diam, where diam is the diameter of G. This upper bound can be matched asymptotically in lollipop graphs. In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. The case study is performed in the form of a game between a player pl intending to lock-in the agent in an Euler tour as quickly as possible and its adversary ad with the counter objective. First, we observe that in certain (easy) cases the lock-in can be achieved in time O(m). On the other hand we show that if adversary ad is solely responsible for the assignment of ports and pointers, the lock-in time Omega(m diam) can be enforced in any graph with m edges and diameter diam. Furthermore, we show that if ad provides its own port numbering after the initial setup of pointers by pl, the complexity of the lock-in problem is bounded by O(m min{log m,diam}). We also propose a class of graphs in which the lock-in requires time Omega(m log m). In the remaining two cases we show that the lock-in requires time Omega(m diam) in graphs with the worst-case topology. In addition, however, we present non-trivial classes of graphs with a large diameter in which the lock-in time is O(m).

Published
2009

6. A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones

Author

Karsten Schölzel, Miguel Couceiro, Lucien Haddad, Tamás Waldhauser, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Knowledge representation, reasonning (ORPAILLEUR), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Royal Military College of Canada (RMCC), Royal Military College of Canada, Mathematics Research Unit, University of Luxembourg [Luxembourg], Bolyai Institute [Szeged], University of Szeged [Szeged], Université du Luxembourg (Uni.lu), and The authors thank the anonymous referees for their valuable comments on the previous version of this paper. L. Haddad is supported by Academic Research Program of RMC. K. Sch¨olzel is supported by the internal research project MRDO2 of the University of Luxembourg. T. Waldhauser acknowledges that the present project is supported by the Hungarian National Foundation for Scientific Research under grants no. K83219 and K104251. The present project is supported by the European Union and co-funded by the European Social Fund under the project 'Telemedicine-focused research activities on the field of Mathematics, Informatics and Medical sciences' of project number 'TAMOP-4.2.2.A-11/1/KONV-2012-0073'.

Subjects
Discrete mathematics, 021103 operations research, Parity function, Two-element Boolean algebra, 010102 general mathematics, 0211 other engineering and technologies, 02 engineering and technology, Boolean algebras canonically defined, Complete Boolean algebra, 01 natural sciences, Combinatorics, Boolean domain, Maximum satisfiability problem, Free Boolean algebra, Boolean expression, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Mathematics
Abstract

International audience; The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose total component is C. We establish some results in this direction and combine them with previous ones to show the following dichotomy result: For every total clone C on 2, the set I(C) is either finite or of continuum cardinality. 1. Preliminaries Let k ≥ 2 be an integer and let k be a k-element set. Without loss of generality we assume that k := {0,. .. , k − 1}. For a positive integer n, an n-ary partial function on k is a map f : dom (f) → k where dom (f) is a subset of k n , called the domain of f. Let Par (n) (k) denote the set of all n-ary partial functions on k and let Par(k) := n≥1