组合拓扑方法在组合学和图论中的应用

本文介绍组合拓扑方法在图论和组合学中的应用，探索一些新的离散问题和连续问题的关系，介绍目前有关这方面的新结果及发展动向。本文主要介绍同调理论在图论中的应用，与图有关的复形及性质，不动点定理在离散问题中的应用等。文中提出了一些新结果及可供研究的新问题。     

Some fixed point results on a metric space with a graph

Combining some branches is a typical activity in different fields of science, especially in mathematics. Naturally, it is notable in fixed point theory. Over the past few decades, there have been a lot of activity in fixed point theory and another branches in mathematics such differential equations, geometry and algebraic topology. In 2006, Espinola and Kirk made a useful contribution on combining fixed point theory and graph theory. Recently, Reich and Zaslavski studied a new inexact iterative scheme for fixed points of contractive and nonexpansive multifunctions. In this paper, by using main idea of their work and the idea of combining fixed point theory and graph theory, we present some iterative scheme results for G-contractive and G-nonexpansive mappings on graphs.     

Upper semifinite hyperspaces as unifying tools in normal Hausdorff topology

In this paper we use the upper semifinite topology in hyperspaces to get results in normal Hausdorff topology. The advantage of this point of view is that the upper semifinite topology, although highly non-Hausdorff, is very easy to handle. By this way we treat different topics and relate topological properties on spaces with some topological properties in hyperspaces. This hyperspace is, of course, determined by the base space. We prove here some reciprocals which are not true for the usual Vietoris topology. We also point out that this framework is a very adequate one to construct the ?ech-Stone compactification of a normal space. We also describe compactness in terms of the second countability axiom and of the fixed point property. As a summary we relate non-Hausdorff topology with some facts in the core of normal Hausdorff topology. In some sense, we reinforce the unity of the subject.     

Développements récents de la théorie des graphies

Stimulated by its numerous applications, the theory of graphs continuously progresses in various domains. The concept of graph in itself varies in accordance with authors and problems considered: it belongs to the logic of sets as well as to combinatorial topology. Questions may be grouped into three main classes: the study of characteristic properties (invariants such as connectivity, existence of Hamiltonian circuits, Ramsey numbers); problems of embedding on surfaces (planarity, genus, thickness) and of graph-coloring; and enumeration of given classes of graphs, a peculiarly difficult field of investigation. Hypergraphs present a generalization of graphs from a set theoretic point of view. In spite of its rapid growth, graph theory has not yet reached its deep unity.     

Star clusters in independence complexes of graphs

We introduce the notion of star cluster of a simplex in a simplicial complex. This concept provides a general tool to study the topology of independence complexes of graphs. We use star clusters to answer a question arisen from works of Engström and Jonsson on the homotopy type of independence complexes of triangle-free graphs and to investigate a large number of examples which appear in the literature. We present an alternative way to study the chromatic and clique numbers of a graph from a homotopical point of view and obtain new results regarding the connectivity of independence complexes.     

Multiobjective traveling salesperson problem on Halin graphs

In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially solvable combinations.     

Some recent results in metric fixed point theory

This is a survey of recent results on best approximation and fixed point theory in certain geodesic spaces. Some of these results are related to fundamental fixed point theorems in topology that have been known for many years. However the metric approach is emphasized here. Dedicated to Edward Fadell and Albrecht Dold on the occasion of their 80th birthdays     

On the Hardness of Approximating the Chromatic Number

k -colorable for some fixed . Our main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. As an immediate corollary we obtain that it is NP-hard to color a k-chromatic graph with at most colors. We also give simple proofs of two results of Lund and Yannakakis [20]. The first result shows that it is NP-hard to approximate the chromatic number to within for some fixed ε > 0. We point here that this hardness result applies only to graphs with large chromatic numbers. The second result shows that for any positive constant h, there exists an integer , such that it is NP-hard to decide whether a given graph G is -chromatic or any coloring of G requires colors. Received April 11, 1997/Revised June 10, 1999     

Mild solutions of evolution quantum stochastic differential equations with nonlocal conditions

We study existence of a unique mild solution of evolution quantum stochastic differential equations with nonlocal conditions under the strong topology. Using the method of successive approximations, we do not need to transform the nonlocal problem to a fixed point form. The evolution operator A generates a family of semigroup that are continuous. Nonlocal conditions allow additional measurements of certain phenomena that cannot be captured by the traditional initial conditions. We show that under some given conditions, the mild solution is unique and also stable. The method applied here is much easier when compared with previous methods used in literature.     

On an equivalence of topological vector space valued cone metric spaces and metric spaces

Scalarization method is an important tool in the study of vector optimization as corresponding solutions of vector optimization problems can be found by solving scalar optimization problems. Recently this has been applied by Du (2010) [14] to investigate the equivalence of vectorial versions of fixed point theorems of contractive mappings in generalized cone metric spaces and scalar versions of fixed point theorems in general metric spaces in usual sense. In this paper, we find out that the topology induced by topological vector space valued cone metric coincides with the topology induced by the metric obtained via a nonlinear scalarization function, i.e any topological vector space valued cone metric space is metrizable, prove a completion theorem, and also obtain some more results in topological vector space valued cone normed spaces.     

Compact Compatible Topologies for Posets and Graphs

A topology on the vertex set of a comparability graph G is said to be compatible (respectively, weakly compatible) with G if each induced subgraph (respectively, each finite induced subgraph) is topologically connected if and only it it is graph-connected; a weakly compatible topology on the vertex set of a graph completely determines the graph structure. We consider here the problem of deciding whether or not a comparability graph has a compact compatible or weakly compatible topology and in the case of graphs with small cycles, hence in the case of trees, we give a characterization.     

Disconnected Colors in Generalized Gallai‐Colorings

Gallai‐colorings of complete graphs—edge colorings such that no triangle is colored with three distinct colors—occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper), information theory and the theory of perfect graphs. A basic property of Gallai‐colorings with at least three colors is that at least one of the color classes must span a disconnected graph. We are interested here in whether this or a similar property remains true if we consider colorings that do not contain a rainbow copy of a fixed graph F. We show that such graphs F are very close to bipartite graphs, namely, they can be made bipartite by the removal of at most one edge. We also extend Gallai's property for two infinite families and show that it also holds when F is a path with at most six vertices.     

Non-parametric radially symmetric mean curvature flow with a free boundary

We study the mean curvature flow of radially symmetric graphs with prescribed contact angle on a fixed, smooth hypersurface in Euclidean space. In this paper we treat two distinct problems. The first problem has a free Neumann boundary only, while the second has two disjoint boundaries, a free Neumann boundary and a fixed Dirichlet height. We separate the two problems and prove that under certain initial conditions we have either long time existence followed by convergence to a minimal surface, or finite maximal time of existence at the end of which the graphs develop a curvature singularity. We also give a rate of convergence for the singularity.     

Uniform random colored complexes

We present here random distributions on (D + 1)‐edge‐colored, bipartite graphs with a fixed number of vertices 2p. These graphs encode D‐dimensional orientable colored complexes. We investigate the behavior of those graphs as p→∞. The techniques involved in this study also yield a Central Limit Theorem for the genus of a uniform map of order p, as p→∞.     

Parameterized complexity of even/odd subgraph problems

We study the parameterized complexity of the problems of determining whether a graph contains a k-edge subgraph (k-vertex induced subgraph) that is a Π-graph for Π-graphs being one of the following four classes of graphs: Eulerian graphs, even graphs, odd graphs, and connected odd graphs. We also consider the parameterized complexity of their parametric dual problems.For these sixteen problems, we show that eight of them are fixed parameter tractable and four are W[1]-hard. Our main techniques are the color-coding method of Alon, Yuster and Zwick, and the random separation method of Cai, Chan and Chan.     

Consensus problems in discrete-time multiagent systems with fixed topology

In this paper, we study the consensus problems in discrete-time multiagent systems with fixed topology. A necessary and sufficient condition for a system that solves a consensus problem is established, and the structure of consensus functions is characterized. Based on them, we introduce the standard topologies (graphs) of information flow, with which the systems can be viewed as single-leader-multi-follower systems. Moreover, the convex combination of these topologies can create a system that solves any predeterminate consensus problem. Additionally, we characterize the structural decomposition—the leaders-followers decomposition of a multiagent system, and establish a necessary and sufficient condition for an agent to be a leader.     

Homotopical intersection theory, II: equivariance

This paper is a sequel to (Klein and Williams in Geom Topol 11:939–977, 2007). We develop here an intersection theory for manifolds equipped with an action of a finite group. As in Klein and Williams (2007), our approach will be homotopy theoretic, enabling us to circumvent the specter of equivariant transversality. We give applications of our theory to embedding problems, equivariant fixed point problems and the study of periodic points of self maps.     

Planarity and Edge Poset Dimension

Different areas of discrete mathematics lead to instrinsically different characterizations of planar graphs. Planarity is expressed in terms of topology, combinatorics, algebra or search trees. More recently, Schnyder's work has related planarity to partial order theory. Acyclic orientations and associated edge partial orders lead to a new characterization of planar graphs, which also describes all of the possible planar embeddings. We prove here that there is a bijection between bipolar plane digraphs and 2-dimensionalN-free partial orders. We give also a characterization of planarity in terms of 2-colorability of a graph and provide a short proof of a previous result on planar lattices.     

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

Symplectic geometry,minors and graph Laplacians

In my talk, I will present some works done in the nineties on Laplacians on graphs: from eigenvalue problems to inverse problem for resistor networks. I will focus on the motivations and the main results as well as on the main ideas:

• •A differential topology point of view on the minor relation: a nice stratification associated to a finite graph Γ whose strata are associated to the minors of Γ
• •“Discrete” (graphs) versus “continuous” (Riemannian manifolds)
• •Stability of spectra with respect to singular limits: a finite dimensional theory of operators with domains (Von Neumann theory).

The link with topology will appear in some results about my graph parameter μ, in particular the planarity and the linkless embedding properties.