Homotopy Sphere Representations for Matroids

For any rank r oriented matroid M, a construction is given of a ??topological representation?? of M by an arrangement of homotopy spheres in a simplicial complex which is homotopy equivalent to S ^r?C1 . The construction is completely explicit and depends only on a choice of maximal flag in M. If M is orientable, then all Folkman-Lawrence representations of all orientations of M embed in this representation in a homotopically nice way.     

Minimum Difference Representations of Graphs

Define a k-minimum-difference-representation (k-MDR) of a graph G to be a family of sets \({\{S(v): v\in V(G)\}}\) such that u and v are adjacent in G if and only if min{|S(u)?S(v)|, |S(v)?S(u)|} ≥ k. Define ρ _min(G) to be the smallest k for which G has a k-MDR. In this note, we show that {ρ _min(G)} is unbounded. In particular, we prove that for every k there is an n ₀ such that for n > n ₀ ‘almost all’ graphs of order n satisfy ρ _min(G) > k. As our main tool, we prove a Ramsey-type result on traces of hypergraphs.     

Constraint-Based Representations of Statistical Graphs

Abstract

Pictor is an environment for statistical graphics that promotes simple commands for common uses and offers the ability to experiment with whole new paradigms. Pictor describes graphs as graphical objects whose component pieces are related by several sorts of constraints. This article describes in detail the constraint system that Pictor uses.     

P-Adic and Non-Archimedean Product Representations

Two algorithms are introduced and shown to lead to a unique product representation for a given p-adic integer A with leading coefficient 1, as a product of terms \(1+{1\over a_n}\) where the a _n are certain rational numbers. The degree of approximation by the N-th partial product of such terms is investigated, and in some explicit cases the products corresponding to particular types of p-adic integers are characterized. In addition, we consider similar representations for elements of arbitrary complete non-archimedean fields with discrete valuations.     

Planar Graphs Have 1-string Representations

We prove that every planar graph is an intersection graph of strings in the plane such that any two strings intersect at most once.     

Shrinkability of Minimal Elements in Sphere Representations of Posets

Let k be a positive integer and let P = (X,≤) be a poset. We call P a k-sphere order provided there is a mapping f which assigns to each element x $ \in$ X a ball f(x) in Rk so that x ≤ y in P if and only if f(x) $ \subseteq$ f(y). We ask: Given that P is a k-sphere order, does there necessarily exist a representation f with the property that every minimal element of P is assigned a ball of radius zero? The answer is “yes” for k = 1, but “no” for all k ≥ 2.     

Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs

The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of graphs.     

Representations of Quantum Affinizations and Fusion Product

In this paper we study general quantum affinizations of symmetrizable quantum Kac-Moody algebras and we develop their representation theory. We prove a triangular decomposition and we give a classication of (type 1) highest weight simple integrable representations analog to Drinfel'd-Chari-Presley one. A generalization of the q-characters morphism, introduced by Frenkel-Reshetikhin for quantum affine algebras, appears to be a powerful tool for this investigation. For a large class of quantum affinizations (including quantum affine algebras and quantum toroidal algebras), the combinatorics of q-characters give a ring structure * on the Grothendieck group of the integrable representations that we classified. We propose a new construction of tensor products in a larger category by using the Drinfel'd new coproduct (it cannot directly be used for because it involves infinite sums). In particular, we prove that * is a fusion product (a product of representations is a representation).     

Sphere Packings, VI. Tame Graphs and Linear Programs

This paper is the sixth and final part in a series of papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In a previous paper in this series, a continuous function f on a compact space is defined, certain points in the domain are conjectured to give the global maxima, and the relation between this conjecture and the Kepler conjecture is established. In this paper we consider the set of all points in the domain for which the value of f is at least the conjectured maximum. To each such point, we attach a planar graph. It is proved that each such graph must be isomorphic to a tame graph, of which there are only finitely many up to isomorphism. Linear programming methods are then used to eliminate all possibilities, except for three special cases treated in earlier papers: pentahedral prisms, the face-centered cubic packing, and the hexagonal-close packing. The results of this paper rely on long computer calculations.     

图的笛卡儿积及字典式积的连通性

文章给出了两个图的笛卡儿积及字典式的积为最大边连通的、最大连通的、super-λ,super-κ及hyper-κ的充分条件,同时证明了其中一些条件也是必要的.此外,对这两种积的局部割集和广义割集的性质也进行了考虑.     

Expansion Of Product Replacement Graphs

We establish a connection between the expansion coefficient of the product replacement graph Γ_k(G) and the minimal expansion coefficient of a Cayley graph of G with k generators. In particular, we show that the product replacement graphs Γ_k(PSL(2,p)) form an expander family, under assumption that all Cayley graphs of PSL(2,p), with at most k generators are expanders. This gives a new explanation of the outstanding performance of the product replacement algorithm and supports the speculation that all product replacement graphs are expanders [42,52].     

两个图的积的S-不可收缩性(英)

本文从组合角度明确给出了两个图的积是S-不可收缩的特征．     

乘积图的全色数

本文得到了有关乘积图的全色数的一些结果,并利用这些结果证明了Mesh图和Tours-图均满足全色数猜想．特别,几乎所有的Mesh-图都是第一类图．     

On Cartesian Product of Factor-Critical Graphs

A graph G is k-factor-critical if G ? S has a perfect matching for any k-subset S of V(G). In this paper, we investigate the factor-criticality in Cartesian products of graphs and show that Cartesian product of an m-factor-critical graph and an n-factor-critical graph is ${(m+n+\varepsilon )}$ -factor-critical, where ${\varepsilon = 0}$ if both of m and n are even; ${\varepsilon = 1}$ , otherwise. Moreover, this result is best possible.     

若干笛卡尔积图的邻点可区别E-全染色

图G(V,E)的k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射,如果u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到了Pm×Pn,Pm×Cn,Cm×Cn的邻点可区别E-全色数,其中C(u)={f(u)}∪{f(uv)uv∈E(G)}.     

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K _n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G ₁ and G ₂ with η(G ₁) = h and η(G ₂) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following:

图的字典积的非零整数流(英文)

充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流.