Contraction obstructions for treewidth

We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.     

The structure of obstructions to treewidth and pathwidth

It is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant w can be characterized by a finite obstruction set obs(TW(w)) (resp. obs(PW(w))). These obstruction sets are known for w3 so far. In this paper we give a structural characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with a fixed number of vertices in terms of subgraphs of the complement. Our approach also essentially simplifies known characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with (w+3) vertices.

Also for any w3 a graph from obs(TW(w))obs(PW(w)) is constructed, that solves an open problem.     

Ultrafilters and non-Cantor minimal sets in linearly ordered dynamical systems

It is well known that infinite minimal sets for continuous functions on the interval are Cantor sets; that is, compact zero dimensional metrizable sets without isolated points. On the other hand, it was proved in Alcaraz and Sanchis (Bifurcat Chaos 13:1665–1671, 2003) that infinite minimal sets for continuous functions on connected linearly ordered spaces enjoy the same properties as Cantor sets except that they can fail to be metrizable. However, no examples of such subsets have been known. In this note we construct, in ZFC, non-metrizable infinite pairwise non-homeomorphic minimal sets on compact connected linearly ordered spaces.      

Algorithmic aspects of clique-transversal and clique-independent sets

A minimum clique-transversal set MCT(G) of a graph G=(V,E) is a set SV of minimum cardinality that meets all maximal cliques in G. A maximum clique-independent set MCI(G) of G is a set of maximum number of pairwise vertex-disjoint maximal cliques. We prove that the problem of finding an MCT(G) and an MCI(G) is NP-hard for cocomparability, planar, line and total graphs. As an interesting corollary we obtain that the problem of finding a minimum number of elements of a poset to meet all maximal antichains of the poset remains NP-hard even if the poset has height two, thereby generalizing a result of Duffas et al. (J. Combin. Theory Ser. A 58 (1991) 158–164). We present a polynomial algorithm for the above problems on Helly circular-arc graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms for the weighted version of the clique-transversal problem on strongly chordal graphs, chordal graphs of bounded clique size, and cographs. The algorithms presented run in linear time for strongly chordal graphs and cographs. These mark the first attempts at the weighted version of the problem.     

Separator orders in interval, cocomparability, and AT-free graphs

We introduce a new type of order of sets of vertices. Using this concept, we describe the structure and the relationship between chordal, interval, cocomparability, and asteriodal triple-free graphs.     

Some formal relationships among soft sets,fuzzy sets,and their extensions

We prove that every hesitant fuzzy set on a set E can be considered either a soft set over the universe $[0,1]$ or a soft set over the universe E. Concerning converse relationships, for denumerable universes we prove that any soft set can be considered even a fuzzy set. Relatedly, we demonstrate that every hesitant fuzzy soft set can be identified with a soft set, thus a formal coincidence of both notions is brought to light. Coupled with known relationships, our results prove that interval type-2 fuzzy sets and interval-valued fuzzy sets can be considered as soft sets over the universe $[0,1]$. Altogether we contribute to a more complete understanding of the relationships among various theories that capture vagueness and imprecision.     

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.     

Bregman distances without coercive condition: suns,Chebyshev sets and Klee sets

ABSTRACT

In a real Banach space X, we introduce for a non-empty set C in X the notion of suns in the sense of Bregman distances and show that C is such a sun if and only if C is convex. Also, we give some necessary and sufficient conditions for a compact set to be the Klee set, extending corresponding results on the Euclidean space.     

Improvement sets and vector optimization

In this paper we focus on minimal points in linear spaces and minimal solutions of vector optimization problems, where the preference relation is defined via an improvement set E. To be precise, we extend the notion of E-optimal point due to Chicco et al. in [4] to a general (non-necessarily Pareto) quasi ordered linear space and we study its properties. In particular, we relate the notion of improvement set with other similar concepts of the literature and we characterize it by means of sublevel sets of scalar functions. Moreover, we obtain necessary and sufficient conditions for E-optimal solutions of vector optimization problems through scalarization processes by assuming convexity assumptions and also in the general (nonconvex) case. By applying the obtained results to certain improvement sets we generalize well-known results of the literature referred to efficient, weak efficient and approximate efficient solutions of vector optimization problems.     

On the number of pairwise non-isomorphic minimal blocking sets in PG(2, q)

In this paper we examine whether the number of pairwise non-isomorphic minimal blocking sets in PG(2, q) of a certain size is larger than polynomial. Our main result is that there are more than polynomial pairwise non-isomorphic minimal blocking sets for any size in the intervals [2q−1, 3q−4] for q odd and for q square. We can also prove a similar result for certain values of the intervals and .      

Liouville numbers, Rajchman measures, and small Cantor sets

We show that the set of Liouville numbers carries a positive measure whose Fourier transform vanishes at infinity. The proof is based on a new construction of a Cantor set of Hausdorff dimension zero supporting such a measure.

     

Pairs,sets and sequences in first-order theories

In this paper we study the idea of theories with containers, like sets, pairs, sequences. We provide a modest framework to study such theories. We prove two concrete results. First, we show that first-order theories of finite signature that have functional non-surjective ordered pairing are definitionally equivalent to extensions in the same language of the basic theory of non-surjective ordered pairing. Second, we show that a first-order theory of finite signature is sequential (is a theory of sequences) iff it is definitionally equivalent to an extension in the same language of a system of weak set theory called WS.      

Gaussian kernel based fuzzy rough sets: Model, uncertainty measures and applications

Kernel methods and rough sets are two general pursuits in the domain of machine learning and intelligent systems. Kernel methods map data into a higher dimensional feature space, where the resulting structure of the classification task is linearly separable; while rough sets granulate the universe with the use of relations and employ the induced knowledge granules to approximate arbitrary concepts existing in the problem at hand. Although it seems there is no connection between these two methodologies, both kernel methods and rough sets explicitly or implicitly dwell on relation matrices to represent the structure of sample information. Based on this observation, we combine these methodologies by incorporating Gaussian kernel with fuzzy rough sets and propose a Gaussian kernel approximation based fuzzy rough set model. Fuzzy T-equivalence relations constitute the fundamentals of most fuzzy rough set models. It is proven that fuzzy relations with Gaussian kernel are reflexive, symmetric and transitive. Gaussian kernels are introduced to acquire fuzzy relations between samples described by fuzzy or numeric attributes in order to carry out fuzzy rough data analysis. Moreover, we discuss information entropy to evaluate the kernel matrix and calculate the uncertainty of the approximation. Several functions are constructed for evaluating the significance of features based on kernel approximation and fuzzy entropy. Algorithms for feature ranking and reduction based on the proposed functions are designed. Results of experimental analysis are included to quantify the effectiveness of the proposed methods.     

Nonsingularity of some classes of matrices, and minimal solutions of Silverman''s game on discrete sets

We establish the irreducibility of each game in four infinite three-parameter families of even order Silverman games, and the major step in doing so is to prove that certain matrices A, related in a simple way to the payoff matrices, are nonsingular for all relevant values of the parameters. This nonsingularity is established by, in effect, producing a matrix D such that AD is known to be nonsingular. The elements of D are polynomials from six interrelated sequences of polynomials closely related to the Chebyshev polynomials of the second kind. Each of these sequences satisfies a second order recursion, and consequently has many Fibonacci-like properties, which play an essential role in proving that the product AD is what we claim it is. The matrices D were found experimentally, by discovering patterns in low order cases worked out with the help of some computer algebra systems. The corresponding results for four families of odd order games were reported in an earlier paper.     

Structure and algorithms for (cap,even hole)-free graphs

A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph $G$ has a vertex of degree at most $\frac{3}{2}\omega \left(G\right)?1$, and hence $\chi \left(G\right)\le \frac{3}{2}\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the size of a largest clique in $G$ and $\chi \left(G\right)$ denotes the chromatic number of $G$. We give an $O\left(nm\right)$ algorithm for $q$-coloring these graphs for fixed $q$ and an $O\left(nm\right)$ algorithm for maximum weight stable set, where $n$ is the number of vertices and $m$ is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring.Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs $G$ without clique cutsets have treewidth at most $6\omega \left(G\right)?1$ and clique-width at most 48.     

Entropy, independent sets and antichains: A new approach to Dedekind's problem

For -regular, -vertex bipartite graphs with bipartition , a precise bound is given for the sum over independent sets of the quantity . (In other language, this is bounding the partition function for certain instances of the hard-core model.) This result is then extended to graded partially ordered sets, which in particular provides a simple proof of a well-known bound for Dedekind's Problem given by Kleitman and Markowsky in 1975.

     

Stable sets, corner polyhedra and the Chvátal closure

We consider the edge formulation of the stable set problem. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived from one row of the simplex tableau as fractional Gomory cuts. It follows that the split closure is not stronger than the Chvátal closure for the edge relaxation of the stable set problem.     

Aitken–Neville sets, principal lattices and divided differences

In this paper we study multivariate polynomial interpolation on Aitken–Neville sets by relating them to generalized principal lattices. We express their associated divided differences in terms of spline integrals.