On a classification of independence systems

By generalizing matroid axiomatics we provide a framework in which independence systems may be classified. The concept is applied to independence systems arising from well-known combinatorial optimization problems such ask-matroid-intersection-, matchoid-, vertex packingor travelling salesman-problems.     

Lower bounds on the worst-case complexity of some oracle algorithms

To give a proper definition of the complexity of very general computational problems such as optimization problems over arbitrary independence systems or fixed-point problems for continuous functions, it is useful to consider the input for these problems as “oracles” R which can be called by the algorithms for some values x ∈ X and which then give back some information R(x) about x, e.g. whether x belongs to the independence system or the point into which x is mapped by the continuous function. A lower bound on the complexity of an algorithm using an oracle R is the number of calls on R in the worst case. Using this technique it is shown that there is no polynomial approximative algorithm for the maximization problem over a general independence system which has a better worst-case behaviour than the greedy algorithm. Moreover several formalizations of the problem of approximating a fixed point of a continuous function are considered, and it is shown that none of these problems can be solved by a bounded algorithm.     

Bimatroidal independence systems

An independence system Σ=(X, F) is called bimatroidal if there exist two matroidsM=(X F _M) andN=(X, F _N) such thatF=F _M∪ F_N. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This paper initiates the study of bimatroidal systems. Given the collection of circuits of an arbitrary independence system Σ (or, equivalently, the constraints of a set-covering problem), we address the following question: does Σ admit a bimatroidal decomposition {M,N} and, if so, how can we actually produce the circuits ofM andN? We derive a number of results concerning this problem, and we present a polynomial time algorithm to solve it when every two circuits of Σ have at most one common element. We also propose different polynomial time algorithms for set covering problems defined on the circuit-set of bimatroidal systems.     

Independence entropy of \mathbb{Z}^{d}-shift spaces

We introduce a concept of independence entropy for symbolic dynamical systems. This notion of entropy measures the extent to which one can freely insert symbols in positions without violating the constraint defined by the shift space. We show that for a certain class of one-dimensional shift spaces X, the independence entropy coincides with the limiting, as d tends to infinity, topological entropy of the dimensional shift defined by imposing the constraints of X in each of the d cardinal directions. This is of interest because for these shift spaces independence entropy is easy to compute. Thus, while in these cases, the topological entropy of the d-dimensional shift (d≥2) is difficult to compute, the limiting topological entropy is easy to compute. In some cases, we also compute the rate of convergence of the sequence of d-dimensional entropies. This work generalizes earlier work on constrained systems with unconstrained positions.     

Better bases for radial basis function interpolation problems

Radial basis function interpolation involves two stages. The first is fitting, solving a linear system corresponding to the interpolation conditions. The second is evaluation. The systems occurring in fitting problems are often very ill-conditioned. Changing the basis in which the radial basis function space is expressed can greatly improve the conditioning of these systems resulting in improved accuracy, and in the case of iterative methods, improved speed, of solution. The change of basis can also improve the accuracy of evaluation by reducing loss of significance errors. In this paper new bases for the relevant space of approximants, and associated preconditioning schemes are developed which are based on Floater’s mean value coordinates. Positivity results and scale independence results are shown for schemes of a general type. Numerical results show that the given preconditioning scheme usually improves conditioning of polyharmonic spline and multiquadric interpolation problems in R² and R³ by several orders of magnitude. The theory indicates that using the new basis elements (evaluated indirectly) for both fitting and evaluation will reduce loss of significance errors on evaluation. Numerical experiments confirm this showing that such an approach can improve overall accuracy by several significant figures.     

New upper bounds for the independence numbers of graphs with vertices in {−1, 0, 1} n and their applications to problems of the chromatic numbers of distance graphs

Upper bounds for the independence numbers in the graphs with vertices at {?1, 0, 1} ⁿ are improved. Their applications to problems of the chromatic numbers of distance graphs are studied.     

Maximum eccentricity as a union-intersection test statistic in multivariate analysis

Union-intersection is a heuristic method of test construction developed by S. N. Roy. Among the well-known applications of this principle is the test for independence between two sets of variates which leads directly to the concept of canonical correlation. Another multivariate application of considerable importance is the test of internal independence. In this article we consider the structure of a correlation matrix and derive a union-intersection test statistic for internal independence. This statistic will be shown to be a function of the maximum eccentricity of the p-dimensional correlation ellipsoid x′R^?1x = 1. The statistic will be applied to problems in factor analysis and categorical scaling.     

Independence equivalence classes of paths

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. A graph whose independence equivalence class contains only itself, up to isomorphism, is independence unique. Beaton, Brown and Cameron [2] showed that paths with an odd number of vertices are independence unique and raised the problem of finding the independence equivalence class of paths with an even number of vertices. The problem is completely solved in this paper.     

Properly Weighted Independence Systemsand Applications to Scheduling Problems

1.IntroductionIncombinatorialoptimizationthetheoryofindependencesystemsplaysanimportantrole.Oneofthereasonswasthatawiderangeofpracticalproblemscanbeformulatedasthemaximumweightindependentsetproblem(MWIprobleminshort)onanindependencesystem.AmatroidisaspecialindependencesystemwiththecharacterizationthatthegreedyalgorithmcanalwaysworkforthecorrespondingMWIproblemwithanyweightfunction.Thisisafundamentalgreedilysolvablecase11,21.Theothergreedilysolvablecaseshavereceivedstronginterestsinrecentyea…     

Solution du huitième problème de Schneider

The problem we shall now solve is the eighth of Schneider's problems: “Show that at least one of the two numbers e^e, e^e2, must be transcendental.” We shall deduce this result from a theorem of algebraic independence.     

Independence equivalence classes of cycles

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. Beaton, Brown and Cameron (2019) found the independence equivalence classes of even cycles, and raised the problem of finding the independence equivalence class of odd cycles. The problem is completely solved in this paper.     

A U-statistic test in competing risk models

We consider a situation in which systems are subject to failure from competing risks or could be censored from an independent censoring process. A procedure, based on a U-statistic, is proposed for testing the equality of two failure rates in the competing risks set. Under independence assumptions, the asymptotic distribution of the statistic is given and used to construct the test. To cite this article: N. Molinari, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

New systems of generalized quasi-variational inclusions in FC-spaces and applications

In this paper, we study some new systems of generalized quasi-variational inclusion problems in FC-spaces without convexity structure.By applying an existence theorem of maximal elements of set-valued mappings due to the author, some new existence theorems of solutions for the systems of generalized quasi-variational inclusion problems are proved in noncompact FC-spaces. As applications, some existence results of solutions for the system of quasi-optimization problems and mathematical programs with the systems of generalized quasi-variational inclusion constraints are obtained in FC-spaces.     

Rank-axiomatic characterizations of independence systems

Motivated by the rank-axiomatic definitions of a matroid and Woodall's characterization of independence systems [6] we provide an abstract framework for general independence systems in terms of their rank function.     

Linear independence of automatic formal power series

We extend a result of J.-P. Allouche and O. Salon on linear independence of formal power series associated to polynomial extractions of quasistrongly p-additive sequences. The original result was on the F_p-linear independence and we extend it to the F_p[X]-linear independence.     

Independence roots and independence fractals of certain graphs

The independence polynomial of a graph G is the polynomial ∑i _k x ^k , where i _k denote the number of independent sets of cardinality k in G. In this paper, we obtain the relationships between the independence polynomial of path P _n and cycle C _n with Jacobsthal polynomial. We find all roots of Jacobsthal polynomial. As a consequence, the roots of independence polynomial of the family {P _n } and {C _n } are real and dense in $(-\infty,-\frac{1}{4}]$ . Also we investigate the independence fractals or independence attractors of paths, cycles, wheels and certain trees.     

Nonparametric tests of independence between random vectors

A nonparametric test of the mutual independence between many numerical random vectors is proposed. This test is based on a characterization of mutual independence defined from probabilities of half-spaces in a combinatorial formula of Möbius. As such, it is a natural generalization of tests of independence between univariate random variables using the empirical distribution function. If the number of vectors is p and there are n observations, the test is defined from a collection of processes R_n,A, where A is a subset of {1,…,p} of cardinality |A|>1, which are asymptotically independent and Gaussian. Without the assumption that each vector is one-dimensional with a continuous cumulative distribution function, any test of independence cannot be distribution free. The critical values of the proposed test are thus computed with the bootstrap which is shown to be consistent. Another similar test, with the same asymptotic properties, for the serial independence of a multivariate stationary sequence is also proposed. The proposed test works when some or all of the marginal distributions are singular with respect to Lebesgue measure. Moreover, in singular cases described in Section 4, the test inherits useful invariance properties from the general affine invariance property.     

A preference-based approach to spanning trees and shortest paths problems****

Comparison of solutions in combinatorial problems is often based on an additive cost function inducing a complete order on solutions. We investigate here a generalization of the problem, where preferences take the form of a quasi-transitive binary relation defined on the solutions space. We first propose preference-based search algorithms for two classical combinatorial problems, namely the preferred spanning trees problem (a generalization of the minimum spanning tree problem) and the preferred paths problem (a generalization of the shortest path problem). Then, we introduce a very useful axiom for preference relations called independence. Using this axiom, we establish admissibility results concerning our preference-based search algorithms. Finally, we address the problem of dealing with non-independent preference relations and provide different possible solutions for different particular problems (e.g. lower approximation of the set of preferred solutions for multicriteria spanning trees problems, or relaxation of the independence axiom for interval-valued preferred path problems).     

Matricially free random variables

We show that the framework developed by Voiculescu for free random variables can be extended to arrays of random variables whose multiplication imitates matricial multiplication. The associated notion of independence, called matricial freeness, can be viewed as a concept which not only leads to a natural generalization of freeness, but also underlies other fundamental types of noncommutative independence, such as monotone independence and boolean independence. At the same time, the sums of matricially free random variables, called random pseudomatrices, are closely related to random matrices. The main results presented in this paper concern the standard and tracial central limit theorems for random pseudomatrices and the corresponding limit distributions which can be viewed as matricial semicircle laws.