Independence number,connectivity, and r-factors

We show that if r ? 1 is an odd integer and G is a graph with |V(G)| even such that k(G) ? (r + 1)²/2 and (r + 1)²α(G) ? 4rk(G), then G has an r-factor; if r ? 2 is even and G is a graph with k(G) ? r(r + 2)/2 and (r + 2)α(G) ? 4k(G), then G has an r-factor (where k(G) and α(G) denote the connectivity and the independence number of G, respectively).     

Independence, measure and pseudofinite fields

We give a measure-theoretic refinement of the Independence Theorem in pseudofinite fields.     

Independence,clique size and maximum degree

It was shown before that ifG is a graph of maximum degreep containing no cliques of the sizeq then the independence ratio is greater than or equal to 2 / (p +q). We shall discuss here some extreme cases of this inequality. Dedicated to Paul Erdős on his seventieth birthday     

Independence for full conditional probabilities: Structure,factorization, non-uniqueness,and Bayesian networks

This paper examines concepts of independence for full conditional probabilities; that is, for set-functions that encode conditional probabilities as primary objects, and that allow conditioning on events of probability zero. Full conditional probabilities have been used in economics, in philosophy, in statistics, in artificial intelligence. This paper characterizes the structure of full conditional probabilities under various concepts of independence; limitations of existing concepts are examined with respect to the theory of Bayesian networks. The concept of layer independence (factorization across layers) is introduced; this seems to be the first concept of independence for full conditional probabilities that satisfies the graphoid properties of Symmetry, Redundancy, Decomposition, Weak Union, and Contraction. A theory of Bayesian networks is proposed where full conditional probabilities are encoded using infinitesimals, with a brief discussion of hyperreal full conditional probabilities.     

Independence,irredundance, degrees and chromatic number in graphs

Let β(G) and IR(G) denote the independence number and the upper irredundance number of a graph G. We prove that in any graph of order n, minimum degree δ and maximum degree Δ≠0, IR(G)⩽n/(1+δ/Δ) and IR(G)−β(G)⩽((Δ−2)/2Δ)n. The two bounds are attained by arbitrarily large graphs. The second one proves a conjecture by Rautenbach related to the case Δ=3. When the chromatic number χ of G is less than Δ, it can be improved to IR(G)−β(G)⩽((χ−2)/2χ)n in any non-empty graph of order n⩾2.     

Independence and port oracles for matroids,with an application to computational learning theory

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.Research partially funded by NSF PYI Grant No. DDM-91-96083.Research partially funded by NSF Grant No CCR-92-10957.     

Properly Weighted Independence Systemsand Applications to Scheduling Problems

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

Teaching the Independence of $\bar X$ and $S^2$

---

Teaching the Independence of $\bar X$ and $S^2$

---

     

Mathematics for Independence: From Spanish Liberal Exile to the Young American Republics

This paper studies one period in the history of mathematical relationships between Spain and Latin America, when right after the first liberating movements at the beginning of the 19th century, the Spanish-exiled liberals in London produced a peculiar kind of mathematical textbook for the new republics, the catechisms. Copyright 1999 Academic Press.Este trabajo estudia un periodo de la historia de los intercambios matemáticos entre España y Latinoamérica inmediatamente posterior a los movimientos liberadores de principios del siglo XIX, cuando los liberales españoles exiliados en Londres produjeron un tipo muy peculiar de textos matemáticos para las nuevas repúblicas americanas, los catecismos. Copyright 1999 Academic Press.AMS 1991 subject classifications: 00A05, 01A55, 01A80.     

Hidden Regular Variation, Second Order Regular Variation and Asymptotic Independence

We survey the related asymptotic properties of multivariate distributions; (i) asymptotic independence, (ii) hidden regular variation, and (iii) multivariate second order regular variation. Connections and implications are discussed. The point of view of convergence of measures is emphasized in formulations because we are interested in the concepts being coordinate system free, whenever possible.     

Conditionally Monotone Independence II: Multiplicative Convolutions and Infinite Divisibility

We study the multiplicative convolution for c-monotone independence. This convolution unifies the monotone, Boolean and orthogonal multiplicative convolutions. We characterize convolution semigroups for the c-monotone multiplicative convolution on the unit circle. We also prove that an infinitely divisible distribution can always be embedded in a convolution semigroup. We furthermore discuss the (non)-uniqueness of such embeddings including the monotone case. Finally connections to the multiplicative Boolean convolution are discussed.     

Letter to the Editor: Linear Independence of Time-Frequency Shifts Up To Extreme Dilations

Journal of Fourier Analysis and Applications - Given $$f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)$$ and a finite set $$\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}$$ we demonstrate the linear...     

Thickness-Two Graphs Part Two: More New Nine-Critical Graphs,Independence Ratio,Cloned Planar Graphs,and Singly and Doubly Outerplanar Graphs

There are numerous means for measuring the closeness to planarity of a graph such as crossing number, splitting number, and a variety of thickness parameters. We focus on the classical concept of the thickness of a graph, and we add to earlier work in [4]. In particular, we offer new 9-critical thickness-two graphs on 17, 25, and 33 vertices, all of which provide counterexamples to a conjecture on independence ratio of Albertson; we investigate three classes of graphs, namely singly and doubly outerplanar graphs, and cloned planar graphs. We give a sharp upper bound for the largest chromatic number of the cloned planar graphs, and we give upper and lower bounds for the largest chromatic number of the former two classes.     

独立数与最小度和[a，b]-因子

设G是一个图,a,b是整数且0≤a≤b,G的一个支撑子图F称为一个[a,b]-因子,若对任意的v∈V(G)有a≤dF(v)≤b.在本文中,我们给出了图存在[a,b]-因子涉及到独立数和最小度的一个充分条件,推广了前人的结果.     

Independence Sequences of Well-Covered Graphs: Non-Unimodality and the Roller-Coaster Conjecture

A graph G is well-covered provided each maximal independent set of vertices has the same cardinality. The term s_k of the independence sequence (s₀,s₁,,s) equals the number of independent k-sets of vertices of G. We investigate constraints on the linear orderings of the terms of the independence sequence of well-covered graphs. In particular, we provide a counterexample to the recent unimodality conjecture of Brown, Dilcher, and Nowakowski. We formulate the Roller-Coaster Conjecture to describe the possible linear orderings of terms of the independence sequence. We are grateful to Jason Brown for a helpful discussion in December of 1999 and to Richard Stanley for valuable feedback in August of 2000. The work of the second author was partially supported by the Naval Academy Research Council and ONR grant N0001400WR20041