Small 3-Manifolds of Large Genus

In this paper we prove the Cheeger inequality for infinite weighted graphs endowed with 'corresponding' measure. This measure has already been developed in the study of tree lattices. Our graphs have finite volumes. A similar theory has already been developed for manifolds of finite volumes.     

Markov chains, Hamiltonian cycles and volumes of convex bodies

In this note the Hamiltonian cycle problem is mapped into an infinite horizon discounted cost constrained Markov decision problem. The occupation measure based linear polytope associated with this control problem defines a convex set which either strictly contains or is equal to another convex set, depending on whether the underlying graph has a Hamiltonian cycle or not. This allows us to distinguish Hamiltonian graphs from non-Hamiltonian graphs by comparing volumes of two convex sets.     

Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations

This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. Our motivation is in geometrically comparing relaxations in the context of mixed-integer linear and nonlinear optimization, with the goal of gaining algorithmic and modeling insights. We consider relaxations of: fixed-charge formulations, vertex packing polytopes, boolean-quadric polytopes, and relaxations of graphs of monomials on box domains. Besides surveying the area, we do give a few new results, and we provide many directions for further work.     

Flow Graphs: Analysis with Near Sets

This paper introduces a framework for flow graphs induced by perceptual systems as well as analysis of such graphs using near set theory. A distinctive feature of such graphs are layers; therefore we shall generally call them flow graphs with layers. In a specific context of perceptual systems, these graphs will referred be to as perceptual flow graphs. A method for determining nearness of flow graphs with layers (perceptual graphs) is given in terms of a practical application to digital image analysis.     

Alcoved Polytopes,I

The aim of this paper is to study alcoved polytopes, which are polytopes arising from affine Coxeter arrangements. This class of convex polytopes includes many classical polytopes, for example, the hypersimplices. We compare two constructions of triangulations of hypersimplices due to Stanley and Sturmfels and explain them in terms of alcoved polytopes. We study triangulations of alcoved polytopes, the adjacency graphs of these triangulations, and give a combinatorial formula for volumes of these polytopes. In particular, we study a class of matroid polytopes, which we call the multi-hypersimplices.     

A STRUCTURAL APPROACH TO THE REPRESENTATION OF LIFE HISTORY DATA 1

We propose a structural approach to the representation of life history data, based on an interval graph formalism. Various “life history graphs” are defined using this approach, and properties of such graphs are related to life course concepts. The analysis of life history graphs using standard network methods is illustrated, and suggestions are made regarding the use of network analysis for life course research. A duality is demonstrated between individual life history graphs and social networks, and connections between life history graph analysis and conventional life course methods are discussed.     

Simplices and Spectra of Graphs

In this note we show that the (n−2)-dimensional volumes of codimension 2 faces of an n-dimensional simplex are algebraically independent quantities of the volumes of its edge-lengths. The proof involves computation of the eigenvalues of Kneser graphs. We also show examples of families of simplices (of dimension 4 or greater) which show that the set of (n−2)-dimensional volumes of (n−2)-dimensional faces of a simplex do not determine its volume.     

Learning difficulties with solids of revolution: classroom observations

The study aims to identify areas of difficulty in learning about volumes of solids of revolution (VSOR) at a Further Education and Training college in South Africa. Students’ competency is evaluated along five skill factors which refer to knowledge skills required to succeed in performing tasks relating to applications of the definite integral, in particular to VSOR. The paper reflects on reasons for the difficulties that students experience in this topic. The study reveals that many students are not competent in drawing graphs and in interpreting the region bounded by the given graphs. If the graphs are given, students have difficulty in selecting the representative strip that is used in approximating the bounded region. Although many students are able to produce the correct formula to calculate the volume, be it a disc, washer or shell, they find it problematic to draw the three-dimensional (3D) representation of the rotated strip and the generated solid of revolution. Students seem to succeed better with tasks requiring simple manipulation skills. The study illustrates how a measure (the skill factors) can be put into practice for establishing exactly where the problems lie when students under-perform in the topic of VSOR. The results can serve as guide on how conclusions can be drawn by assessing the problematic situation through breaking it down along the framework of skill factors.     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

Witness (Delaunay) graphs

Proximity graphs are used in several areas in which a neighborliness relationship for input data sets is a useful tool in their analysis, and have also received substantial attention from the graph drawing community, as they are a natural way of implicitly representing graphs. However, as a tool for graph representation, proximity graphs have some limitations that may be overcome with suitable generalizations.We introduce a generalization, witness graphs, that encompasses both the goal of more power and flexibility for graph drawing issues and a wider spectrum for neighborhood analysis. We study in detail two concrete examples, both related to Delaunay graphs, and consider as well some problems on stabbing geometric objects and point set discrimination, that can be naturally described in terms of witness graphs.     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

三圈图的极小广义和连通指数

图的广义和连通指数作为新提出的一类分子拓扑指数, 在QSPR/QSAR 中有很大的应用价值. 树图、单圈图和双圈图的极值问题已取得很多结果, 而三圈图相关问题的研究较为复杂. 限制 - 1\leqslant \alpha < 0, 对三圈图的广义和连通指数进行了研究. 通过对三圈图的分析, 构造了一种图的变换, 指出在三圈图中广义和连通指 数的极小值必由其中的七种类型图取得. 然后通过悬挂边的变换, 最终得到三圈图广义和连通指 数的极小值并刻画了唯一的极图.     

Complexity of networks II: The set complexity of edge‐colored graphs

We previously introduced the concept of “set‐complexity,” based on a context‐dependent measure of information, and used this concept to describe the complexity of gene interaction networks. In a previous paper of this series we analyzed the set‐complexity of binary graphs. Here, we extend this analysis to graphs with multicolored edges that more closely match biological structures like the gene interaction networks. All highly complex graphs by this measure exhibit a modular structure. A principal result of this work is that for the most complex graphs of a given size the number of edge colors is equal to the number of “modules” of the graph. Complete multipartite graphs (CMGs) are defined and analyzed. The relation between complexity and structure of these graphs is examined in detail. We establish that the mutual information between any two nodes in a CMG can be fully expressed in terms of entropy, and present an explicit expression for the set complexity of CMGs (Theorem 3). An algorithm for generating highly complex graphs from CMGs is described. We establish several theorems relating these concepts and connecting complex graphs with a variety of practical network properties. In exploring the relation between symmetry and complexity we use the idea of a similarity matrix and its spectrum for highly complex graphs. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

On the planarity of Hanoi graphs

Hanoi graphs are the state graphs for Tower of Hanoi problems with three or more pegs. We prove hamiltonicity and present a complete analysis of planarity of these graphs.     

图的最小填充的分解定理

在计算数学领域,稀疏矩阵的最小填充排序问题由于其重要的实际意义而受到重视。本文从图论的观点提出一种处理方法,即运用分解定理来处理一些特殊结构,从而导出一些特殊图的最小填充数。     

Spectral bounds for the independence ratio and the chromatic number of an operator

We define the independence ratio and the chromatic number for bounded, self-adjoint operators on an L ²-space by extending the definitions for the adjacency matrix of finite graphs. In analogy to the Hoffman bounds for finite graphs, we give bounds for these parameters in terms of the numerical range of the operator. This provides a theoretical framework in which many packing and coloring problems for finite and infinite graphs can be conveniently studied with the help of harmonic analysis and convex optimization. The theory is applied to infinite geometric graphs on Euclidean space and on the unit sphere.