Every self-dual ordering has a self-dual linear extension

In this note, it is showed that every self-dual ordering has a self-dual linear extension.     

Every planar graph has an acyclic 7-coloring

A proper coloring of the vertices of a graph is said to be acyclic provided that no cycle is two colored. We prove that every planar graph has an acyclic seven coloring. Research supported in part by the Research Corporation through a Cottrell College Science Research Grant.     

Every monotone graph property has a sharp threshold

In their seminal work which initiated random graph theory Erdös and Rényi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This follows from the following theorem. Let denote the Hamming space endowed with the probability measure defined by , where . Let be a monotone subset of . We say that is symmetric if there is a transitive permutation group on such that is invariant under . Theorem. For every symmetric monotone , if then for . ( is an absolute constant.)

     

The poset on connected induced subgraphs of a graph need not be Sperner

SupposeG is a finite connected graph. LetC(G) denote the inclusion ordering on the connected vertex-induced subgraphs ofG. Penrice asked whetherC(G) is Sperner for general graphsG. Answering Penrice's question in the negative, we present a treeT such thatC(T) is not Sperner. We also construct a related distributive lattice that is not Sperner.     

A chain complete poset with no infinite antichain has a finite core

It is well known that dismantling a finite posetP leads to a retract, called the core ofP, which has the fixed-point property if and only ifP itself has this property. The PT-order, or passing through order, of a posetP is the quasi order defined onP so thatab holds if and only if every maximal chain ofP which passes througha also passes throughb. This leads to a generalization of the dismantling procedure which works for arbitrary chain complete posets which have no infinite antichain. We prove that such a poset also has a finite core, i.e. a finite retract which reflects the fixed-point property forP.This research was written while the first author was visiting the University of Calgary.Research supported by NSERC grant #69-0982.     

Every rayless graph has an unfriendly partition

We prove that every rayless graph has an unfriendly partition.     

Every rayless graph has an unfriendly partition

It is proved that every graph containing no infinite path has an unfriendly partition.     

Every planar graph with the Liouville property is amenable

We introduce a strengthening of the notion of transience for planar maps in order to relax the standard condition of bounded degree appearing in various results, in particular, the existence of Dirichlet harmonic function s proved by Benjamini and Schramm. As a corollary we obtain that every planar nonamenable graph admits nonconstant Dirichlet harmonic function s27.     

Every galois connection is the polarity of an antitone relation

En route to the result in the title (which completes a number of partial sorties made in this direction) there is established the extendability of arbitrary monotone functions to residuated or polar maps between suitable join-extensions.     

Every connected graph is a query graph

Let V be a set of bit strings of length k, i.e., V ? {0, 1}^k. The query graph Q(V) is defined as follows: the vertices of Q(V) are the elements of V, and {ū, v?} is an edge of Q(V) if and only if no other w? ? V agrees with ū in all the positions in which v? does. If V represents the set of keys for a statistical data base in which queries that match only one key are rejected, then the security of the individual data is related to the graph Q(V). Ernst Leiss showed that graphs belonging to any of several classes could be represented as query graphs and asked whether any connected graph could be so represented. We answer his question in the affirmative by making use of a spanning tree with special properties.     

The minimum semidefinite rank of a triangle-free graph

We employ a result of Moshe Rosenfeld to show that the minimum semidefinite rank of a triangle-free graph with no isolated vertex must be at least half the number of its vertices. We define a Rosenfeld graph to be such a graph that achieves equality in this bound, and we explore the structure of these special graphs. Their structure turns out to be intimately connected with the zero-nonzero patterns of the unitary matrices. Finally, we suggest an exploration of the connection between the girth of a graph and its minimum semidefinite rank, and provide a conjecture in this direction.     

A relation between the comparability graph and the number of linear extensions

In this note, we prove that the comparability graph of a posetP has less edges than that of a posetQ on the same set of elements, thenP has more linear extensions thanQ. This solves a problem posed by Kelly [1].Research partially supported by the grant RP.I.09 from the Institute of Informatics, University of Warsaw.     

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.     

Some geometrical aspects of a maximal three-coloured triangle-free graph

A three-coloured triangle-free complete graph with 16 vertices is constructed in an ad hoc manner. The edges of one colour in the complete graph, with the 16 vertices, form a Greenwood-Gleason graph, which can be regarded as the edges and diagonals of a hypercube in four dimensions, and which also has a representation as a graph in five dimensions all of whose automorphisms are isometries. In the complete graph, the blue edges form 40 quadrilaterals; 20 of these have red diagonals, and these 20 “red quadrilaterals,” meeting along 40 edges and at 16 vertices, represent a topological surface of characteristic ?4, a Klein bottle with two handles. This surface can be represented using a tessellation of regular quadrilaterals in the hyperbolic plane. To obtain the only other three-coloured triangle-free complete graph with 16 vertices some of the blue and red edges are interchanged in a way that can be described very simply using either the surface of characteristic ?4 or the hyperbolic tessellation.     

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.     

Every poset has a central element

It is proved that there exists a constant , such that in every finite partially ordered set there is an element such that the fraction of order ideals containing that element is between δ and 1−δ. It is shown that δ can be taken to be at least (3−log₂ 5)/40.17. This settles a question asked independently by Colburn and Rival, and Rosenthal. The result implies that the information-theoretic lower bound for a certain class of search problems on partially ordered sets is tight up to a multiplicative constant.     

Weak orders admitting a perpendicular linear order

Two orders on the same set are perpendicular if the constant maps and the identity map are the only maps preserving both orders. We characterize the finite weak orders admitting a perpendicular linear order.