CiteULike: AbnerCYH's topology

The complexity of Tarski's fixed point theorem

Ching-Lueh Chang — 2008-06-26T09:50:21-00:00

Theoretical Computer Science, Vol. 401, No. 1-3. (23 July 2008), pp. 228-235.

Tarski's fixed point theorem guarantees the existence of a fixed point of an order-preserving function f:L-->L defined on a nonempty complete lattice (L,[not precedes, equals]) [B. Knaster, Un théorème sur les fonctions d'ensembles, Annales de la Société Polonaise de Mathématique 6 (1928) 133-134; A. Tarski, A lattice theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics 5 (1955) 285-309]. In this paper, we investigate several algorithmic and complexity-theoretic topics regarding Tarski's fixed point theorem. In particular, we design an algorithm that finds a fixed point of f when it is given (L,[not precedes, equals]) as input and f as an oracle. Our algorithm makes O(log|L|) queries to f when [not precedes, equals] is a total order on L. We also prove that when both f and (L,[not precedes, equals]) are given as oracles, any deterministic or randomized algorithm for finding a fixed point of f makes an expected [Omega](|L|) queries for some (L,[not precedes, equals]) and f.

Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge

Michael Saks — 2008-06-20T10:57:37-00:00

SIAM Journal on Computing, Vol. 29, No. 5. (2000), pp. 1449-1483.

Shellable Nonpure Complexes and Posets. II

Anders Bjorner — 2008-05-27T08:00:27-00:00

Vol. 349, No. 10. (October 1997), pp. 3945-3975.

Shellable Nonpure Complexes and Posets. I

Anders Bjorner — 2008-05-27T07:58:17-00:00

Transactions of the American Mathematical Society, Vol. 348, No. 4. (April 1996), pp. 1299-1367.

Shellable graphs and sequentially Cohen-Macaulay bipartite graphs

Adam Van Tuyl — 2008-05-20T04:00:55-00:00

Journal of Combinatorial Theory, Series A, Vol. 115, No. 5. (July 2008), pp. 799-814.

Associated to a simple undirected graph G is a simplicial complex [Delta]G whose faces correspond to the independent sets of G. We call a graph G shellable if [Delta]G is a shellable simplicial complex in the non-pure sense of Björner-Wachs. We are then interested in determining what families of graphs have the property that G is shellable. We show that all chordal graphs are shellable. Furthermore, we classify all the shellable bipartite graphs; they are precisely the sequentially Cohen-Macaulay bipartite graphs. We also give a recursive procedure to verify if a bipartite graph is shellable. Because shellable implies that the associated Stanley-Reisner ring is sequentially Cohen-Macaulay, our results complement and extend recent work on the problem of determining when the edge ideal of a graph is (sequentially) Cohen-Macaulay. We also give a new proof for a result of Faridi on the sequentially Cohen-Macaulayness of simplicial forests.

Topological Methods in Combinatorics and Geometry

Jiri Matousek — 2008-04-20T05:54:00-00:00

simplicial complexes : : : : : : : : : : : : : : : : : : : 4 1.4 Simplicial mappings : : : : : : : : : : : : : : : : : : : : : : : : 5 1.5 Correspondence between posets and simplicial complexes : : : 5 2 The theorem of Borsuk and Ulam 6 2.1 Several equivalent formulations : : : : : : : : : : : : : : : : : : 6 2.2 A combinatorial proof of the Borsuk-Ulam theorem : : : : : : : 7 2.3 Application: The necklace problem : : : : : : : : : : : : : : : : 9 2.4 Application: The ham-sandwich theorem : : ...

Complexes of Graphs with Bounded Matching Size

Svante Linusson — 2008-04-14T10:00:17-00:00

Journal of Algebraic Combinatorics, Vol. 27, No. 3. (10 May 2008), pp. 331-349.

Abstract For positive integers k,n, we investigate the simplicial complex of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r,s and k the simplicial complex of all bipartite graphs G on bipartition such that there is no matching of size k in G, and obtain results similar to those obtained for .

Notes on topological vector spaces

Stephen Semmes — 2008-03-28T16:50:53-00:00

(13 Apr 2003)

These are some informal notes concerning topological vector spaces, with a brief overview of background material and basic notions, and emphasis on examples related to classical analysis.

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

Hans Bodlaender — 2008-03-26T09:05:48-00:00

SIAM Journal on Computing, Vol. 25, No. 6. (1996), pp. 1305-1317.

Domination, Fractional Domination, 2-Packing, and Graph Products

David Fisher — 2007-02-18T23:54:52-00:00

SIAM Journal on Discrete Mathematics, Vol. 7, No. 3. (1994), pp. 493-498.

A digital analogue of the Jordan curve theorem

J Slapal — 2008-03-22T18:17:55-00:00

Discrete Applied Mathematics, Vol. 139, No. 1-3. (30 April 2004), pp. 231-251.

We study certain closure operations on , with the aim of showing that they can provide a suitable framework for solving problems of digital topology. The Khalimsky topology on , which is commonly used as a basic structure in digital topology nowadays, can be obtained as a special case of the closure operations studied. By proving an analogy of the Jordan curve theorem for these closure operations, we show that they provide a convenient model of the real plane and can therefore be used for studying topological and geometric properties of digital images. We also discuss some advantages of the closure operations investigated over the Khalimsky topology.

Digital manifolds: an intuitive definition and some properties

Li Chen — 2008-03-22T18:17:37-00:00

(1993), pp. 459-460.

Topological properties of closed digital spaces: One method of constructing digital models of closed continuous surfaces by using covers

Alexander Evako — 2008-03-22T18:17:35-00:00

Computer Vision and Image Understanding, Vol. 102, No. 2. (May 2006), pp. 134-144.

This paper studies properties of closed digital n-dimensional spaces, which are digital models of continuous n-dimensional closed surfaces. We show that the minimal number of points in a closed digital n-dimensional space is 2n + 2 points. A closed digital n-dimensional space with 2n + 2 points is the minimal n-dimensional sphere, which is the join of n + 1 copies of the 0-dimensional sphere. We prove that a closed digital n-dimensional space cannot contain a closed digital n-dimensional subspace, which is different from the space itself. We introduce the general definition of a closed digital space and prove that a closed digital space is necessarily a closed digital n-dimensional space. Finally, we present conditions which guarantee that every digitization process preserves important topological and geometric properties of continuous closed 2-surfaces. These conditions also allow us to determine the correct digitization resolution for a given closed 2-surface.

Digital Jordan Curve Theorems

Christer Kiselman — 2008-03-22T18:14:47-00:00

Discrete Geometry for Computer Imagery (2000), pp. 46-56.

Efim Khalimsky’s digital Jordan curve theorem states that the complement of a Jordan curve in the digital plane equipped with the Khalimsky topology has exactly two connectivity components. We present a new, short proof of this theorem using induction on the Euclidean length of the curve. We also prove that the theorem holds with another topology on the digital plane but then only for a restricted class of Jordan curves.

Discrete Jordan Curve Theorems

Andrew Vince — 2008-03-22T18:13:33-00:00

Journal of Combinatorial Theory, Series B, Vol. 47, No. 3. (December 1989), pp. 251-261.

Discrete versions of the Jordan Curve Theorem are proved.

Two Discrete Forms of the Jordan Curve Theorem

Lawrence Stout — 2008-03-22T18:11:17-00:00

The American Mathematical Monthly, Vol. 95, No. 4. (1988), pp. 332-336.

The Jordan Curve Theorem

RH Bing — 2008-03-22T18:05:37-00:00

The American Mathematical Monthly, Vol. 67, No. 7. (1960), pp. 29-34.

Order-Optimal Consensus through Randomized Path Averaging

F Benezit — 2008-02-21T01:28:54-00:00

(19 Feb 2008)

Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust message-passing schemes for distributed information processing over networks. However for many topologies that are realistic for wireless ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding ($O(n^2)$ messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a $\sqrtn$ factor, by exploiting geographic information to enable multi-hop long distance communications. In this paper we prove that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional $\sqrtn$ factor and is order optimal ($O(n)$ messages) for grids and random geometric graphs. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities, which can give bounds on the performance of randomized message-passing algorithms operating over various graph topologies.

Topological permutation entropy

Jose Amigo — 2007-11-26T13:38:44-00:00

Physica D: Nonlinear Phenomena, Vol. 231, No. 2. (15 July 2007), pp. 137-142.

Permutation entropy quantifies the diversity of possible ordering of the successively observed values a random or deterministic system can take, just as Shannon entropy quantifies the diversity of the values themselves. When the observable or state variable has a natural order relation, making permutation entropy possible to compute, then the asymptotic rate of growth in permutation entropy with word length forms an alternative means of describing the intrinsic entropy rate of a source. Herein, extending a previous result on metric entropy rate, we show that the topological permutation entropy rate for expansive maps equals the conventional topological entropy rate familiar from symbolic dynamics. This result is not limited to one-dimensional maps.

Algorithmic Aspects of a General Modular Decomposition Theory

Binh-Minh Bui-Xuan — 2007-11-21T16:30:21-00:00

(20 Nov 2007)

A new general decomposition theory inspired from modular graph decomposition is presented. This helps unifying modular decomposition on different structures, including (but not restricted to) graphs. Moreover, even in the case of graphs, the terminology “module” not only captures the classical graph modules but also allows to handle 2-connected components, star-cutsets, and other vertex subsets. The main result is that most of the nice algorithmic tools developed for modular decomposition of graphs still apply efficiently on our generalisation of modules. Besides, when an essential axiom is satisfied, almost all the important properties can be retrieved. For this case, an algorithm given by Ehrenfeucht, Gabow, McConnell and Sullivan 1994 is generalised and yields a very efficient solution to the associated decomposition problem.

A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension

Michel Habib — 2007-11-21T16:27:20-00:00

Algorithm Theory - SWAT 2004, Vol. 3111 (2004), pp. 187-198.

The first polynomial time algorithm () for modular decomposition appeared in 1972 [8] and since then there have been incremental improvements, eventually resulting in linear-time algorithms [22,7,23,9]. Although having optimal time complexity these algorithms are quite complicated and difficult to implement. In this paper we present an easily implementable linear-time algorithm for modular decomposition. This algorithm uses the notion of factorizing permutation and a new data-structure, the Ordered Chain Partitions.

Studying Recommendation Algorithms by Graph Analysis

Batul Mirza — 2007-11-09T09:46:16-00:00

Journal of Intelligent Information Systems, Vol. 20, No. 2. (1 March 2003), pp. 131-160.

We present a novel framework for studying recommendation algorithms in terms of the 'jumps' that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset and allows us to consider questions relating algorithmic parameters to properties of the datasets. For instance, given a particular algorithm 'jump,' what is the average path length from a person to an artifact? Or, what choices of minimum ratings and jumps maintain a connected graph? We illustrate the approach with a common jump called the 'hammock' using movie recommender datasets.

The Discrete Fundamental Group of the Order Complex of $B_n$

Hélène Barcelo — 2007-11-07T12:25:51-00:00

(6 Nov 2007)

A few years ago Kramer and Laubenbacher introduced a discrete notion of homotopy for simplicial complexes. In this paper, we compute the discrete fundamental group of the order complex of the Boolean lattice. As it turns out, it is equivalent to computing the discrete homotopy group of the 1-skeleton of the permutahedron. To compute this group we introduce combinatorial techniques that we believe will be helpful in computing discrete fundamental groups of other polytopes. More precisely, we use the language of words, over the alphabet of simple transpositions, to obtain conditions that are necessary and sufficient to characterize the equivalence classes of cycles. The proof requires only simple combinatorial arguments. As a corollary, we also obtain a combinatorial proof of the fact that the first Betti number of the complement of the 3-equal arrangement is equal to $2^n-3(n^2-5n+8)-1.$ This formula was originally obtained by Björner and Welker in 1995.

The Strength of Weak Ties: A Network Theory Revisited

Mark Granovetter — 2005-03-29T00:45:33-00:00

Sociological Theory, Vol. 1 (1983), pp. 201-233.

In this chapter I review empirical studies directly testing the hypotheses of my 1973 paper "The Strength of Weak Ties" (hereafter "SWT") and work that elaborates those hypotheses theoretically or uses them to suggest new empirical research not discussed in my original formulation. Along the way, I will reconsider various aspects of the theoretical argument, attempt to plug some holes, and broaden its base.

The Strength of Weak Ties

Mark Granovetter — 2005-02-20T23:47:44-00:00

The American Journal of Sociology, Vol. 78, No. 6. (1973), pp. 1360-1380.

Analysis of social networks is suggested as a tool for linking micro and macro levels of sociological theory. The procedure is illustrated by elaboration of the macro implications of one aspect of small-scale interaction: the strength of dyadic ties. It is argued that the degree of overlap of two individuals' friendship networks varies directly with the strength of their tie to one another. The impact of this principle on diffusion of influence and information, mobility opportunity, and community organization is explored. Stress is laid on the cohesive power of weak ties. Most network models deal, implicitly, with strong ties, thus confining their applicability to small, well-defined groups. Emphasis on weak ties lends itself to discussion of relations between groups and to analysis of segments of social structure not easily defined in terms of primary groups.

Empirical Analysis of an Evolving Social Network

Gueorgi Kossinets — 2006-01-07T17:06:32-00:00

Science, Vol. 311, No. 5757. (6 January 2006), pp. 88-90.

Social networks evolve over time, driven by the shared activities and affiliations of their members, by similarity of individuals' attributes, and by the closure of short network cycles. We analyzed a dynamic social network comprising 43,553 students, faculty, and staff at a large university, in which interactions between individuals are inferred from time-stamped e-mail headers recorded over one academic year and are matched with affiliations and attributes. We found that network evolution is dominated by a combination of effects arising from network topology itself and the organizational structure in which the network is embedded. In the absence of global perturbations, average network properties appear to approach an equilibrium state, whereas individual properties are unstable.

Power-law distributions in empirical data

Aaron Clauset — 2007-06-13T16:25:35-00:00

(7 Jun 2007)

Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the empirical detection and characterization of power laws is made difficult by the large fluctuations that occur in the tail of the distribution. In particular, standard methods such as least-squares fitting are known to produce systematically biased estimates of parameters for power-law distributions and should not be used in most circumstances. Here we describe statistical techniques for making accurate parameter estimates for power-law data, based on maximum likelihood methods and the Kolmogorov-Smirnov statistic. We also show how to tell whether the data follow a power-law distribution at all, defining quantitative measures that indicate when the power law is a reasonable fit to the data and when it is not. We demonstrate these methods by applying them to twenty-four real-world data sets from a range of different disciplines. Each of the data sets has been conjectured previously to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data while in others the power law is ruled out.

Characterization of complex networks: A survey of measurements

Luciano — 2005-10-17T16:49:02-00:00

(30 Jun 2005)

Each complex network (or class of networks) presents specific topological features which characterize its connectivity and highly influence the dynamics and function of processes executed on the network. The analysis, discrimination, and synthesis of complex networks therefore rely on the use of measurements capable of expressing the most relevant topological features. This article presents a survey of such measurements. It includes general considerations about complex network characterization, a brief review of the principal models, and the presentation of the main existing measurements organized into classes. Special attention is given to relating complex network analysis with the areas of pattern recognition and feature selection, as well as on surveying some concepts and measurements from traditional graph theory which are potentially useful for complex network research. Depending on the network and the analysis task one has in mind, a specific set of features may be chosen. It is hoped that the present survey will help the identification of suitable measurements.

Elements of Algebraic Topology

James Munkres — 2007-10-31T17:40:49-00:00

(01 December 1993)

Systems Analysis by Graphs and Matroids: Structural Solvability and Controllability (Algorithms and Combinatorics, Vol 3)

Kazuo Murota — 2007-10-31T16:52:10-00:00

(02 July 1987)

Recent technology involves large-scale physical or engineering systems consisting of thousands of interconnected elementary units. This monograph illustrates how engineering problems can be solved using the recent results of combinatorial mathematics through appropriate mathematical modeling. The structural solvability of a system of linear or nonlinear equations as well as the structural controllability of a linear time-invariant dynamical system are treated by means of graphs and matroids. Special emphasis is laid on the importance of relevant physical observations to successful mathematical modelings. The reader will become acquainted with the concepts of matroid theory and its corresponding matroid theoretical approach. This book is of interest to graduate students and researchers.

Linear Programming Duality: An Introduction to Oriented Matroids (Universitext)

Achim Bachem — 2007-10-31T16:48:45-00:00

(26 August 1992)

This book presents an elementary introduction to the theory of oriented matroids. The way oriented matroids are intro- duced emphasizes that they are the most general - and hence simplest - structures for which linear Programming Duality results can be stated and proved. The main theme of the book is duality. Using Farkas' Lemma as the basis the authors start withre- sults on polyhedra in Rn and show how to restate the essence of the proofs in terms of sign patterns of oriented ma- troids. Most of the standard material in Linear Programming is presented in the setting of real space as well as in the more abstract theory of oriented matroids. This approach clarifies the theory behind Linear Programming and proofs become simpler. The last part of the book deals with the facial structure of polytopes respectively their oriented matroid counterparts. It is an introduction to more advanced topics in oriented matroid theory. Each chapter contains suggestions for furt- herreading and the references provide an overview of the research in this field.

Introduction to the theory of matroids (Modern analytic and computational methods in science and mathematics)

Tutte — 2007-10-31T16:48:42-00:00

(23 July 1971)

2-Dimension from the Topological Viewpoint

Jonathan Barmak — 2007-10-23T08:12:30-00:00

Order, Vol. 24, No. 1. (17 February 2007), pp. 49-58.

Abstract In this paper we study the 2-dimension of a finite poset from the topological point of view. We use homotopy theory of finite topological spaces and the concept of a beat point to improve the classical results on 2-dimension, giving a more complete answer to the problem of all possible 2-dimensions of an n-point poset.

On the Complexity of Partial Order Properties

Stefan Felsner — 2007-10-23T03:27:23-00:00

Order, Vol. 17, No. 2. (1 June 2000), pp. 179-193.

The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n2 for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k = n2 / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.

Combinatorial representation and convex dimension of convex geometries

Paul Edelman — 2007-10-23T03:26:09-00:00

Order, Vol. 5, No. 1. (1 March 1988), pp. 23-32.

We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.

On algorithms for discrete and approximate brouwer fixed points

Xi Chen — 2006-06-02T19:22:07-00:00

(2005), pp. 323-330.

Poset Topology: Tools and Applications

Michelle Wachs — 2006-02-13T19:05:40-00:00

(11 Feb 2006)

These lecture notes for the IAS/Park City Graduate Summer School in Geometric Combinatorics (July 2004) provide an overview of poset topology. These notes include introductory material, as well as recent developments and open problems. Some of the topics covered are: subspace arrangements, graph complexes, group actions on poset homology, shellability, recursive techniques, and fiber theorems.

Unit disk graph recognition is NP-hard

Heinz Breu — 2006-02-28T17:06:18-00:00

Comput. Geom. Theory Appl., Vol. 9, No. 1-2. (1998), pp. 3-24.

Unit disk graphs

Brent Clark — 2007-10-03T09:45:38-00:00

Discrete Mathematics, Vol. 86, No. 1-3. (14 December 1990), pp. 165-177.

Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set, domination, independent domination, and connected domination; NP-completeness for the domination problem is shown to hold even for grid graphs, a subclass of unit disk graphs. In contrast, we give a polynomial time algorithm for finding cliques when the geometric representation (circles in the plane) is provided.

Geometry based heuristics for unit disk graphs

Madhav Marathe — 2007-10-03T08:42:31-00:00

(21 Sep 1994)

Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring and minimum dominating set. We also present an on-line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and to intersection graphs of higher dimensional regular objects.

Convexity in Discrete Space

Anthony Roy — 2007-08-31T04:30:37-00:00

Spatial Information Theory (2003), pp. 253-269.

This paper looks at Coppel’s axioms for convexity, and shows how they can be applied to discrete spaces. Two structures for a discrete geometry are considered: oriented matroids, and cell complexes. Oriented matroids are shown to have a structure which naturally satisfies the axioms for being a convex geometry. Cell complexes are shown to give rise to various different notions of convexity, one of which satisfies the convexity axioms, but the others also provide valid notions of convexity in particular contexts. Finally, algorithms are investigated to validate the sets of a matroid, and to compute the convex hull of a subset of an oriented matroid.

Matroid representation of clique complexes

Kenji Kashiwabara — 2007-08-19T17:00:58-00:00

Discrete Applied Mathematics, Vol. 155, No. 15. (15 September 2007), pp. 1910-1929.

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of "how complex a graph is with respect to the maximum weighted clique problem" since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.

Algebraic topology and concurrency

Lisbeth Fajstrup — 2007-08-09T15:58:27-00:00

Theoretical Computer Science, Vol. 357, No. 1-3. (25 July 2006), pp. 241-278.

We show in this article that some concepts from homotopy theory, in algebraic topology, are relevant for studying concurrent programs. We exhibit a natural semantics of semaphore programs, based on partially ordered topological spaces, which are studied up to "elastic deformation" or homotopy, giving information about important properties of the program, such as deadlocks, unreachables, serializability, essential schedules, etc. In fact, it is not quite ordinary homotopy that has to be used, but rather a "directed homotopy" that does not reverse the flow of time. We show some of the essential differences between ordinary and directed homotopy through examples. We also relate the topological view to a combinatorial view of concurrent programs closer to transition systems, through the notion of a cubical set. Finally we apply some of these concepts to the proof of the safeness of a two-phase protocol, well-known and used in concurrent database theory. We end up with a list of problems from both a mathematical and a computer-scientific point of view.

Geometric representation of graphs in low dimension

Sunil Chandran — 2007-08-01T06:21:27-00:00

(31 Jul 2007)

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (Δ + 2) \ln n$ dimensions, where $Δ$ is the maximum degree of G. We also show that $\boxi(G) ≤ (Δ + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $Δ$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c⋅(d_av + 1) \ln n$ where d_av is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) ≤ \sqrt8 n d_av \ln n$, which is tight up to a factor of $b \sqrt\ln n$ for a constant b.

Are network motifs the spandrels of cellular complexity?

Ricard Sole — 2006-08-05T01:50:33-00:00

Trends in Ecology & Evolution, Vol. 21, No. 8. (August 2006), pp. 419-422.

Cellular networks display modular organization at different levels, from small sets of genes exchanging signals in morphogenesis to large groups of proteins involved in cell death. At the smallest scale, minute groups of interacting proteins or genes, so-called 'network motifs', have been suggested to be the functional building blocks of network biology. In this context, the relative abundance of a network motif would reflect its adaptive value. However, although the overabundance of motifs is non-random, recent studies by Mazurie et al. and by Kuo et al. show that motif abundance does not reflect their true adaptive value. Just as some architectural components emerge as a byproduct of a prior decision, common motifs might be a side effect of inevitable rules of genome growth and change.

Small-World Networks and Functional Connectivity in Alzheimer's Disease

Cj Stam — 2006-12-18T17:56:29-00:00

Cerebral Cortex, Vol. 17, No. 1. (January 2007), pp. 92-99.

Research Problems in Discrete Geometry

P Brass — 2007-03-28T03:03:41-00:00

(2005)

Although Discrete Geometry has a rich history extending more than 150 years, it abounds in open problems that even a high-school student can understand and appreciate. Some of these problems are notoriously difficult and are intimately related to deep questions in other fields of mathematics. But many problems, even old ones, can be solved by a clever undergraduate or a high-school student equipped with an ingenious idea and the kinds of skills used in a mathematical olympiad. "Research Problems in Discrete Geometry" is the result of a twenty-five year old project initiated by the late Leo Moser. It is a collection of more than 500 attractive open problems in the field, many of which can be understood without extensive preparation. The largely self-contained chapters provide a broad overview of discrete geometry, along with historical details and the most important partial results related to these problems. This book is intended as a source book for both professional mathematicians and graduate students who love beautiful mathematical questions, are willing to spend sleepless nights thinking about them, and who would like to get involved in mathematical research. Important features include: * More than 500 open problems, some old, others new and never before published; * Each chapter divided into self-contained sections, each section ending with an extensive bibliography; * A great selection of research problems for graduate students looking for a dissertation topic; * A comprehensive survey of Discrete Geometry, highlighting the frontiers and future of research; * More than 150 figures; * A Preface to an earlier version written by the late Paul Erdos.

On the Development of the Intersection of a Plane with a Polytope

Joseph O'Rourke — 2007-03-27T11:07:07-00:00

(3 Aug 2006)

Define a “slice” curve as the intersection of a plane with the surface of a polytope, i.e., a convex polyhedron in three dimensions. We prove that a slice curve develops on a plane without self-intersection. The key tool used is a generalization of Cauchy's arm lemma to permit nonconvex “openings” of a planar convex chain.

Combinatorics of branching in higher dimensional automata

P Gaucher — 2006-09-22T08:45:01-00:00

(1999)

We explore the combinatorial properties of the branching areas of execution paths in higher dimensional automata. Mathematically, this means that we investigate the combinatorics of the negative corner (or branching) homology of a globular #-category and the combinatorics of a new homology theory called the reduced branching homology. The latter is the homology of the quotient of the branching complex by the sub-complex generated by its thin elements. Conjecturally it coincides with the non...

A homology theory for spanning trees of a graph

L Lovász — 2006-07-22T18:33:14-00:00

Acta Math. Acad. Sci. Hungar., Vol. 30, No. 3-4. (1977), pp. 241-251.

The author constructs a cellular complex $K(G,a)=K$, called the arborescence complex of a digraph $G$ (relative to vertex $a$); in fact, $K$ is simply connected (Theorem 5). By calculation, the author demonstrates (Theorem 4) that the reduced homology groups $H_r(K)$ of the arborescence complex of $G$ are zero, for $0≤ r≤ k-2$, whenever $G$ is a digraph containing a vertex $a$ such that no point can be separated from $a$ by less than $k$ points $(k≥ 2)$. Lastly, using Theorem 4, both the undirected and directed versions of a conjecture of A. Frank ("Combinatorial algorithms, algorithmic proofs", Dissertation, Budapest, 1975) follow. Theorem: Given a $k$-connected graph $G$, $k$ points $v_1,⋅s,v_k∈ V(G)$, and $k$ positive integers whose sum $n_1+n_2+⋅s+n_k=|V(G)|$, there exists a partition ${V_1,⋅s,V_k}$ of $V(G)$ such that $v_i∈ V_i$, $|V_i|=n_k$ and $V_i$ spans a connected subgraph.