Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

The sweet mystery of compatibilism

Any satisfactory account of freedom must capture, or at least permit, the mysteriousness of freedom—a “sweet” mystery involving a certain kind of ignorance rather than a “sour” mystery of unintelligibility, incoherence, or unjustifiedness. I argue that compatibilism can capture the sweet mystery of freedom. I argue first that an action is free if and only if a certain “rationality constraint” is satisfied, and that nothing in standard libertarian accounts of freedom entails its satisfaction. Satisfaction of this constraint is consistent with the universal causal predetermination of action (UCP). If UCP is true and the rationality constraint satisfied, there’s a sense in which our actions are explanatorily (though not necessarily causally) overdetermined. While it seems plausible (given UCP) that our actions are so overdetermined, it seems utterly mysterious why they should be so overdetermined. Compatibilism’s capacity to accommodate this mystery is a mark in its favor.     

Two Remarks Concerning Balanced Matroids

The property of balance (in the sense of Feder and Mihail) is investigated in the context of paving matroids. The following examples are exhibited: (a) a class of “sparse” paving matroids that are balanced, but at the same time rich enough combinatorially to permit the encoding of hard counting problems; and (b) a paving matroid that is not balanced. The computational significance of (a) is the following. As a consequence of balance, there is an efficient algorithm for approximating the number of bases of a sparse paving matroid within specified relative error. On the other hand, determining the number of bases exactly is likely to be computationally intractable. * The work described here was supported by the grant “Sharper analysis of randomised algorithms” from the UK Engineering and Physical Sciences Research Council.     

Towards a new theory of confirmation

Any sequence of events can be “explained” by any of an infinite number of hypotheses. Popper describes the “logic of discovery” as a process of choosing from a hierarchy of hypotheses the first hypothesis which is not at variance with the observed facts. Blum and Blum formalized these hierarchies of hypotheses as hierarchies of infinite binary sequences and imposed on them certain decidability conditions. In this paper we also consider hierarchies of infinite binary sequences but we impose only the most elementary Bayesian considerations. We use the structure of such hierarchies to define “confirmation”. We then suggest a definition of probability based on the amount of confirmation a particular hypothesis (i.e. pattern) has received. We show that hypothesis confirmation alone is a sound basis for determining probabilities and in particular that Carnap’s logical and empirical criteria for determining probabilities are consequences of the confirmation criterion in appropriate limiting cases.     

Construction of pseudorandom binary lattices by using the multiplicative inverse

In an earlier work Hubert and the authors of this paper introduced and studied the notion of pseudorandomness of binary lattices. Later in another paper the authors gave a construction for a large family of “good” binary lattices by using the quadratic characters of finite fields. Here, a further large family of “good” binary lattices is constructed by using finite fields and the notion of multiplicative inverse.     

Logical analysis of numerical data

“Logical analysis of data” (LAD) is a methodology developed since the late eighties, aimed at discovering hidden structural information in data sets. LAD was originally developed for analyzing binary data by using the theory of partially defined Boolean functions. An extension of LAD for the analysis of numerical data sets is achieved through the process of “binarization” consisting in the replacement of each numerical variable by binary “indicator” variables, each showing whether the value of the original variable is above or below a certain level. Binarization was successfully applied to the analysis of a variety of real life data sets. This paper develops the theoretical foundations of the binarization process studying the combinatorial optimization problems related to the minimization of the number of binary variables. To provide an algorithmic framework for the practical solution of such problems, we construct compact linear integer programming formulations of them. We develop polynomial time algorithms for some of these minimization problems, and prove NP-hardness of others. The authors gratefully acknowledge the partial support by the Office of Naval Research (grants N00014-92-J1375 and N00014-92-J4083).     

A desarguesian theorem for algebraic combinatorial geometries

The points of an algebraic combinatorial geometry are equivalence classes of transcendentals over a fieldk; two transcendentals represent the same point when they are algebraically dependent overk. The points of an algebraically closed field of transcendence degree two (three) overk are the lines (resp. planes) of the geometry. We give a necessary and sufficient condition for two coplanar lines to meet in a point (Theorem 1) and prove the converse of Desargues’ theorem for these geometries (Theorem 2). A corollary: the “non-Desargues” matroid is non-algebraic. The proofs depend on five properties (or postulates). The fifth of these is a deep property first proved by Ingleton and Main [3] in their paper showing that the Vámos matroid is non-algebraic.     

On minors of non-binary matroids

No binary matroid has a minor isomorphic toU ₄ ² , the “four-point line”, and Tutte showed that, conversely, every non-binary matroid has aU ₄ ² minor. However, more can be said about the element sets ofU ₄ ² minors and their distribution. Bixby characterized those elements which are inU ₄ ² minors; a matroidM has aU ₄ ² minor using elementx if and only if the connected component ofM containingx is non-binary. We give a similar (but more complicated) characterization for pairs of elements. In particular, we prove that for every two elements of a 3-connected non-binary matroid, there is aU ₄ ² minor using them both.     

Recent developments in algebraic combinatorics

We survey three recent developments in algebraic combinatorics. The first is the theory of cluster algebras and the Laurent phenomenon of Sergey Fomin and Andrei Zelevinsky. The second is the construction of toric Schur functions and their application to computing three-point Gromov-Witten invariants, by Alexander Postnikov. The third development is the construction of intersection cohomology for nonrational fans by Paul Bressler and Valery Lunts and its application by Kalle Karu to the torich-vector of a nonrational polytope. We also briefly discuss the “half hard Lefschetz theorem” of Ed Swartz and its application to matroid complexes. Partially supported by NSF grant #DMS-9988459.     

Hyper-rectangular space partitioning trees: A practical approach

Summary  The process of computation of classification trees can be characterized as involving three basic choices: the type of splits considered in the growing process, the criterion to be optimized at each step of the process, and the way to get right-sized trees. Most implementations are ordinary binary trees, i.e. trees whose successive cuts are made by hyper-planes perpendicular to the axes. L. Devroye, L. Gy?rfy and G. Lugosi (1996) define and consider the remarkable theoretical properties of a binary tree classifier whose prominent feature is the particular type of splits used in its construction: at a given node, partitioning is made by hyper-rectangles rather than hyper-planes. We propose an approximation of the solution for the complex optimization problem involved to allow insights on the practical advantages of those trees. Then we compare the performance of our algorithm with some leading algorithms for ordinary binary trees, namely CART and C4.5 as implemented in the Splus “tree” procedure and in SAS’s Enterprise Miner respectively. Research support from “Projet d’Actions de Recherche Concertées” (No. 98/03-217) and from the “Interuniversity Attraction Pole”, Phase V (No. P5/24) from the Belgian Government are also acknowledged.     

Coordinatizing R-trees in terms of universal c-trees

A complete ℝ-treeT will be constructed such that, for everyxσT, the cardinality of the set of connected components ofT{x} is the same and equals a pre-given cardinalityc; by this construction simultaneously the valuated matroid of the ends of this ℝ-tree is given. In addition, for any arbitrary ℝ-tree, an embedding into such a “universalc-tree” (for suitablec) will be constructed.     

Lebesgue numbers and Atsuji spaces in subsystems of second-order arithmetic

We study Lebesgue and Atsuji spaces within subsystems of second order arithmetic. The former spaces are those such that every open covering has a Lebesgue number, while the latter are those such that every continuous function defined on them is uniformly continuous. The main results we obtain are the following: the statement “every compact space is Lebesgue” is equivalent to ; the statements “every perfect Lebesgue space is compact” and “every perfect Atsuji space is compact” are equivalent to ; the statement “every Lebesgue space is Atsuji” is provable in ; the statement “every Atsuji space is Lebesgue” is provable in . We also prove that the statement “the distance from a closed set is a continuous function” is equivalent to . Received: February 2, 1996     

Polytime,combinatory logic and positive safe induction

 We characterize the polynomial time operations as those which are provably total in a first order system, which comprises (untyped) combinatory logic with extensionality, together with positive “safe induction” on the set of binary strings. The formalization of safe induction is inspired by Leivants idea of ramification. We also show how to replace ramification by means of modal logic. Received: 14 June 2000 / Published online: 20 December 2001     

Numerical simulation of sheath plasma by the particle method taking account of coulomb collisions

We study the problem of the behavior of a plasma bounded longitudinally by an absorbing sheath. This model contains charged particles (electrons and ions) moving subject to a self-consistent electrostatic field. New particle pairs are generated in the region of a distributed source. As a numerical model we used the electrostatic “particle-in-cell” method supplemented by the Emmert model for a bulk source and the algorithm of binary Coulomb collisions using the Monte Carlo method. We give a mathematical statement of the problem. The computations were carried out using the direct implicit method with the “explicit limit” time step. The results of numerical simulation of this system are given. We consider the formation and evoluiton of potential structures (multiple weak nonmonotonic double layers). Five figures. Bibliography: 35 titles. Translated fromProblemy Matematicheskoi Fiziki, 1998, pp. 75–89.     

The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.     

Construction of large families of pseudorandom binary sequences

Oon constructed large families of finite binary sequences with strong pseudorandom properties by using Dirichlet characters of large order. In this paper Oon’s construction is generalized and extended. We prove that in our construction the well-distribution and correlation measures are as “small” as in the case of the Legendre symbol.      

Remarks on a principle of localization

We prove that the Brauer class of a crossed product is a sum of symbols iff its “local” components are. Analogously we show that a solution of the “Goldie rank conjecture” would follow from the “local” statements; an extension of a result of Cliff-Sehgal is an easy corollary.     

On the interaction of δ-shocks and contact vacuum states

We study the pressureless gas equations, with piecewise constant initial data. In the immediate solution, δ-shocks and contact vacuum states arise and even meet (interact) eventually. A solution beyond the “interaction” is constructed. It shows that the δ-shock will continue with the velocity it attained instantaneously before the time of interaction, and similarly, the contact vacuum state will move past the δ-shock with a velocity value prior to the interaction. We call this the “no-effect-from-interaction” solution. We prove that this solution satisfies a family of convex entropies (in the Lax’s sense). Next, we construct an infinitely large family of weak solutions to the “interaction”. Suppose further that any of these solutions satisfy a convex entropy, it is necessary and suffcient that these solutions reduce to only the “no-effect-from-interaction” solution. In [1], Bouchut constructed another entropy satisfying solution. As with other previous papers, it is obvious that it will not be sufficient that a “correct” solution satisfies a convex entropy, in a non-strictly hyperbolic conservation laws system.     

Stability analysis for several second-order Sigma—Delta methods of coarse quantization of bandlimited functions

We investigate the stability and robustness properties of a family of algorithms used to “coarsely quantize” bandlimited functions. The algorithms we will consider are one-bit second-orderΣΔA-quantization schemes and some modified versions of these. We prove that there exists a bounded region that remains positively invariant under the two-dimensional piecewise-affine discrete dynamical system associated with each of these quantizers. Moreover, this bounded region can be constructed so that it is robust under small changes in the quantizer. We also show some interesting properties of the resulting binary sequences.