Richmond and Richmond (1997) proved the following theorem: If, in a metric space with at least five points, all triangles are degenerate, then the space is isometric to a subset of the real line. We prove that the hypothesis is unnecessarily strong: In a metric space on n points, fewer than 7n2/6 suitably placed degenerate triangles suffice. However, fewer than n(n−1)/2 degenerate triangles, no matter how cleverly placed, never suffice.

In a pioneering classic, Warren McCulloch and Walter Pitts proposed a model of the central nervous system. Motivated by EEG recordings of normal brain activity, Chvátal and Goldsmith asked whether these dynamical systems can be engineered to produce trajectories that are irregular, disorderly, and apparently unpredictable. We show that they cannot build weak pseudorandom functions.

A graph G is called a Berge graph if neither G nor its complement contains a chordless cycle whose length is odd and at least five; what we call a dart is the graph with vertices u,v,w,x,y and edges uv,vw,uy,vy,wy,xy; a graph is called dart-free if it has no induced subgraph isomorphic to the dart. We present a polynomial-time algorithm to recognize dart-free Berge graphs; this algorithm uses as a subroutine the polynomial-time algorithm for recognizing claw-free Berge graphs designed previously by Chvátal and Sbihi [J. Combin. Theory Ser. B, 44 (1988), pp. 154--176].

Consider a randomly generated boolean formula F (in the conjunctive normal form) with m clauses of size k over n variables; k is fixed at any value greater than 1, but n tends to infinity and m = (1 + o(1))cn for some c depending only on k. It is easy to see that F is unsatisfiable with probability 1-o(1) whenever c>(ln 2)2/sup k/; the authors complement this observation by proving that F is satisfiable with probability 1-o(1) whenever c1.>

For every choice of positive integers c and k such that k ≥ 3 and c 2 - k ≥ 0.7, there is a positive number ε such that, with probability tending to 1 as n tends to ∞, a randomly chosen family of cn clauses of size k over n variables is unsatisfiable, but every resolution proof of its unsatisfiability must generate at least (1 + ε) n clauses.

We formalize certain rules for deriving upper bounds on the stability number of a graph. The resulting system is powerful enough to (i) encompass the algorithms of Tarjan’s type and (ii) provide very short proofs on graphs for which the stability number equals the clique-covering number. However, our main result shows that for almost all graphs with a (sufficiently large) linear number of edges, proofs within our system must have at least exponential length.