Matroid representation of clique complexes

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.     

Coalescent random walks on graphs

Inspired by coalescent theory in biology, we introduce a stochastic model called “multi-person simple random walks” or “coalescent random walks” on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.     

The complete optimal stars-clustering-tree problem

We consider the following complete optimal stars-clustering-tree problem: Given a complete graph G=(V,E) with a weight on every edge and a collection of subsets of V, we want to find a minimum weight spanning tree T such that each subset of the vertices in the collection induces a complete star in T. One motivation for this problem is to construct a minimum cost (weight) communication tree network for a collection of (not necessarily disjoint) groups of customers such that each group induces a complete star. As a result the network will provide a “group broadcast” property, “group fault tolerance” and “group privacy”. We present another motivation from database systems with replications. For the case where the intersection graph of the subsets is connected we present a structure theorem that describes all feasible solutions. Based on it we provide a polynomial algorithm for finding an optimal solution. For the case where each subset induces a complete star minus at most k leaves we prove that the problem is NP-hard.     

A geometric view on learning Bayesian network structures

We recall the basic idea of an algebraic approach to learning Bayesian network (BN) structures, namely to represent every BN structure by a certain (uniquely determined) vector, called a standard imset. The main result of the paper is that the set of standard imsets is the set of vertices (=extreme points) of a certain polytope. Motivated by the geometric view, we introduce the concept of the geometric neighborhood for standard imsets, and, consequently, for BN structures. Then we show that it always includes the inclusion neighborhood, which was introduced earlier in connection with the greedy equivalence search (GES) algorithm. The third result is that the global optimum of an affine function over the polytope coincides with the local optimum relative to the geometric neighborhood.To illustrate the new concept by an example, we describe the geometric neighborhood in the case of three variables and show it differs from the inclusion neighborhood. This leads to a simple example of the failure of the GES algorithm if data are not “generated” from a perfectly Markovian distribution. The point is that one can avoid this failure if the search technique is based on the geometric neighborhood instead. We also found out what is the geometric neighborhood in the case of four and five variables.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Countable connected Hausdorff and Urysohn bunches of arcs in the plane

In this paper, we answer a question by Krasinkiewicz, Reńska and Sobolewski by constructing countable connected Hausdorff and Urysohn spaces as quotient spaces of bunches of arcs in the plane. We also consider a generalization of graphs by allowing vertices to be continua and replacing edges by not necessarily connected sets. We require only that two “vertices” be in the same quasi-component of the “edge” that contains them. We observe that if a graph G cannot be embedded in the plane, then any generalized graph modeled on G is not embeddable in the plane. As a corollary we obtain not planar bunches of arcs with their natural quotients Hausdorff or Urysohn. This answers another question by Krasinkiewicz, Reńska and Sobolewski.     

Every finite graph is a full subgraph of a rigid graph

We prove that every finite undirected graph is a full subgraph of a rigid graph. Our construction proceeds on taking a family of “mutually rigid” graphs and attaching them to the vertices of a given graph in a one-to-one manner; then the vertices are fixed on their place. Actually, the new graph is “strongly rigid”, which enables us to show that the category of all graphs containing a given finite graph as a full subgraph is binding.     

Embedding processes in combinatorial game theory

Berlekamp asked the question “What is the habitat of ∗2?” (See Guy, 1996 [6].) It is possible to generalize the question and ask “For a game G, what is the largest n such that ∗n is a position of G?” This leads to the concept of the nim dimension. In Santos and Silva (2008) [8] a fractal process was proposed for analyzing the previous questions. For the same purpose, in Santos and Silva (2008) [9], an algebraic process was proposed. In this paper we implement a third idea related to embedding processes. With Alan Parr’s traffic lights, we exemplify the idea of estimating the “difficulty” of the game and proving that its nim dimension is infinite.     

Portfolio optimization when asset returns have the Gaussian mixture distribution

In this paper we consider a portfolio optimization problem where the underlying asset returns are distributed as a mixture of two multivariate Gaussians; these two Gaussians may be associated with “distressed” and “tranquil” market regimes. In this context, the Sharpe ratio needs to be replaced by other non-linear objective functions which, in the case of many underlying assets, lead to optimization problems which cannot be easily solved with standard techniques. We obtain a geometric characterization of efficient portfolios, which reduces the complexity of the portfolio optimization problem.     

On the extremal Merrifield-Simmons index and Hosoya index of quasi-tree graphs

It is well known that the two graph invariants, “the Merrifield-Simmons index” and “the Hosoya index” are important in structural chemistry. A graph G is called a quasi-tree graph, if there exists u₀ in V(G) such that G−u₀ is a tree. In this paper, at first we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest Merrifield-Simmons indices. Then we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest Hosoya indices, as well as those n-vertex quasi-tree graphs with k pendent vertices having the smallest Hosoya index.     

Markov decision processes with exponentially representable discounting

We generalize the geometric discount of finite discounted cost Markov Decision Processes to “exponentially representable”discount functions, prove existence of optimal policies which are stationary from some time N onward, and provide an algorithm for their computation. Outside this class, optimal “N-stationary” policies in general do not exist.     

Using the K5Connected Cognition Diagram to analyze teachers’ communication and understanding of regions in three-dimensional space

This paper reports on a study that introduces and applies the K₅Connected Cognition Diagram as a lens to explore video data showing teachers’ interactions related to the partitioning of regions by axes in a three-dimensional geometric space. The study considers “semiotic bundles” ( Arzarello, 2006), introduces “semiotic connections,” and discusses the fundamental role each plays in developing individual understanding and communication with peers. While all teachers solved the problem posed, many failed to make or verbalize connections between the types of semiotic resources introduced during their discussions.     

Chiral differential operators: Formal loop group actions and associated modules

Chiral differential operators (CDOs) are closely related to string geometry and the quantum theory of 2-dimensional σ-models. This paper investigates two topics about CDOs on smooth manifolds. In the first half, we study how a Lie group action on a smooth manifold can be lifted to a “formal loop group action” on an algebra of CDOs; this turns out to be a condition on the equivariant first Pontrjagin class. The case of a principal bundle receives particular attention and gives rise to a type of vertex algebras of great interest. In the second half, we introduce a construction of modules over CDOs using the said “formal loop group actions” and semi-infinite cohomology. Intuitively, these modules should have a geometric meaning in terms of “formal loop spaces”. The first example we study leads to a new conceptual construction of an arbitrary algebra of CDOs. The other example, called the spinor module, may be useful for a geometric theory of the Witten genus.     

Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].     

Vertex-weightings for distance moments and thorny graphs

Valence-weightings are considered for shortest-path distance moments, as well as related weightings for the so-called “Wiener” polynomial. In the case of trees the valence-weighted quantities are found to be expressible as a combination of unweighted quantities. Further the weighted quantities for a so-called “thorny” graph are considered and shown to be related to the weighted and unweighted quantities for the underlying parent graph.     

On a graph’s security number

A secure set S⊆V of graph G=(V,E) is a set whose every nonempty subset can be successfully defended from an attack, under appropriate definitions of “attack” and “defended.” The set S is secure when |N[X]∩S|≥|N[X]−S| for every X⊆S. The smallest cardinality of a secure set in G is the security number of G. New bounds for the security number are established, the effect of some graph modifications on the security number is investigated, and the exact value of the security number for some families of graphs is given.     

A bivariate optimal replacement policy for a cold standby repairable system with preventive repair

In this paper, the repair-replacement problem for a deteriorating cold standby repairable system is investigated. The system consists of two dissimilar components, in which component 1 is the main component with use priority and component 2 is a supplementary component. In order to extend the working time and economize the running cost of the system, preventive repair for component 1 is performed every time interval T, and the preventive repair is “as good as new”. As a supplementary component, component 2 is only used at the time that component 1 is under preventive repair or failure repair. Assumed that the failure repair of component 1 follows geometric process repair while the repair of component 2 is “as good as new”. A bivariate repair-replacement policy (T, N) is adopted for the system, where T is the interval length between preventive repairs, and N is the number of failures of component 1. The aim is to determine an optimal bivariate policy (T, N)^∗ such that the average cost rate of the system is minimized. The explicit expression of the average cost rate is derived and the corresponding optimal bivariate policy can be determined analytically or numerically. Finally, a Gamma distributed example is given to illustrate the theoretical results for the proposed model.     

Tau-functions,Grassmannians and rank one conditions

In integrable systems, specifically the KP hierarchy, there are functions known as “tau-functions”, closely related to the Schur polynomials in terms of which they are often written. Although they are generally viewed as the solutions to a collection of nonlinear PDEs, in this note they will equivalently be characterized by a quadratic difference equation. Sato's theorem associates tau-functions to the points of a Grassmann manifold. To make that amazing theorem clear to non-experts, we will first show an analogous (but easily understood) example of a linear ODE and its solution from a flow on the xy-plane. In each case the solution is created via a flow generated by a certain linear operator. The question we pose is this: “What other operators could have been used to generate solutions in the same way?” Although the answer is well known in the ODE case, the question in the nonlinear case is the main result of our new paper. We will state the result and discuss its relationship to the “trend” of writing tau-functions in terms of matrices satisfying certain rank one conditions. The elucidation of a geometric interpretation of the Hirota bilinear difference equation (HBDE) is a key feature of the proof and will be briefly described.     

On nilpotent ideals in the cohomology ring of a finite group

In this paper we find upper bounds for the nilpotency degree of some ideals in the cohomology ring of a finite group by studying fixed point free actions of the group on suitable spaces. The ideals we study are the kernels of restriction maps to certain collections of proper subgroups. We recover the Quillen-Venkov lemma and the Quillen F-injectivity theorem as corollaries, and discuss some generalizations and further applications.We then consider the essential cohomology conjecture, and show that it is related to group actions on connected graphs. We discuss an obstruction for constructing a fixed point free action of a group on a connected graph with zero “k-invariant” and study the class related to this obstruction. It turns out that this class is a “universal essential class” for the group and controls many questions about the groups essential cohomology and transfers from proper subgroups.     

Detecting an induced net subdivision

A net is a graph consisting of a triangle C and three more vertices, each of degree one and with its neighbour in C, and all adjacent to different vertices of C. We give a polynomial-time algorithm to test whether an input graph has an induced subgraph which is a subdivision of a net. Unlike many similar questions, this does not seem to be solvable by an application of the “three-in-a-tree” subroutine.