Regularity lemmas in a Banach space setting

Szemerédi’s regularity lemma is a fundamental tool in extremal graph theory, theoretical computer science and combinatorial number theory. Lovász and Szegedy (2007) gave a Hilbert space interpretation of the lemma and an interpretation in terms of compactness of the space of graph limits. In this paper we prove several compactness results in a Banach space setting, generalising results of Lovász and Szegedy (2007) as well as a result of Borgs et al. (2014).     

Sphere Packings, VI. Tame Graphs and Linear Programs

This paper is the sixth and final part in a series of papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In a previous paper in this series, a continuous function f on a compact space is defined, certain points in the domain are conjectured to give the global maxima, and the relation between this conjecture and the Kepler conjecture is established. In this paper we consider the set of all points in the domain for which the value of f is at least the conjectured maximum. To each such point, we attach a planar graph. It is proved that each such graph must be isomorphic to a tame graph, of which there are only finitely many up to isomorphism. Linear programming methods are then used to eliminate all possibilities, except for three special cases treated in earlier papers: pentahedral prisms, the face-centered cubic packing, and the hexagonal-close packing. The results of this paper rely on long computer calculations.     

Chain graph interpretations and their relations revisited

In this paper we study how different theoretical concepts of Bayesian networks have been extended to chain graphs. Today there exist mainly three different interpretations of chain graphs in the literature. These are the Lauritzen–Wermuth–Frydenberg, the Andersson–Madigan–Perlman and the multivariate regression interpretations. The different chain graph interpretations have been studied independently and over time different theoretical concepts have been extended from Bayesian networks to also work for the different chain graph interpretations. This has however led to confusion regarding what concepts exist for what interpretation.In this article we do therefore study some of these concepts and how they have been extended to chain graphs as well as what results have been achieved so far. More importantly we do also identify when the concepts have not been extended and contribute within these areas. Specifically we study the following theoretical concepts: Unique representations of independence models, the split and merging operators, the conditions for when an independence model representable by one chain graph interpretation can be represented by another chain graph interpretation and finally the extension of Meek's conjecture to chain graphs. With our new results we give a coherent overview of how each of these concepts is extended for each of the different chain graph interpretations.     

A note on Fiedler vectors interpreted as graph realizations

The second smallest eigenvalue of the Laplace matrix of a graph and its eigenvectors, also known as Fiedler vectors in spectral graph partitioning, carry significant structural information regarding the connectivity of the graph. Using semidefinite programming duality, we offer a geometric interpretation of this eigenspace as optimal solution to a graph realization problem. A corresponding interpretation is also given for the eigenspace of the maximum eigenvalue of the Laplacian.     

Categorical principles,techniques and results for high-level-replacement systems in computer science

The aim of this paper is to give an introduction how to use categorical methods in a specific field of computer science: The field of high-level-replacement systems has its roots in the well-established theories of formal languages, term rewriting, Petri nets, and graph grammars playing a fundamental role in computer science. More precisely, it is a generalization of the algebraic approach to graph grammars which is based on gluing constructions for graphs defined as pushouts in the category of graphs. The categorical theory of high-level-replacement systems is suitable for the dynamic handling of a large variety of high-level structures in computer science including different kinds of graphs and algebraic specifications. In this paper we discuss the basic principles and techniques from category theory applied in the field of high-level-replacement systems and present some basic results together with the corresponding categorical proof techniques.     

An interrelation between line graphs,eigenvalues, and matroids

If L(G) is the line graph of G, and A(L(G)), the adjacency matrix of L(G), acts on a vector x, this vector may be thought of as an integral chain of G. The eigenspace of L(G) determines a matroid for G. For the eigenvalue ?2, this matroid has a geometric interpretation, and from this we obtain all eigenvectors corresponding to this eigenvalue. Matroids are normally considered over integral domains, and the results for eigenvectors are generalized to a geometric interpretation for all integral domains. These results are applied to the ring of complex numbers, and strict bounds for the least eigenvalue of a line graph are obtained.     

Multitriangulations, Pseudotriangulations and Primitive Sorting Networks

We study the set of all pseudoline arrangements with contact points which cover a given support. We define a natural notion of flip between these arrangements and study the graph of these flips. In particular, we provide an enumeration algorithm for arrangements with a given support, based on the properties of certain greedy pseudoline arrangements and on their connection with sorting networks. Both the running time per arrangement and the working space of our algorithm are polynomial. As the motivation for this work, we provide in this paper a new interpretation of both pseudotriangulations and multitriangulations in terms of pseudoline arrangements on specific supports. This interpretation explains their common properties and leads to a natural definition of multipseudotriangulations, which generalizes both. We study elementary properties of multipseudotriangulations and compare them to iterations of pseudotriangulations.     

The smallest graph of girth 6 and valency 7

With the aid of a computer. we give a regular graph of girth 6 and valency 7, which has 90 vertices and show that this is the unique smallest graph with these properties.     

Chromatic Polynomials and the Symmetric Group

In this paper we give first a new combinatorial interpretation of the coefficients of chromatic polynomials of graphs in terms of subsets of permutations. Motivated by this new interpretation, we introduce next a combinatorially defined polynomial associated to a directed graph, and prove that it is related to chromatic polynomials. These polynomials are a specialization of cover polynomials of digraphs.I am grateful to the Swiss National Science Foundation for its partial financial supportFinal version received: June 25, 2003     

On expressiveness of the chain graph interpretations

In this article we study the expressiveness of the different chain graph interpretations. Chain graphs is a class of probabilistic graphical models that can contain two types of edges, representing different types of relationships between the variables in question. Chain graphs is also a superclass of directed acyclic graphs, i.e. Bayesian networks, and can thereby represent systems more accurately than this less expressive class of models. Today there do however exist several different ways of interpreting chain graphs and what conditional independences they encode, giving rise to different so-called chain graph interpretations. Previous research has approximated the number of representable independence models for the Lauritzen–Wermuth–Frydenberg and the multivariate regression chain graph interpretations using an MCMC based approach. In this article we use a similar approach to approximate the number of models representable by the latest chain graph interpretation in research, the Andersson–Madigan–Perlman interpretation. Moreover we summarize and compare the different chain graph interpretations with each other. Our results confirm previous results that directed acyclic graphs only can represent a small fraction of the models representable by chain graphs, even for a low number of nodes. The results also show that the Andersson–Madigan–Perlman and multivariate regression interpretations can represent about the same amount of models and twice the amount of models compared to the Lauritzen–Wermuth–Frydenberg interpretation. However, at the same time almost all models representable by the latter interpretation can only be represented by that interpretation while the former two have a large intersection in terms of representable models.     

The Endogenous Analysis of Flows,with Applications to Migrations,Social Mobility and Opinion Shifts

For exponential random graph models, under quite general conditions, it is proved that induced subgraphs on node sets disconnected from the other nodes still have distributions from an exponential random graph model. This can help in the theoretical interpretation of such models. An application is that for saturated snowball samples from a potentially larger graph which is a realization of an exponential random graph model, it is possible to do the analysis of the observed snowball sample within the framework of exponential random graph models without any knowledge of the larger graph.     

Fractions,Decimals,and Percents

<正>When am I ever going to use this'?Surveys The graph shows the results of a survey in which teens were asked to name the most important invention of the 20th century.1.What percent of the teens said that the personal computer was the most important invention?2.How is this percent written as a ratio?     

On imposing connectivity constraints in integer programs

We study an extension of the classical graph cut problem, wherein we replace the modular (sum of edge weights) cost function by a submodular set function defined over graph edges. Special cases of this problem have appeared in different applications in signal processing, machine learning, and computer vision. In this paper, we connect these applications via the generic formulation of “cooperative graph cuts”, for which we study complexity, algorithms, and connections to polymatroidal network flows. Finally, we compare the proposed algorithms empirically.     

A Toughness Condition for Fractional (k,m)-deleted Graphs Revisited

In computer networks, toughness is an important parameter which is used to measure the vulnerability of the network. Zhou et al. obtains a toughness condition for a graph to be fractional (k, m)-deleted and presents an example to show the sharpness of the toughness bound. In this paper, we remark that the previous example does not work and inspired by this fact, we present a new toughness condition for fractional (k, m)-deleted graphs improving the existing one. Finally, we state an open problem.     

Numerical enclosure for multiple eigenvalues of an Hermitian matrix whose graph is a tree

In this paper we consider a numerical enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. If an Hermitian matrix A whose graph is a tree has multiple eigenvalues, it has the property that matrices which are associated with some branches in the undirected graph of A have the same eigenvalues. By using this property and interlacing inequalities for Hermitian matrices, we show an enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. Since we do not generally know whether a given matrix has exactly a multiple eigenvalue from approximate computations, we use the property of interlacing inequalities to enclose some eigenvalues including multiplicities.In this process, we only use the enclosure of simple eigenvalues to enclose a multiple eigenvalue by using a computer and interval arithmetic.     

Graph spectra in Computer Science

In this paper, we shall give a survey of applications of the theory of graph spectra to Computer Science. Eigenvalues and eigenvectors of several graph matrices appear in numerous papers on various subjects relevant to information and communication technologies. In particular, we survey applications in modeling and searching Internet, in computer vision, data mining, multiprocessor systems, statistical databases, and in several other areas. Some related new mathematical results are included together with several comments on perspectives for future research. In particular, we claim that balanced subdivisions of cubic graphs are good models for virus resistent computer networks and point out some advantages in using integral graphs as multiprocessor interconnection networks.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems

In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.     

Efficient bounds on a branch and bound algorithm for graph colouration

By a proper colouring of a simple graph, we mean an assignment of colours to its vertices with adjacent vertices receiving different colours. Applications of this graph‐theoretic modelling are numerous, especially in the areas of scheduling and timetabling. We shall refer to a proper colouration that uses a smallest possible number of colours as a minimum (proper) colouration. This number for the graph is simply its chromatic number, the determination of which is well known to be a ‘hard’ problem. In this paper, from the computational point of view of actually constructing a colouration, we examine a simple coalescence/expansion procedure that bases on the branch and bound technique improved by efficient bounding conditions. They include various tightened fathoming criteria as well as complete subgraph determination. For the computer implementation, we also look at the issues of branching rules and the decomposition of solution tree. With these efforts, empirical results show that minimum colourations can be constructed for moderate size graphs, with ‘good’ solutions computed for problems of up to about forty vertices.     

The Hamiltonian connectivity of rectangular supergrid graphs

A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph.