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.     

Tolerance graphs,and orders

We show that, if a tolerance graph is the complement of a comparability graph, it is a trapezoid graph, i.e., the complement of an order of interval dimension at most 2. As consequences we are able to give obstructions for the class of bounded tolerance graphs and to give an example of a graph that is alternatingly orientable but not a tolerance graph. We also characterize the tolerance graphs among complements of trees. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 129–140, 1998     

Abelian varieties and the general Hodge conjecture

We investigate the relationship between the usual and general Hodgeconjectures for abelian varieties. For certain abelian varieties A, weshow that the usual Hodge conjecture for all powers of A implies thegeneral Hodge conjecture for A.     

The multiplicative group action on singular varieties and Chow varieties

We answer two questions of Carrell on a singular complex projective variety admitting the multiplicative group action, one positively and the other negatively. The results are applied to Chow varieties and we obtain Chow groups of 0-cycles and Lawson homology groups of 1-cycles for Chow varieties. A brief survey on the structure of Chow varieties is included for comparison and completeness. Moreover, we give counterexamples to Shafarevich's problem on the rationality of the irreducible components of Chow varieties.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

Small cycle double covers of products I: Lexicographic product with paths and cycles

Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if G does not have an isolated vertex then G □ P₂ and G □ C_2k have SCDCs. If G has an SCDC then so does G □ P_k, k > 2 and G □ C_{2k + 1}. We use these Cartesian results to show that P_2j[G] (j ≥ 1) and C_k[G] (k ≠ 3, 5, 7) have SCDCs. Also, if G has an SCDC then so does P_{2j + 1}[G] (j ≥ 4). The results for the lexicographic product are harder and, in addition to the Cartesian results, require certain decompositions of K_n,n into perfect matchings. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 99–123, 2008     

Brauer Diagrams, Updown Tableaux and Nilpotent Matrices

We interpret geometrically a variant of the Robinson-Schensted correspondence which links Brauer diagrams with updown tableaux, in the spirit of Steinberg's result [32] on the original Robinson-Schensted correspondence. Our result uses the variety of all where is a complete flag in is a nondegenerate alternating bilinear form on and N is a nilpotent element of the Lie algebra of the simultaneous stabilizer of both and instead of Steinberg's variety of where are two complete flags in and N is a nilpotent element of the Lie algebra of the simultaneous stabilizer of both .     

The basis number of the composition of theta graphs with stars and wheels

he basis number, b(G), of a graph G is defined to be the least integer k such that G has a k-fold basis for its cycle space. In this paper we investigate the basis number of the composition of theta graphs with stars and wheels. This revised version was published online in June 2006 with corrections to the Cover Date.     

Enumeration of perfect matchings of a type of Cartesian products of graphs

Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by P_m and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let C_n denote the cycle with n vertices. Then Pm(C₄×T)=∏(2+α²), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C₄×T) is always a square or double a square.2. Let T be a tree. Then Pm(P₄×T)=∏(1+3α²+α⁴), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P₃×T)=∏(2+α²), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C₄×T)=[Pm(P₃×T)]².     

偶错位图的张量幂的最大独立集和自同构群

若A_n 是X := {1, 2,..., n} 上的偶置换构成的交错群, E_n 是X 上的偶错位集, 则Cayley 图AΓ_n := Γ(A_n, E_n) 称为偶错位图. 令AΓ_n^q 为q 个AΓ_n 的张量幂. 在本文中, 我们研究了AΓ_n^q 的连通性、直径、独立数、团数、色数和最大独立集等性质. 利用AΓ_n^q 最大独立集的结果, 我们完全确定了AΓ_n^q 的自同构群的结构.     

Schubert varieties, linear codes and enumerative combinatorics

We consider linear error correcting codes associated to higher-dimensional projective varieties defined over a finite field. The problem of determining the basic parameters of such codes often leads to some interesting and difficult questions in combinatorics and algebraic geometry. This is illustrated by codes associated to Schubert varieties in Grassmannians, called Schubert codes, which have recently been studied. The basic parameters such as the length, dimension and minimum distance of these codes are known only in special cases. An upper bound for the minimum distance is known and it is conjectured that this bound is achieved. We give explicit formulae for the length and dimension of arbitrary Schubert codes and prove the minimum distance conjecture in the affirmative for codes associated to Schubert divisors.     

Approximate varieties, approximate ideals and dimension reduction

We consider a method to determine, for a given finite set of points, an algebraic variety of small degree which contains these points. In contrast to most other algorithms in Computer Algebra, this one is adapted to numerical, inexact computations. Dedicated to Walter Gautschi, an admirable and outstanding scientist and gentleman.     

Sphericity, cubicity, and edge clique covers of graphs

The sphericity sph(G) of a graph G is the minimum dimension d for which G is the intersection graph of a family of congruent spheres in R^d. The edge clique cover number θ(G) is the minimum cardinality of a set of cliques (complete subgraphs) that covers all edges of G. We prove that if G has at least one edge, then sph(G)?θ(G). Our upper bound remains valid for intersection graphs defined by balls in the L_p-norm for 1?p?∞.     

一个五阶图与路、圈的联图的交叉数

目前已经确定的两个图的联图的交叉数结果较少.设H是由一个4圈及一个孤立点所构成的5阶图.研究了图H与路、圈的联图的交叉数,得到了cr(H+P_n)=Z(5,n)+[n/2]+l,cr(H+C_n):Z(5,n)+[n/2]+2,其中,P_n与C_n分别表示含n个顶点的路与圈.     

Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks

We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian), by Thomassen (every 4-connected line graph is Hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent to the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjá?ek and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjá?ek in 1997.     

Isometric cycles,cutsets, and crowning of bridged graphs

A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that d_G(x,y) < d_C(x,y). A cycle C is isometric if d_G(x,y) = d_C(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that d_G(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003     

Graded quiver varieties,quantum cluster algebras and dual canonical basis

Inspired by a previous work of Nakajima, we consider perverse sheaves over acyclic graded quiver varieties and study the Fourier–Sato–Deligne transform from a representation theoretic point of view. We obtain deformed monoidal categorifications of acyclic quantum cluster algebras with specific coefficients. In particular, the (quantum) positivity conjecture is verified whenever there is an acyclic seed in the (quantum) cluster algebra.