A note on maximal triangle-free graphs

We show that a maximal triangle-free graph on n vertices with minimum degree δ contains an independent set of 3δ ? n vertices which have identical neighborhoods. This yields a simple proof that if the binding number of a graph is at least 3/2 then it has a triangle. This was conjectured originally by Woodall. © 1993 John Wiley & Sons, Inc.     

A characterization of triangle-free tolerance graphs

We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).     

A skew-product which is Bernoulli

We show that if is the shift on sequences of {0,1} and is the entropy zero transformation used by Ornstein in constructing a counter-example toPinsker's conjecture, then the skew-product transformationT defined byT(x,y)=(x, ^x0 y) is Bernoulli. ThisT is conditionally mixing with respect to the independent generator for , a partition with full entropy.This research was done while the first author was a visitor at Stanford, supported in part by NSF Grant MP-575-08324.     

A technique for multicoloring triangle-free hexagonal graphs

In order to avoid interference in cellular telephone networks, sets of radio frequencies are to be assigned to transmitters such that adjacent transmitters are allotted disjoint sets of frequencies. Often these transmitters are laid out like vertices of a triangular lattice in a plane. This problem corresponds to the problem of multicoloring an induced subgraph of a triangular lattice with integer demands associated with each vertex. We deal with the simpler case of triangle-free subgraphs of the lattice. [Frédéric Havet, Discrete Math. 233 (2001) 1–3] uses inductive arguments to prove that triangle-free hexagonal graphs can be colored with colors where ω_d is the maximum demand on a clique in the graph. We give a simpler proof and hope that our techniques can be used to prove the conjecture by [McDiarmid and Reed, Networks Suppl. 36 (2000) 114–117] that these graphs are -multicolorable.     

A note on bipartite subgraphs of triangle-free graphs

Let G be a triangle-free graph on n points with m edges and vertex degrees d₁, d₂,…, d_n. Let k be the maximum number of edges in a bipartite subgraph of G. In this note we show that k ? m/2 + Σ √d_i. It follows as a corollary that k ? m/2 + cm^3/4.     

A cohesive set which is not high

We study the degrees of unsolvability of sets which are cohesive (or have weaker recursion-theoretic “smallness” properties). We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets in place of r-cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1-generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly. MSC: 03D30, 03D55.     

A copositive Q-matrix which is notR 0

Jeter and Pye gave an example to show that Pang's conjecture, thatL ₁ ?Q ?R ₀, is false while Seetharama Gowda showed that the conjecture is true for symmetric matrices. It is known thatL ₁-symmetric matrices are copositive matrices. Jeter and Pye as well as Seetharama Gowda raised the following question: Is it trueC ₀ ?Q ?R ₀? In this note we present an example of a copositive Q-matrix which is notR ₀. The example is based on the following elementary proposition: LetA be a square matrix of ordern. SupposeR ₁ =R ₂ whereR _i stands for theith row ofA. Further supposeA ₁₁ andA ₂₂ are Q-matrices whereA _ii stands for the principal submatrix omitting theith row andith column fromA. ThenA is a Q-matrix.     

A note on the matching numbers of triangle-free graphs

For the sake of brevity the absolute values of the coefficients of the matching polynomial of a graph are called matching numbers in this note. It is shown that for a triangle-free graph these numbers coincide with the coefficients of the chromatic polynomial of its complement when this polynomial is written in factorial form. As an application it is mentioned that the coefficients of every rook polynomial are at the same time coefficients of some chromatic polynomial.     

A note on bipartite subgraphs of triangle-free regular graphs

Lower bounds on the size of a maximum bipartite subgraph of a triangle-free r-regular graph are presented.     

Characterization of tomographic reconstructions which commute with rigid motions

This note considers linear reconstruction operators for parallel beam tomography when the number of radiographs is finite. It is shown that if such reconstructions are continuous and commute with rigid motions in an appropriate sense, then they must be representable as convolution operators with a polynomial kernel whose degree depends on the number of radiographs.     

A note on the independence number of triangle-free graphs

Let G be a triangle-free graph on n points with average degree d. Let α be the independence number of G. In this note we give a simple proof that α ? n (d ln d ? d + 1)/(d ? 1)². We also consider what happens when G contains a limited number of triangles.     

A non-Bernoulli skew product which is loosely Bernoulli

LetT: Y→Y be the Bernoulli two shift with independent generatorQ={Q ₀,Q ₁} and letS: X→X be a measure preserving bijection. If (S, X) is ergodic then the skew product onX×Y defined by {fx339-1} is aK-automorphism. IfŜ is also Bernoulli we sayS is pre-Bernoulli. J. Feldman showed that ifS is pre-Bernoulli thenS must be loosely Bernoulli. We construct an example to show the converse is false, i.e. anS that is loosely Bernoulli but not pre-Bernoulli.     

A weakly definable type which is not definable

Summary For each completion of Peano Arithmetic there is a weakly definable type which is not definable.     

A countably categorical theory which is not G-compact

We give an example of a countably categorical theory which is not G-compact. The countable model of this theory does not have AZ-enumerations.     

A compact group which is not Valdivia compact

A compact space is Valdivia compact if it can be embedded in a Tikhonov cube in such a way that the intersection is dense in , where is the sigma-product ( the set of points with countably many non-zero coordinates). We show that there exists a compact connected Abelian group of weight which is not Valdivia compact, and deduce that Valdivia compact spaces are not preserved by open maps.

     

Structure and stability of triangle-free set systems

We define the notion of stability for a monotone property of set systems. This phenomenon encompasses some classical results in combinatorics, foremost among them the Erdos-Simonovits stability theorem. A triangle is a family of three sets such that , , are each nonempty, and . We prove the following new theorem about the stability of triangle-free set systems.

Fix . For every , there exist and such that the following holds for all : if and is a triangle-free family of -sets of containing at least members, then there exists an -set which contains fewer than members of .

This is one of the first stability theorems for a nontrivial problem in extremal set theory. Indeed, the corresponding extremal result, that for every triangle-free family of -sets of has size at most , was a longstanding conjecture of Erdos (open since 1971) that was only recently settled by Mubayi and Verstraëte (2005) for all .

     

A relation algebra which is not a cylindric reduct

There is an incomplete atomic relation algebra which is not the reduct of any 4-dimensional cylindric algebra. This completes the answer to a problem in [Mo61].Presented by Bjarni Jónsson.     

A Pseudocompact Completely Regular Frame which is not Spatial

Compact regular frames are always spatial. In this note we present a method for constructing non-spatial frames. As an application we show that there is a countably compact (and hence pseudocompact) completely regular frame which is not spatial.