Simple, Reducible Venn Diagrams on Five Curves and Hamiltonian Cycles

Recently, using graph theory, we developed procedures for the construction of Venn diagrams. Utilizing these procedures with some new methods introduced here, we determine the number of simple, reducible spherical Venn diagrams of five sets. In so doing, we obtain examples of Venn diagrams which yield answers to several problems and conjectures of Grünbaum. Among others, we construct a simple, reducible Venn diagram with five congruent ellipses. We show that this diagram is unique on the sphere and produces two different plane diagrams. This corrects some erroneous statements that started with John Venn more than a century ago in 1880 and have been repeated frequently by others ever since.     

Changing and unchanging domination: a classification

The six classes of graphs resulting from the changing or unchanging of the domination number of a graph when a vertex is deleted, or an edge is deleted or added are considered. Each of these classes has been studied individually in the literature. We consider relationships among the classes, which are illustrated in a Venn diagram. We show that no subset of the Venn diagram is empty for arbitrary graphs, and prove that some of the subsets are empty for connected graphs. Our main result is a characterization of trees in each subset of the Venn diagram.     

Analysis of Venn Diagrams Using Cycles in Graphs

This paper is the last in a series by the authors on the use of graph theory to analyze Venn diagrams on few curves. We complete the construction (and hence the enumeration) of spherical Venn diagrams on five curves, which yields additional results about conjectures of Grünbaum concerning which Venn diagrams are convex, which are exposed, and which can be drawn with congruent ellipses.     

Which n-Venn Diagrams Can Be Drawn with Convex k-Gons?

We establish a new lower bound for the number of sides required for the component curves of simple Venn diagrams made from polygons. Specifically, for any n-Venn diagram of convex k-gons, we prove that k ≥ (2ⁿ - 2 - n) / (n (n - 2)). In the process we prove that Venn diagrams of seven curves, simple or not, cannot be formed from triangles. We then give an example achieving the new lower bound of a (simple, symmetric) Venn diagram of seven convex quadrilaterals. Previously Grunbaum had constructed a symmetric 7-Venn diagram of non-convex 5-gons ["Venn Diagrams II", Geombinatorics 2:25-31, 1992].     

用Venn图表示相互独立事件及其概率

在概率论中，常用Ｖｅｎｎ图来表示事件及其概率，但尚未见用它来表示相互独立事件及其概率的报导．本文提出了一个解决这一问题的方法     

Generating simple convex Venn diagrams

In this paper we are concerned with producing exhaustive lists of simple monotone Venn diagrams that have some symmetry (non-trivial isometry) when drawn on the sphere. A diagram is simple if at most two curves intersect at any point, and it is monotone if it has some embedding on the plane in which all curves are convex. We show that there are 23 such 7-Venn diagrams with a 7-fold rotational symmetry about the polar axis, and that 6 of these have an additional 2-fold rotational symmetry about an equatorial axis. In the case of simple monotone 6-Venn diagrams, we show that there are 39 020 non-isomorphic planar diagrams in total, and that 375 of them have a 2-fold symmetry by rotation about an equatorial axis, and amongst these we determine all those that have a richer isometry group on the sphere. Additionally, 270 of the 6-Venn diagrams also have the 2-fold symmetry induced by reflection about the center of the sphere.Since such exhaustive searches are prone to error, we have implemented the search in a couple of ways, and with independent programs. These distinct algorithms are described. We also prove that the Grünbaum encoding can be used to efficiently identify any monotone Venn diagram.     

Conjugation in Brauer algebras and applications to character theory

The Brauer algebra has a basis of diagrams and these generate a monoid H consisting of scalar multiples of diagrams. Following a recent paper by Kudryavtseva and Mazorchuk, we define and completely determine three types of conjugation in H. We are thus able to define Brauer characters for Brauer algebras which share many of the properties of Brauer characters defined for finite groups over a field of prime characteristic. Furthermore, we reformulate and extend the theory of characters for Brauer algebras as introduced by Ram to the case when the Brauer algebra is not semisimple.     

Sorting dinosaurs: an opportunity to teach mathematics with biology

With the growing desire for increased communication between mathematics teachers and science teachers there is a need for materials specifically written to help bring about communication at that level which also have potential in class. This paper is concerned with one example, a study of dinosaurs through the algebra of sets, simultaneously exploring and developing a topic in biology and a topic in mathematics by raising a series of questions about dinosaurs which are most effectively answered by means of mathematics.

Initially the questions asked can be answered by means of Venn diagrams, and set notation is no more than an alternative, brief way of expressing the same answer. But systematically the Venn diagrams become more involved and there is a growing dependence upon the algebra of sets so that ultimately answers are sought by that means and Venn diagrams are used (if at all) to reinforce the findings. Very many aspects of set notation and algebra are incorporated into the study and a number of set theories illustrated.

Some aspects of its possible use in class are considered.     

Plücker environments, wiring and tiling diagrams, and weakly separated set-systems

For the ordered set [n] of n elements, we consider the class Bn of bases B of tropical Plücker functions on ²[n] such that B can be obtained by a series of so-called weak flips (mutations) from the basis formed by the intervals in [n]. We show that these bases are representable by special wiring diagrams and by certain arrangements generalizing rhombus tilings on an n-zonogon. Based on the generalized tiling representation, we then prove that each weakly separated set-system in ²[n] having maximum possible size belongs to Bn, yielding the affirmative answer to one conjecture due to Leclerc and Zelevinsky. We also prove an analogous result for a hyper-simplex .     

New Roses: Simple Symmetric Venn Diagrams with 11 and 13 Curves

A symmetric \(n\) -Venn diagram is one that is invariant under \(n\) -fold rotation, up to a relabeling of curves. A simple \(n\) -Venn diagram is an \(n\) -Venn diagram in which at most two curves intersect at any point. In this paper, we introduce a new property of Venn diagrams called crosscut symmetry, which is related to dihedral symmetry. Utilizing a computer search restricted to diagrams with crosscut symmetry, we found many simple symmetric Venn diagrams with 11 curves. The question of the existence of a simple 11-Venn diagram has been open since the 1960s. The technique used to find the 11-Venn diagram is extended and a symmetric 13-Venn diagram is also demonstrated.     

Chromatic number of Hasse diagrams,eyebrows and dimension

We construct posets of dimension 2 with highly chromatic Hasse diagrams. This solves a previous problem by Nesetril and Trotter.     

Hypergraph planarity and the complexity of drawing venn diagrams

We introduce two new notions of planarity for hypergraphs based on dual generalizations of the standard Venn diagram. These definitions are illustrated by results concerning the existence and nonexistence of such diagrams for certain classes of hypergraphs. We conclude by showing that the general problem of determining whether such diagrams exist is NP-complete.     

Coincidences among skew Schur functions

New sufficient conditions and necessary conditions are developed for two skew diagrams to give rise to the same skew Schur function. The sufficient conditions come from a variety of new operations related to ribbons (also known as border strips or rim hooks). The necessary conditions relate to the extent of overlap among the rows or among the columns of the skew diagram.     

FLUIDIFICATION OF QUIVERS AND THE TIETZE EXTENSION THEOREM FOR DIAGRAMS OF TOPOLOGICAL SPACES

For quivers with no directed cycles, the concept of fluidification is defined and used to prove that, under corresponding assumptions, the Tietze extension theorem for diagrams of topological spaces modeled on such quivers holds. Another application of the given concept of fluidification -is a characterization of certain diagrams of proper maps.     

The cover pebbling number of graphs

A pebbling move on a graph consists of taking two pebbles off of one vertex and placing one pebble on an adjacent vertex. In the traditional pebbling problem we try to reach a specified vertex of the graph by a sequence of pebbling moves. In this paper we investigate the case when every vertex of the graph must end up with at least one pebble after a series of pebbling moves. The cover pebbling number of a graph is the minimum number of pebbles such that however the pebbles are initially placed on the vertices of the graph we can eventually put a pebble on every vertex simultaneously. We find the cover pebbling numbers of trees and some other graphs. We also consider the more general problem where (possibly different) given numbers of pebbles are required for the vertices.     

Unavoidable Traces Of Set Systems

Sauer, Shelah, Vapnik and Chervonenkis proved that if a set system on n vertices contains many sets, then the set system has full trace on a large set. Although the restriction on the size of the groundset cannot be lifted, Frankl and Pach found a trace structure that is guaranteed to occur in uniform set systems even if we do not bound the size of the groundset. In this note we shall give three sequences of structures such that every set system consisting of sufficiently many sets contains at least one of these structures with many sets.     

On the sum of the Laplacian eigenvalues of a tree

Given an n-vertex graph G=(V,E), the Laplacian spectrum of G is the set of eigenvalues of the Laplacian matrix L=D-A, where D and A denote the diagonal matrix of vertex-degrees and the adjacency matrix of G, respectively. In this paper, we study the Laplacian spectrum of trees. More precisely, we find a new upper bound on the sum of the k largest Laplacian eigenvalues of every n-vertex tree, where k∈{1,…,n}. This result is used to establish that the n-vertex star has the highest Laplacian energy over all n-vertex trees, which answers affirmatively to a question raised by Radenkovi? and Gutman [10].     

Minimum cycle bases of graphs on surfaces

In this paper we study the cycle base structures of embedded graphs on surfaces. We first give a sufficient and necessary condition for a set of facial cycles to be contained in a minimum cycle base (or MCB in short) and then set up a 1-1 correspondence between the set of MCBs and the set of collections of nonseparating cycles which are in general positions on surfaces and are of shortest total length. This provides a way to enumerate MCBs in a graph via nonseparating cycles. In particular, some known results such as P.F. Stadler's work on Halin graphs [Minimum cycle bases of Halin graphs, J. Graph Theory 43 (2003) 150-155] and Leydold and Stadler's results on outer-planar graphs [Minimum cycle bases of outerplanar graphs, Electronic J. Combin. 5(16) (1998) 14] are concluded. As applications, the number of MCBs in some types of graphs embedded in lower surfaces (with arbitrarily high genera) is found. Finally, we present an interpolation theorem for the number of one-sided cycles contained in MCB of an embedded graph.     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday