On an isomorphism problem on the closed-set lattice of a graph

Let (G) and V(G) be, respectively, the closed-set lattice and the vertex set of a graph G. Any lattice isomorphism : V(G)(G) induces a bijection : V(G)V(G) such that for each x in V(G), (x)=x' in V(G') iff ({x})={x'}. A graph G is strongly sensitive if for any graph G' and any lattice isomorphism : (G)(G), the bijection induced by is a graph isomorphism of G onto G'. In this paper we present some sufficient conditions for graphs to be strongly sensitive and prove in particular that all C ₄-free graphs and all covering graphs of finite lattices are strongly sensitive.     

Hook-free colorings and a problem of Hanson

Hanson posed the following problem: What is the minimum numberχ(n) of colors needed to color all subsets of ann-set such that there is no monochromatic tripleA, B, C withA ∪B=C? It is known thatχ(n)≦[(n+1)/2], while Erd?s and Shelah provedχ(n)≧[(n+1)/4]. Their proof suggests the following notion: LetC be any finite plane point-configuration. The hook-free coloring numberχ(C) is the smallest number of colors needed forC such that no monochromatic hooks arise, i.e. if (c _x ,c _y ) are the coordinates of pointc∈C, then there are no 3 distinct pointsa, b, c∈C witha _x =b _x <c _x ,b _y =c _y <a _y . In this paperχ(R _m,n ) is determined exactly for anm×n-rectangle, and asymptotically for the triangular staircase. As a corollary one obtainsχ(n)≧0.293n.     

Ann-dimensional search problem with restricted questions

The problem is the following: How many questions are necessary in the worst case to determine whether a pointX in then-dimensional Euclidean spaceR ⁿ belongs to then-dimensional unit cubeQ ⁿ, where we are allowed to ask which halfspaces of (n−1)-dimensional hyperplanes contain the pointX? It is known that ⌌3n/2⌍ questions are sufficient. We prove here thatcn questions are necessary, wherec≈1.2938 is the solution of the equationx log₂ x−(x−1) log₂ (x−1)=1.     

On the number of vertices and edges of the Buneman graph

In 1971, Peter Buneman proposed a way to construct a tree from a collection of pairwise compatible splits. This construction immediately generalizes to arbitrary collections of splits, and yields a connected median graph, called the Buneman graph. In this paper, we prove that the vertices and the edges of this graph can be described in a very simple way: given a collection of splitsS, the vertices of the Buneman graph correspond precisely to the subsetsS′ ofS such that the splits inS′ are pairwise incompatible and the edges correspond to pairs (S′, S) withS′ as above andS∈S′. Using this characterization, it is much more straightforward to construct the vertices of the Buneman graph than using prior constructions. We also recover as an immediate consequence of this enumeration that the Buneman graph is a tree, that is, that the number of vertices exceeds the number of edges (by one), if and only if any two distinct splits inS are compatible.     

The zero-divisor graph of a reduced ring

In this paper the zero-divisor graph Γ(R) of a commutative reduced ring R is studied. We associate the ring properties of R, the graph properties of Γ(R) and the topological properties of . Cycles in Γ(R) are investigated and an algebraic and a topological characterization is given for the graph Γ(R) to be triangulated or hypertriangulated. We show that the clique number of Γ(R), the cellularity of and the Goldie dimension of R coincide. We prove that when R has the annihilator condition and ; Γ(R) is complemented if and only if is compact. In a semiprimitive Gelfand ring, it turns out that the dominating number of Γ(R) is between the density and the weight of . We show that Γ(R) is not triangulated and the set of centers of Γ(R) is a dominating set if and only if the set of isolated points of is dense in .     

On the singular graph and the Weyr characteristic of anM-matrix

LetA be anM-matrix in standard lower block triangular form, with diagonal blocksA _ii irreducible. LetS be the set of indices such that the diagonal blockA is singular. We define the singular graph ofA to be the setS with partial order defined by > if there exists a chain of non-zero blocksA _i, A_ij, , A_l.Let ₁ be the set of maximal elements ofS, and define thep-th level _p ,p = 2, 3, , inductively as the set of maximal elements ofS \( _{1 p-1}). Denote by _p the number of elements in _p . The Weyr characteristic (associated with 0) ofA is defined to be (A) = ( ₁, ₂,, _h ), where ₁ + + _p = dim KerA ^p ,p = 1, 2, , and _h > 0, _h+1 = 0.Using a special type of basis, called anS-basis, for the generalized eigenspaceE(A) of 0 ofA, we associate a matrixD withA. We show that(A) = ( ₁, , _h) if and only if certain submatricesD _p,p+1 ,p = 1, , h – 1, ofD have full column rank. This condition is also necessary and sufficient forE(A) to have a basis consisting of non-negative vectors, which is a Jordan basis for –A. We also consider a given finite partially ordered setS, and we find a necessary and sufficient condition that allM-matricesA with singular graphS have(A) = ( ₁, , _h). This condition is satisfied ifS is a rooted forest.The work of the second-named author was partly supported by the National Science Foundation, under grant MPS-08618 A02.     

Neighborhood Complexes of Stable Kneser Graphs

It is shown that the neighborhood complexes of a family of vertex critical subgraphs of Kneser graphs—the stable Kneser graphs introduced by L. Schrijver—are spheres up to homotopy. Furthermore, it is shown that the neighborhood complexes of a subclass of the stable Kneser graphs contain the boundaries of associahedra (simplicial complexes encoding triangulations of a polygon) as a strong deformation retract.* The first author was partially supported by the G&ouml;ran Gustafsson Foundation for Research in Natural Sciences and Medicine. The second author was supported by the graduate school Algorithmische Diskrete Mathematik, which is funded by the Deutsche Forschungsgemeinschaft, grant GRK 219/3. The DAAD partially supported a stay at KTH, Stockholm, in December 1998, where this work was done: DAAD program AZ 313/S-PPP     

On the diameter and girth of a zero-divisor graph

For a commutative ring R with zero-divisors Z(R), the zero-divisor graph of R is Γ(R)=Z(R)−{0}, with distinct vertices x and y adjacent if and only if xy=0. In this paper, we characterize when either or . We then use these results to investigate the diameter and girth for the zero-divisor graphs of polynomial rings, power series rings, and idealizations.     

On a class of isometric subgraphs of a graph

In a graphG, which has a loop at every vertex, a connected subgraphH=(V(H),E(H)) is a retract if, for anya, b ∈V(H) and for any pathsP, Q inG, both joininga tob, and satisfying |Q|≧ ≧|P|, thenP ⫅V(H) wheneverQ ⫅V(H). As such subgraphs can be described by a closure operator we are led to the investigation of the corresponding complete lattice of “closed” subgraphs. For example, in this complete lattice every element is the infimum of an irredundant family of infimum irreducible elements. The work presented here was supported in part by N.S.E.R.C. Operating Grant No. A4077.     

Harmonic functions on Walsh’s Brownian motion

We examine a variation of two-dimensional Brownian motion introduced by Walsh that can be described as Brownian motion on the spokes of a (rimless) bicycle wheel. We construct the process by randomly assigning angles to excursions of reflecting Brownian motion. Hence, Walsh’s Brownian motion behaves like one-dimensional Brownian motion away from the origin, but differently at the origin as it is immediately sent off in random directions. Given the similarity, we characterize harmonic functions as linear functions on the rays satisfying a slope-averaging property. We also classify superharmonic functions as concave functions on the rays satisfying extra conditions.     

Harmonic functions on nilpotent groups

For a probability measure on a locally compact groupG which is not supported on any proper closed subgroup, an elementF ofL (G) is called -harmonic if F(st)d(t)=F(s), for almost alls inG. Constant functions are -harmonic and it is known that for abelianG all -harmonic functions are constant. For other groups it is known that non constant -harmonic functions exist and the question of whether such functions exist on nilpotent groups is open, though a number of partial results are known. We show that for nilpotent groups of class 2 there are no non constant -harmonic functions. Our methods also enable us to give new proofs of results similar to the known partial results.     

Cones of alternating and cut submodular set functions

We describe facets of the cones of alternating set functions and cut submodular set functions generated by directed and undirected graphs and by uniform even hypergraphs. This answers a question asked by L. Lovász at the Bonn Mathematical Programming Conference in 1982. We show that there is a network flow algorithm for minimizing a hypergraph cut set function.     

Representing an ordered set as the intersection of super greedy linear extensions

A linear extension [x ₁2<...t] of a finite ordered set P=(P, <) is super greedy if it can be obtained using the following procedure: Choose x ₁ to be a minimal element of P; suppose x ₁,...,x _i have been chosen; define p(x) to be the largest ji such that x _jj exists and 0 otherwise; choose x _i+1 to be a minimal element of P-{ x ₁,...,x _i} which maximizes p. Every finite ordered set P can be represented as the intersection of a family of super greedy linear extensions, called a super greedy realizer of P. The super greedy dimension of P is the minimum cardinality of a super greedy realizer of P. Best possible upper bounds for the super greedy dimension of P are derived in terms of |P-A| and width (P-A), where A is a maximal antichain.Research supported in part by NSF grant IPS-80110451.Research supported in part by ONR grant N00014-85K-0494 and NSERC grants 69-3378, 69-0259, and 69-1325.Research supported in part by NSF grant DMS-8401281.     

Some intersection theorems on two-valued functions

Let be a family of two-valued functions defined on ann-element set in which each pair of functions in satisfy a given intersection condition. For certain intersection conditions we determine the maximal value of .     

Convex functions on Grassmannian manifolds and Lawson-Osserman problem

We derive estimates of the Hessian of two smooth functions defined on Grassmannian manifold. Based on it, we can derive curvature estimates for minimal submanifolds in Euclidean space via Gauss map as in [Y.L. Xin, Ling Yang, Curvature estimates for minimal submanifolds of higher codimension, arXiv: 0709.3686; 24]. In this way, the result for Bernstein type theorem done by Jost and the first author could be improved.     

Bounding Betti numbers of bipartite graph ideals

We prove a conjectured lower bound of Nagel and Reiner on Betti numbers of edge ideals of bipartite graphs.     

On functions behaving like additive functions

Let 0 < 1. In the paper we consider the following inequality: |f(x + y) – f(x) – f(y)| min{|f(x + y)|, |f(x) + f(y)|}, wheref: R R. Solutions and continuous solutions of this inequality are investigated. They have similar properties as additive functions, e.g. if the solution is bounded above (below) on a set of positive inner Lebesgue measure then it is continuous. Some sufficient condition for this inequality is also given.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday     

Extended Keller graph and its properties

Abstract

In the paper extended Keller graph is defined and some of its properties, such as Hamiltonian, the independence number, the chromatic number, etc., are proved. Moreover, the size of a maximum clique of for d = 2, 3, 4 and d ≥ 8 is given and for d = 5, 6, 7 a conjecture is stated.