On generalized Kneser hypergraph colorings

In 2002, the second author presented a lower bound for the chromatic numbers of hypergraphs , “generalized r-uniform Kneser hypergraphs with intersection multiplicities s.” It generalized previous lower bounds by K?í? (1992/2000) for the case s=(1,…,1) without intersection multiplicities, and by Sarkaria (1990) for . Here we discuss subtleties and difficulties that arise for intersection multiplicities si>1:

(1)

In the presence of intersection multiplicities, there are two different versions of a “Kneser hypergraph,” depending on whether one admits hypergraph edges that are multisets rather than sets. We show that the chromatic numbers are substantially different for the two concepts of hypergraphs. The lower bounds of Sarkaria (1990) and Ziegler (2002) apply only to the multiset version.

(2)

The reductions to the case of prime r in the proofs by Sarkaria and by Ziegler work only if the intersection multiplicities are strictly smaller than the largest prime factor of r. Currently we have no valid proof for the lower bound result in the other cases.

We also show that all uniform hypergraphs without multiset edges can be represented as generalized Kneser hypergraphs.     

Oriented matroid systems

The domination invariant has played an important part in reliability theory. While most of the work in this field has been restricted to various types of network system models, many of the results can be generalized to much wider families of systems associated with matroids. Previous papers have explored the relation between undirected network systems and matroids. In this paper the main focus is on directed network systems and their relation to oriented matroids. An oriented matroid is a special type of matroid where the circuits are signed sets. Using these signed sets one can e.g., obtain a set theoretic representation of the direction of the edges of a directed network system. Classical results for directed network systems include the fact that the signed domination is either +1 or −1 if the network is acyclic, and zero otherwise. It turns out that these results can be generalized to systems derived from oriented matroids. Several classes of systems for which the generalized results hold will be discussed. These include oriented versions of k-out-of-n systems and a certain class of systems associated with matrices.     

On the chromatic number of an oriented matroid

We prove that the chromatic number of an oriented matroid of rank r3 is at most r+1 with equality if and only if is the oriented matroid of an orientation of K_r+1, the complete graph on r+1 vertices.     

Solution of Hadwiger-Levi's Covering Problem for Duals of Cyclic 2k-Polytopes

For a collection C of convex bodies let h(C) be the minimum number m with the property that every element K of C can be covered by m or fewer smaller homothetic copies of K. Denote by C _d ^* the collection of all duals of cyclic d-polytopes, d 2. We show that h(C _2k ^* )=(k +1)2 for any k 2. We also prove the inequalities (d+1) (d+3)/4 h(C _d ^* ) (d+1) 2/2$ for any d 2.     

Bias matroids with unique graphical representations

Given a 3-connected biased graph Ω with three node-disjoint unbalanced circles, at most one of which is a loop, we describe how the bias matroid of Ω is uniquely represented by Ω.     

A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)

The vertices of Kneser graph $K(n,k)$ are the subsets of $\{1,2,\dots ,n\}$ of cardinality $k$, two vertices are adjacent if and only if they are disjoint. The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ with two vertices adjacent if their distance in $G$ is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when $n=2k+1$. It is believed that $\chi \left(K^2(2k+1,k)\right)=2k+c$ where $c$ is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: $8k∕3+20∕3$ for 1$k\ge 3$ (Kim and Park, 2014) and $32k∕15+32$ for $k\ge 7$ (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to $\chi \left(K^2(2k+1,k)\right)\le 5k∕2+c$, where $c$ is a constant in $\{5∕2,9∕2,5,6\}$, depending on $k\ge 2$.     

On the structure of parabolic subgroups

The main aim of this paper is to show that the Jacobson and Brown-McCoy radicals of rings graded by free groups are homogeneous. As an application we get some information on the structure of the Jacobson radical of monomial rings. In particular we give a positive answer to a question posed in [12]. We extend also a result of [13] on the Brown-McCoy radical of polynomial rings in non-commutative variables. Actually this and the question of [12] motivated our studies.     

闭模糊拟阵模糊圈的算法研究

用闭模糊拟阵的基本序列来研究和描述它的模糊圈,找到了从闭模糊拟阵的模糊相关集或模糊独立集计算模糊圈的方法,并给出了相应的算法.     

Criss-cross methods: A fresh view on pivot algorithms

Criss-cross methods are pivot algorithms that solve linear programming problems in one phase starting with any basic solution. The first finite criss-cross method was invented by Chang, Terlaky and Wang independently. Unlike the simplex method that follows a monotonic edge path on the feasible region, the trace of a criss-cross method is neither monotonic (with respect to the objective function) nor feasibility preserving. The main purpose of this paper is to present mathematical ideas and proof techniques behind finite criss-cross pivot methods. A recent result on the existence of a short admissible pivot path to an optimal basis is given, indicating shortest pivot paths from any basis might be indeed short for criss-cross type algorithms. The origins and the history of criss-cross methods are also touched upon.     

The equipartition polytope. I: Formulations,dimension and basic facets

The following basic clustering problem arises in different domains, ranging from physics, statistics and Boolean function minimization.Given a graphG = (V, E) and edge weightsc _e , partition the setV into two sets of 1/2|V| and 1/2|V| nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized.Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we give some integer programming formulations of the equicut problem, study the dimension of the equicut polytope and describe some basic classes of facet-inducing inequalities forQ(G). Partial support of NSF grants DMS 8606188 and ECS 8800281.This work was done while these two authors visited IASI, Rome, in Spring 1987.