The multidimensional cube recurrence

We introduce a recurrence which we term the multidimensional cube recurrence, generalizing the octahedron recurrence studied by Propp, Fomin and Zelevinsky, Speyer, and Fock and Goncharov and the three-dimensional cube recurrence studied by Fomin and Zelevinsky, and Carroll and Speyer. The states of this recurrence are indexed by tilings of a polygon with rhombi, and the variables in the recurrence are indexed by vertices of these tilings. We travel from one state of the recurrence to another by performing elementary flips. We show that the values of the recurrence are independent of the order in which we perform the flips; this proof involves nontrivial combinatorial results about rhombus tilings which may be of independent interest. We then show that the multidimensional cube recurrence exhibits the Laurent phenomenon - any variable is given by a Laurent polynomial in the other variables. We recognize a special case of the multidimensional cube recurrence as giving explicit equations for the isotropic Grassmannians IG(n−1,2n). Finally, we describe a tropical version of the multidimensional cube recurrence and show that, like the tropical octahedron recurrence, it propagates certain linear inequalities.     

On the cardinality of a semi-algebraic set

It is shown that the cardinality of a finite semi-algebraic subset over a real closed field can be computed in terms of signatures of effectively constructed quadratic forms.     

The cardinality of functionally complete algebras on a three element set

It is known that there are continuum pairwise non-equivalent functionally complete algebras with the base set A if |A| ≥ 3. In this paper we prove the same statement for |A| = 3. Received December 20, 1996; accepted in final form July 3, 1997.     

Cycles intersecting a prescribed vertex set

A graph is said to have property P(k,l)(k ? l) if for any X ∈ (^G_k) there exists a cycle such that |X ∩ V(C)| = l. Obviously an n-connected graph (n ? 2) satisfies P(n,n). In this paper, we study parameters k and l such that every n-connected graph satisfies P(k,l). We show that for r = 1 or 2 every n-connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3-connected graphs that do not satisfy P(6,3). However, if n ? max{3,(2r ?1)(r + 1)}, then every n-connected graph satisfies P(n + r,n).     

Intersecting a simple mixed integer set with a vertex packing set

We consider a mixed integer set that results from the intersection of a simple mixed integer set with a vertex packing set from a conflict graph. This set arises as a relaxation of the feasible set of mixed integer problems such as inventory routing problems. We derive families of strong valid inequalities that consider the structures of the simple mixed integer set and the vertex packing set simultaneously.     

一类四元素数字集的正交函数的个数

自仿测度的谱与非谱问题近年引起了很大的关注,关于自仿测度的非谱问题,其中之一就是要估算它在L2空间上的正交指数的个数．通过对μM,D傅里叶变换的零点集性质的分析和讨论,对现有的结论进行了改进,确定了相应四元素数字集的平面自仿测度在L2的空间上正交指数函数的最大个数为3．     

The hyperspace of hereditarily decomposable subcontinua of a cube is the Hurewicz set

The hyperspaces of hereditarily decomposable continua and of decomposable subcontinua without pseudoarcs in the cube of dimension greater than 2 are homeomorphic to the Hurewicz set of all nonempty countable closed subsets of the unit interval [0,1]. Moreover, in such a cube, all indecomposable subcontinua form a homotopy dense subset of the hyperspace of (nonempty) subcontinua.     

Boundary set imbeddings in the Hilbert cube

We make the following remarks. Every boundary set in the Hilbert cube can be reimbedded as a dense σZ-set whose complement is not l². There exist spaces that can be imbedded as a boundary set in more than one way. We also give a necessary condition for a space to be imbeddable as a boundary set.     

On the maximum cardinality of a consistent set of arcs in a random tournament

For any tournament T on n vertices, let h(T) denote the maximum number of edges in the intersection of T with a transitive tournament on the same vertex set. Sharpening a previous result of Spencer, it is proved that, if T_n denotes the random tournament on n vertices, then, $\text{P}$$\text{(h(T}{}_{\mathrm{n}}\text{) ≤}\text{1}\text{2}\text{(}{}_2{}^{\mathrm{n}}\text{) + 1.73n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{) → 1}$ as n → ∞.     

The cardinality of the set of all clones containing a given minimal clone on three elements

All minimal clones on three elements were found by B. Csákány. In this paper, for each minimal clone the cardinality of the set of all clones containing this clone is found.     

Divergence of the greedy algorithm in the Faber-Schauder system on a continuum cardinality set

The paper establishes that there exist a continuum cardinality set E ₀ ? [0, 1] and a function f ₀(x) ∈ C _[0,1], such that the greedy algorithm of f ₀(x) with respect to the Faber-Schauder system converges to +∞ at all points of E ₀.     

A fully benzenoid system has a unique maximum cardinality resonant set

A benzenoid system is a 2-connected plane graph such that its each inner face is a regular hexagon of side length 1. A benzenoid system is Kekuléan if it has a perfect matching. Let P be a set of hexagons of a Kekuléan benzenoid system B. The set P is called a resonant set of B if the hexagons in P are pair-wise disjoint and the subgraph B−P (obtained by deleting from B the vertices of the hexagons in P) is either empty or has a perfect matching. It was shown (Gutman in Wiss. Z. Thechn. Hochsch. Ilmenau 29:57–65, 1983; Zheng and Chen in Graphs Comb. 1:295–298, 1985) that for every maximum cardinality resonant set P of a Kekuléan benzenoid system B, the subgraph B−P is either empty or has a unique perfect matching. A Kekuléan benzenoid system B is said to be fully benzenoid if there exists a maximum cardinality resonant set P of B, such that the subgraph B−P is empty. It is shown that a fully benzenoid system has a unique maximum cardinality resonant set, a well-known statement that, so far, has remained without a rigorous proof.     

Covering the vertex set of a graph with subgraphs of smaller degree

The problem of covering the vertex set of a graph with subsets spanning subgraphs of smaller degree is studied. The result of this study is applied to give a new bound on the chromatic number of a graph in terms of the maximum vertex-degree of the graph and the maximum number of vertices in a clique of the graph. By using this bound, it is shown that if d is at least 7 and e is at least 4, then there is no regular graph of valency d, chromatic number d, whose smallest circuit has at least e edges; this settles a conjecture of Branko Grünbaum.     

On the cardinality of the Pareto set in bicriteria shortest path problems

Computing shortest paths with two or more conflicting optimization criteria is a fundamental problem in transportation and logistics. We study the problem of finding all Pareto-optimal solutions for the multi-criteria single-source shortest-path problem with nonnegative edge lengths. The standard approaches are generalizations of label-setting (Dijkstra) and label-correcting algorithms, in which the distance labels are multi-dimensional and more than one distance label is maintained for each node. The crucial parameter for the run time and space consumption is the total number of Pareto optima. In general, this value can be exponentially large in the input size. However, in various practical applications one can observe that the input data has certain characteristics, which may lead to a much smaller number—small enough to make the problem efficiently tractable from a practical viewpoint. For typical characteristics which occur in various applications we study in this paper whether we can bound the size of the Pareto set to a polynomial size or not. These characteristics are also evaluated (1) on a concrete application scenario (computing the set of best train connections in view of travel time, fare, and number of train changes) and (2) on a simplified randomized model. It will turn out that the number of Pareto optima on each visited node is restricted by a small constant in our concrete application, and that the size of the Pareto set is much smaller than our worst case bounds in the randomized model. A preliminary short version of this paper appeared in the Proceedings of the 5th Workshop on Algorithm Engineering (WAE 2001), LNCS 2141, Springer Verlag, pp. 185–197 (2001) under the title “Pareto shortest paths is often feasible in practice.”     

Applying local search to the feedback vertex set problem

The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In spite of the importance of this NP-hard problem, no local search approach had been proposed so far for tackling it. Building on a property of acyclic graphs, we suggest in this paper a new representation of the solutions of the FVSP (feedback sets). Thanks to this solution representation, we are able to design a local transformation (equivalent to a neighborhood) that changes a feedback set into a new one. Based on this neighborhood, we have developed a simulated annealing algorithm for the FVSP. Our experiments show that our algorithm outperforms the best existing heuristic, namely the greedy adaptive search procedure by Pardalos et al.