On maximal t-linearly independent sets

Consider a finite t + r ? 1 dimensional projective space PG(t + r ? 1, s) over a Galois field GF(s) of order s = ?^h, where ? and h are positive integers and ? is the prime characteristic of the field. A collection of k points in PG (t + r ? 1, s) constitutes an L(t, k)-set if no t of them are linearly dependent. An L(t, k)-set is maximal if there exists no other L(t, k′)-set with k′ > k. The largest k for which an L(t, k)-set exists is denoted by M_t(t + r, s). K. A. Bush [3] established that M_t(t, s) = t + 1 for t ? s. The purpose of this paper is to generalize this result and study M_t(t + r, s) for t, r, and s in certain relationships.     

Maximal sets of points in finite projective space,no t-linearly dependent

Consider a finite (t + r ? 1)-dimensional projective space PG(t + r ? 1, s) based on the Galois field GF(s), where s is prime or power of a prime. A set of k distinct points in PG(t + r ? 1, s), no t-linearly dependent, is called a (k, t)-set and such a set is said to be maximal if it is not contained in any other (k¹, t)-set with $\text{k}{}^1\text{> k}$. The number of points in a maximal (k, t)-set with the largest k is denoted by m_t(t + r, s). Our purpose in the paper is to investigate the conditions under which two or more points can be adjoined to the basic set of E_i, i = 1, 2, …, t + r, where E_i is a point with one in i-th position and zeros elsewhere. The problem has several applications in the theory of fractionally replicated designs and information theory.     

On cross t-intersecting families of sets

For all p, t with 0<p<0.11 and 1?t?1/(2p), there exists n₀ such that for all n, k with n>n₀ and k/n=p the following holds: if A and B are k-uniform families on n vertices, and |A∩B|?t holds for all A∈A and B∈B, then .     

On characterization of maximal independent sets via quadratic optimization

This article investigates the local maxima properties of a box-constrained quadratic optimization formulation of the maximum independent set problem in graphs. Theoretical results characterizing binary local maxima in terms of certain induced subgraphs of the given graph are developed. We also consider relations between continuous local maxima of the quadratic formulation and binary local maxima in the Hamming distance-1 and distance-2 neighborhoods. These results are then used to develop an efficient local search algorithm that provides considerable speed-up over a typical local search algorithm for the binary Hamming distance-2 neighborhood.     

On maximal independent sets of vertices in claw-free graphs

A graph is claw-free if: whenever three (distinct) vertices are joined to a single vertex, those three vertices are a nonindependent (nonstable) set. Given a finite claw-free graph with real numbers (weights) assigned to the vertices, we exhibit an algorithm for producing an independent set of vertices of maximum total weight. This algorithm is “efficient” in the sense of J. Edmonds, that is to say, the number of computational steps required is of polynomial (not exponential or factorial) order in n, the number of vertices of the graph. This problem was solved earlier by Edmonds for the special case of “edge-graphs”; our solution is by reducing the more general problem to the earlier-solved special case. Separate attention is given to the case in which all weights are (+1) and thus an independent set is sought which is maximal in the sense of its cardinality.     

On the sum of cardinalities of extremum maximal independent sets

Upper bounds are established for the sum of the smallest and largest cardinalities of maximal independent sets in simple undirected graphs with p vertices and minimum degree k, for the cases k = 1, 2 and $\text{k ?}\text{1}\text{2}\text{p}$.     

Polar graphs and maximal independent sets

We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1,2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1,1)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (α,β)-polar graphs and study the computational complexity of the problems on polar graphs of special types.     

A finiteness theorem for maximal independent sets

Denote bymi(G) the number of maximal independent sets ofG. This paper studies the setS(k) of all graphsG withmi(G) = k and without isolated vertices (exceptG K ₁) or duplicated vertices. We determineS(1), S(2), andS(3) and prove that |V(G)| 2 ^k–1 +k – 2 for anyG inS(k) andk 2; consequently,S(k) is finite for anyk. Supported in part by the National Science Council under grant NSC 83-0208-M009-050     

Greedy maximal independent sets via local limits

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree.     

Probabilistic analysis of a parallel algorithm for finding maximal independent sets

We consider a natural parallel version of the classical greedy algorithm for finding a maximal independent set in a graph. This version was studied in Coppersmith, Raghavan, and Tompa and they conjecture there that its expected running time on random graphs of arbitrary edge density of O (log n). We prove that conjecture.     

The number of maximal independent sets in connected graphs

Generalizing a theorem of Moon and Moser, we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50.     

A construction of maximal linearly independent array

Let M be a subset of r-dimensional vector space Vτ （F2） over a finite field F2, consisting of n nonzero vectors, such that every t vectors of M are linearly independent over F2. Then M is called （n, t）-linearly independent array of length n over Vτ（F2）. The （n, t）-linearly independent array M that has the maximal number of elements is called the maximal （r, t）-linearly independent array, and the maximal number is denoted by M（r, t）. It is an interesting combinatorial structure, which has many applications in cryptography and coding theory. It can be used to construct orthogonal arrays, strong partial balanced designs. It can also be used to design good linear codes, In this paper, we construct a class of maximal （r, t）-linearly independent arrays of length r ＋ 2, and provide some enumerator theorems.     

Large sets of t-designs through partitionable sets: A survey

The method of partitionable sets for constructing large sets of t-designs have now been used for nearly a decade. The method has resulted in some powerful recursive constructions and also existence results especially for large sets of prime sizes. Perhaps the main feature of the approach is its simplicity. In this paper, we describe the approach and show how it is employed to obtain some of the recursive theorems. We also review the existence results and recursive constructions which have been found by this method.     

Enumerating maximal independent sets with applications to graph colouring

We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph.     

Construction of translation planes from t-spread sets

A t-spread set [1] is a set $\text{C}$ of (t + 1) × (t + 1) matrices over GF(q) such that ∥C∥ = q^t+1, 0 ? C, I?C, and det(X ? Y) ≠ 0 if X and Y are distinct elements of $\text{C}$. The amount of computation involved in constructing t-spread sets is considerable, and the following construction technique reduces somewhat this computation. Construction: Let $\text{G}$ be a subgroup of GL(t + 1, q), (the non-singular (t + 1) × (t + 1) matrices over GF(q)), such that ∥G∥|a^t+1, and det (G ? H) ≠ 0 if G and H are distinct elements of $\text{G}$. Let A₁, A₂, …, A_n?GL(t + 1, q) such that det(A_i ? G) ≠ 0 for i = 1, …, n and all G?G, and det(A_i ? A_jG) ≠ 0 for i > j and all G?G. Let $\text{C = \&{0\&} ∪ G ∪ A}{}_1\text{G ∪ … ∪ A}{}_{\mathrm{n}}\text{G}$, and ∥C∥ = q^t+1. Then $\text{C}$ is a t-spread set. A t-spread set can be used to define a left V ? W system over V(t + 1, q) as follows: x + y is the vector sum; let e?V(t + 1, q), then xoy = yM(x) where M(x) is the unique element of $\text{C}$ with x = eM(x). Theorem: Let$\text{C}$be a t-spread set and F the associatedV ? Wsystem; the left nucleus = {y | CM(y) = C}, and the middle nucleus = }y | M(y)C = C}. Theorem: For$\text{C}$constructed as aboveG ? {M(x) | x?N_λ}. This construction technique has been applied to construct a V ? W system of order 25 with ∥N_λ∥ = 6, and ∥N_μ∥ = 4. This system coordinatizes a new projective plane.     

Graphs with the second largest number of maximal independent sets

Let G be a simple undirected graph. Denote by (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of among all graphs of order n and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.     

Constraints on the number of maximal independent sets in graphs

A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. Let i(G) denote the number of maximal independent sets of G. Here, we prove two conjectures, suggested by P. Erdös, that the maximum number of maximal independent sets among all graphs of order n in a family Φ is o(3^n/3) if Φ is either a family of connected graphs such that the largest value of maximum degrees among all graphs of order n in Φ is o(n) or a family of graphs such that the approaches infinity as n → ∞.     

Trees with the second largest number of maximal independent sets

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all trees and forests of order n≥4. We also characterize those extremal graphs achieving these values.     

On scrambled sets and a theorem of Kuratowski on independent sets

The measure of scrambled sets of interval self-maps was studied by many authors, including Smítal, Misiurewicz, Bruckner and Hu, and Xiong and Yang. In this note, first we introduce the notion of ``-chaos" which is related to chaos in the sense of Li-Yorke, and we prove a general theorem which is an improvement of a theorem of Kuratowski on independent sets. Second, we apply the result to scrambled sets of higher dimensional cases. In particular, we show that if a map of the unit -cube is -chaotic on , then for any there is a map such that and are topologically conjugate, and has a scrambled set which has Lebesgue measure 1, and hence if , then there is a homeomorphism with a scrambled set satisfying that is an -set in and has Lebesgue measure 1.