About a new class of matroid-inducing packing families

Let T be a family of graphs. A T-packing of a graph G is a subgraph of G, components of which are isomorphic to members of T. We are concerned with families T, such that in every graph G, the subsets of vertices that can be saturated by some T-packing form a collection of independent sets of a matroid. The main purpose of this paper is to introduce a new class of families with this property.     

The Möbius function of permutations with an indecomposable lower bound

We show that the Möbius function of an interval in a permutation poset where the lower bound is sum (resp. skew) indecomposable depends solely on the sum (resp. skew) indecomposable permutations contained in the upper bound, and that this can simplify the calculation of the Möbius sum. For increasing oscillations, we give a recursion for the Möbius sum which only involves evaluating simple inequalities.     

On the Complexity of Cover-Incomparability Graphs of Posets

In this paper we show that the recognition problem for C-I graphs of posets is NP-complete. On the other hand, we prove that induced subgraphs of C-I graphs are exactly complements of comparability graphs, and hence the recognition problem for induced subgraphs of C-I graphs of posets is polynomial.     

A Priestley Sum of Finite Trees is Acyclic

We show that the Priestley sum of finite trees contains no cyclic finite poset. The first author would like to express his thanks for support from project LN 1M0021620808 of the Ministry of Education of the Czech Republic. The second author would like to express his thanks for support from project 1M0021620808 of the Ministry of Education of the Czech Republic, from the NSERC of Canada and from a PROF grant from the University of Denver. The third author would like to express his thanks for the support from the NSERC of Canada and for partial support from the project 1M0021620808 of the Ministry of Education of the Czech Republic.     

Silver Cubes

An n × n matrix A is said to be silver if, for i = 1,2,...,n, each symbol in {1,2,...,2n − 1} appears either in the ith row or the ith column of A. The 38th International Mathematical Olympiad asked whether a silver matrix exists with n = 1997. More generally, a silver cube is a triple (K _n ^d , I, c) where I is a maximum independent set in a Cartesian power of the complete graph K _n , and is a vertex colouring where, for v ∈ I, the closed neighbourhood N[v] sees every colour. Silver cubes are related to codes, dominating sets, and those with n a prime power are also related to finite geometry. We present here algebraic constructions, small examples, and a product construction. The nonexistence of silver cubes for d = 2 and some values of n, is proved using bounds from coding theory. Luis A. Goddyn: This research was supported by a Canada NSERC Discovery Grant. Ebadollah S. Mahmoodian: Partially supported by the institutes CECM and IRMACS and the departments of Mathematics and Computing Science at Simon Fraser University. Grateful thanks are extended here and also to the Institute for Advanced Studies in Basic Sciences, Iran for support in the final stages of this paper.     

Edge ranking and searching in partial orders

We consider a problem of searching an element in a partially ordered set (poset). The goal is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi and Newman considered a special case where the partial order has the maximum element and the Hasse diagram is a tree (tree-like posets) and they gave an O(n⁴log³n)-time algorithm for finding an optimal search strategy for such a partial order. We show that this problem is equivalent to finding edge ranking of a simple tree corresponding to the Hasse diagram, which implies the existence of a linear-time algorithm for this problem.Then we study a more general problem, namely searching in any partial order with maximum element. We prove that such a generalization is hard, and we give an -approximate polynomial-time algorithm for this problem.     

On the Circuit-cocircuit Intersection Conjecture

Oxley has conjectured that for k≥4, if a matroid M has a k-element set that is the intersection of a circuit and a cocircuit, then M has a (k−2)-element set that is the intersection of a circuit and a cocircuit. In this paper we prove a stronger version of this conjecture for regular matroids. We also show that the stronger result does not hold for binary matroids. The second author was partially supported by CNPq (grant no 302195/02-5) and the ProNEx/CNPq (grant no 664107/97-4).     

Generalized domination in closure systems

In the context of extracting maximal item sets and association rules from a binary data base, the graph-theoretic notion of domination was recently used to characterize the neighborhood of a concept in the corresponding lattice.In this paper, we show that the notion of domination can in fact be extended to any closure operator on a finite universe and be efficiently encoded into propositional Horn functions. This generalization enables us to endow notions and algorithms related to Formal Concept Analysis with Horn minimization and minimal covers of functional dependencies in Relational Databases.     

Obtainable sizes of topologies on finite sets

We study the smallest possible number of points in a topological space having k open sets. Equivalently, this is the smallest possible number of elements in a poset having k order ideals. Using efficient algorithms for constructing a topology with a prescribed size, we show that this number has a logarithmic upper bound. We deduce that there exists a topology on n points having k open sets, for all k in an interval which is exponentially large in n. The construction algorithms can be modified to produce topologies where the smallest neighborhood of each point has a minimal size, and we give a range of obtainable sizes for such topologies.     

Four matroidal structures of covering and their relationships with rough sets

Covering is a common form of data representation, and covering-based rough sets serve as an efficient technique to process this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard so that most algorithms to solve them are greedy. Matroids provide well-established platforms for greedy algorithm foundation and implementation. Therefore, it is necessary to integrate covering-based rough set with matroid. In this paper, we propose four matroidal structures of coverings and establish their relationships with rough sets. First, four different viewpoints are presented to construct these four matroidal structures of coverings, including 1-rank matroids, bigraphs, upper approximation numbers and transversals. The respective advantages of these four matroidal structures to rough sets are explored. Second, the connections among these four matroidal structures are studied. It is interesting to find that they coincide with each other. Third, a converse view is provided to induce a covering by a matroid. We study the relationship between this induction and the one from a covering to a matroid. Finally, some important concepts of covering-based rough sets, such as approximation operators, are equivalently formulated by these matroidal structures. These interesting results demonstrate the potential to combine covering-based rough sets with matroids.     

A new algorithm for the intersection of a line with the independent set polytope of a matroid

We present a new algorithm for the problem of determining the intersection of a half-line with the independent set polytope of a matroid. We show it can also be used to compute the strength of a graph and the corresponding partition using successive contractions. The algorithm is based on the maximization of successive linear forms on the boundary of the polytope. We prove it is a polynomial algorithm in probability with average number of iterations in O(n⁵). Finally, numerical tests reveal that it should only require O(n²) iterations in practice.     

A General Zero-Knowledge Scheme

There is a great similarity between the zero-knowledge proof of quadratic residuocity presented by Goldwasser-Micali-Rackoff and the graph isomorphism proof presented by Goldreich-Micali-Wigderson. There is also a resemblance between the zero-knowledge proofs of Fiat-Shamir, Chaum-Evertse-van de Graaf, Beth and Guillou-Quisquater. A similar observation holds for zero-knowledge proofs based on encryption: the 3-colourability proofs and the Hamiltonian-circuit proofs of Blum and Goldreich-Micali-Wigderson, and the Brassard-Chaum-Crepeau proof for SAT. Feige, Fiat and Shamir introduced the concept of zero-knowledge proofs of knowledge. In this paper we present a general zero-knowledge scheme which unifies all these Arthur-Merlin proofs.     

二部图是可迹的一个充分条件

本文证明了以下结果:设G=(X,Y;E)是连通的二部图,如果4≤|Y|≤|X|≤|Y|+1,且NC_2≥|X|-1,则G是可迹的。从而表明[2]中的猜想对二部图是成立的。     

Maximal caps in AG (6, 3)

We show that there are no complete 44-caps in AG(5, 3). We then use this result to prove that the maximal size for a cap in AG(6, 3) is equal to 112, and that the 112-caps in AG(6, 3) are unique up to affine equivalence.      

Counting reducible and singular bivariate polynomials

Among the bivariate polynomials over a finite field, most are irreducible. We count some classes of special polynomials, namely the reducible ones, those with a square factor, the “relatively irreducible” ones which are irreducible but factor over an extension field, and the singular ones, which have a root at which both partial derivatives vanish.     

Corrigendum to “Toric codes and finite geometries” [Finite Fields Appl. 45 (2017) 203–216]

This correction adds a necessary hypothesis in Proposition 2.4 of [1]. A counterexample to the previous version was pointed out to the author by Melda Görür and the author thanks her for bringing that to his attention. Theorem 3.2 and Corollary 3.3 are also reformulated so they do not refer to the new, more restricted Proposition 2.4.     

Simultaneous design and planning of supply chains with reverse flows: A generic modelling framework

The increase in societal awareness towards environmental issues has accrued the responsibility of goods producers, which at present came to encompass the entire product life cycle. Recently, the efficient design and operation of supply chains with return flows have, in particular, become a major challenge for many companies, given the high number of factors involved and their intricate interactions.     

MEASURING OPTIMAL CONNECTIONS IN LARGE NETWORKS: A NEW ALGORITHM AND ITS APPLICATIONS

Researchers have identified several problems in measuring the strongest path connecting pairs of actors in valued graphs. To address these problems, it has been proposed that average path value be used to indicate optimal connections between dyads. However, a lack of proper computer algorithm and its implementation has hindered a wide-range application of the proposed solution. In this paper we develop a computer algorithm and fully implement it with four JAVA programs, which are available on request. These programs produce an optimal connection matrix, which is subsequently inputted into UCINET for further multidimensional scaling and clustering analysis. We demonstrate this procedure with a data matrix containing 38 organizations in information technology. We discuss the methodological implications of the application of our algorithm to future social network studies.     

Linear colorings of simplicial complexes and collapsing

A vertex coloring of a simplicial complex Δ is called a linear coloring if it satisfies the property that for every pair of facets (F₁,F₂) of Δ, there exists no pair of vertices (v₁,v₂) with the same color such that v₁∈F₁?F₂ and v₂∈F₂?F₁. The linear chromatic numberlchr(Δ) of Δ is defined as the minimum integer k such that Δ has a linear coloring with k colors. We show that if Δ is a simplicial complex with lchr(Δ)=k, then it has a subcomplex Δ^′ with k vertices such that Δ is simple homotopy equivalent to Δ^′. As a corollary, we obtain that lchr(Δ)?Homdim(Δ)+2. We also show in the case of linearly colored simplicial complexes, the usual assignment of a simplicial complex to a multicomplex has an inverse. Finally, we show that the chromatic number of a simple graph is bounded from above by the linear chromatic number of its neighborhood complex.