Bounding the number of bases of a matroid

Letb(M) andc(M), respectively, be the number of bases and circuits of a matroidM. For any given minor closed class? of matroids, the following two questions, are investigated in this paper. (1) When is there a polynomial functionp(x) such thatb(M)≤p(c(m)|E(M)|) for every matroidM in?? (2) When is there a polynomial functionp(x) such thatb(M)≤p(|E(M)|) for every matroidM in?? Let us denote byM _Mn the direct sum ofn copies ofU _1,2. We prove that the answer to the first question is affirmative if and only if someM _Mn is not in?. Furthermore, if all the members of? are representable over a fixed finite field, then we prove that the answer to the second question is affirmative if and only if, also, someM _Mn is not in?.     

The maximum number of q-cliques in a graph with no p-clique

Let $\text{?(n, p, q)}$ be the maximum possible number of q-cliques among all graphs on n nodes with no p-clique. Turán, in 1941, determined $\text{?(n, p, 2)}$ for all n and p. For each n and p, he found the unique graph which attains this maximum. In this paper we determine $\text{?(n, p, q)}$ for all values of n, p and q. We show that, except for the trivial case 1 ? n < q, Turán's graph is the unique graph which attains the maximum $\text{?(n, p, q)}$ for all q such that 1 < q < p.     

On the chromatic number of an oriented matroid

We prove that the chromatic number of an oriented matroid of rank r3 is at most r+1 with equality if and only if is the oriented matroid of an orientation of K_r+1, the complete graph on r+1 vertices.     

The number of lines in Frege proofs with substitution

We prove that for sufficiently large , there are tautologies of size that require proofs containing lines in axiomatic systems of propositional logic based on the rules of substitution and detachment. Received October 19, 1995     

The number of lines determined by a polygon

Given a polygon P in the Euclidean plane, what can be said about the number of lines in the plane which contain at least one edge of P? If P has n edges, it is easy to see that at most n lines contain an edge of P. Further, any convex polygon with n edges provides an example of such a situation. The question of interest here is what is the smallest number of lines, each containing one or more edges, which may be determined by a polygon with n edges? This number is not n and in fact does not even grow like some constant, of necessity less than one, times n. Rather, it grows like √2n. We are actually able to determine this minimum exactly for most values of n and to within one for all values of n.     

On cubature with a minimal number of lines

In this paper we introduce the study of the approximation of integrals on regions of a space of dimension higher than one, by means of linear combinations of integrals on manifolds of lower dimension contained in the region of integration.This approximation arises as an alternative and/or a complement to the formulae developed first by Mysovskikh and which have knots as data.We define the notion of Gaussian formulae and we characterize the minimal representation for this approximation.     

The optimal base of a matroid/with tree-type constraints

Let M be a matroid defined on a weighted finite set E=(e_1,…,e_n).l(e) is the weight of e∈E.P (X_1,…,X_m) is a set of subsets of E.X_i,X_j∈P,if X_i∩X_j≠(the empty set),then either X_i X_j or X_jX_i.For each X_i∈P,there are two associate nonnegative integers a_i and b_i with o_i≤b_i≤|X_i|.We call a base T of M a feasible base with respect to P(or simply call it a feasible base of M),if X_i∈P,a_i≤|X_i∩T|≤b_i.A base T' is called optimal if:i) This feasible,In this paper we present a polynomial algorithm to solve the optimal base problem.     

Packing of arborescences with matroid constraints via matroid intersection

Mathematical Programming - Edmonds’ arborescence packing theorem characterizes directed graphs that have arc-disjoint spanning arborescences in terms of connectivity. Later he also observed a...     

The basis monomial ring of a matroid

We define the basis monomial ring M_G of a matroid G and prove that it is Cohen-Macaulay for finite G. We then compute the Krull dimension of M_G, which is the rank over Q of the basis-point incidence matrix of G, and prove that dim B_G ≥ dim M_G under a certain hypothesis on coordinatizability of G, where B_G is the bracket ring of G.     

The number of cubic surfaces with 27 lines over a finite field

Journal of Algebraic Combinatorics - We study those multiplicative subgroups of $${\mathbb F}_{2^n}^*$$ which are Sidon sets and/or sum-free sets in the group $$({\mathbb F}_{2^n},+)$$ . These...     

The intersection of a matroid and a simplicial complex

A classical theorem of Edmonds provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a ``covering" parameter. We generalize this theorem, replacing one of the matroids by a general simplicial complex. One application is a solution of the case of a matroidal version of Ryser's conjecture. Another is an upper bound on the minimal number of sets belonging to the intersection of two matroids, needed to cover their common ground set. This, in turn, is used to derive a weakened version of a conjecture of Rota. Bounds are also found on the dual parameter--the maximal number of disjoint sets, all spanning in each of two given matroids. We study in detail the case in which the complex is the complex of independent sets of a graph, and prove generalizations of known results on ``independent systems of representatives" (which are the special case in which the matroid is a partition matroid). In particular, we define a notion of -matroidal colorability of a graph, and prove a fractional version of a conjecture, that every graph is -matroidally colorable.

The methods used are mostly topological.

     

The solution to a matroid problem of Knuth

In this note we answer a question posed by Knuth in his recent paper “Random matroids”.     

Complementary bases of a matroid

Let e₁, e′₁, e₂, e′₂, …, e_n, e′_n be the elements of matroid M. Suppose that {e₁, e₂, …;, e_n} is a base of M and that every circuit of M contains at least m + 1 elements. We prove that there exist at least 2^m bases, called complementary bases, of M with the property that only one of each complementary pair e_j, e′_j is contained in any base.We also prove an analogous result for the case where E is partitioned into E₁, E₂, …, E_n and the initial base contains |E_j| ? 1 elements from partition E_j.