We enumerate the bases of the bicircular matroid on \(K_{m,n}\). The structure of bases of the bicircular matroid in relation to the bases of the cycle matroid is explored. The techniques herein may enable the enumeration of the bases of bicircular matroids on larger classes of graphs; indeed one of the motivations for this work is to show the extendibility of the techniques recently used to enumerate the bases of the bicircular matroid on \(K_n\).

Motivated by the work of Granville, Moisiadis and Rees, we consider in this paper complementary \(P_3\)-packings of \(K_v\). We prove that a maximum complementary \(P_3\)-packing of \(K_v\) (with \(\lfloor\frac{v}{4} \lfloor \frac{2(v-1)}{3}\rfloor \rfloor P_3s\)) exists for all integers \(v \geq 4\), except for \(v = 9\) and possibly for \(v \in \{24, 27, 30, 33, 36, 39, 42, 57\}\).

It is proved that there is no maximal partial spread of size \(115\) in \(\mathrm{PG}(3,11)\).

In this short note, using the method developed in [10] and [11], we construct a highly symmetrical, non-simple, attractive \(7\)-Venn diagram. This diagram has the minimum number of vertices, \(21\). The only similar two, published in [1] and [11], differ from ours in many ways. One of them was found by computer search [1]. Both of them are “necklace” type Venn diagrams (see [14] for definition), but ours is not.

A graph is a unit interval graph (respectively, an \(\tilde{n}\)-graph) if we can assign to each vertex an open interval of unit length (respectively, a set of \(n\) consecutive integers) so that edges correspond to pairs of intervals (respectively, of sets) that overlap. Sakai [14] and Troxell [18] provide a linear time algorithm to find the smallest integer \(n\) so that a unit interval graph is an \(\mathbb{A}\)-graph, for the particular case of reduced connected graphs with chromatic number \(3\). This work shows how to obtain such smallest \(n\) for arbitrary graphs, by establishing a relationship with the work by Bogart and Stellpflug [1] in the theory of semiorders.

For words of length \(n\), generated by independent geometric random variables, we consider the probability that these words avoid a given consecutive \(3\)-letter pattern. As a consequence, we count permutations in \(S_n\) avoiding consecutive \(3\)-letter patterns.

A mimeomatroid is a matroid union of a matroid with itself. We develop several properties of mimeomatroids, including a generalization of Rado’s theorem, and prove a weakened version of a matroid conjecture by Rota [2].

The well-known Marriage Lemma states that a bipartite regular graph has a perfect matching. We define a bipartite graph \(G\) with bipartition \((X,Y)\) to be semi-regular if both \(x \mapsto\) deg \(x,x \in X\) and \(y \mapsto\) deg \(y, y \in Y\) are constant. The purpose of this note is to show that if \(G\) is bipartite and semi-regular, and if \(|X| < |Y|\), then there is a matching which saturates \(|X|\). (Actually, we prove this for a condition weaker than semi-regular.) As an application, we show that various subgraphs of a hypercube have saturating matchings. We also exhibit classes of bipartite graphs, some of them semi-regular, whose vertices are the vertices of various weights in the hypercube \(Q_n\), but which are not subgraphs of \(Q_n\).

The sum graph of a set \(S\) of positive integers is the graph \(G^+(S)\) having \(S\) as its vertex set, with two vertices adjacent if and only if their sum is in \(S\). A graph \(G\) is called a sum graph if it is isomorphic to the sum graph \(G^+(S)\) of some finite subset \(S\) of \(N\). An integral sum graph is defined just as the sum graph, the difference being that \(S\) is a subset of \(Z\) instead of \(N\). The sum number of a graph \(G\) is defined as the smallest number of isolated vertices when added to \(G\) results in a sum graph. The integral sum number of \(G\) is defined analogously. In this paper, we study some classes of integral sum graphs.

We say that a graph \(F\) strongly arrows \((G,H)\) and write \(F \longmapsto (G,H)\) if for every edge-coloring of \(F\) with colors red and blue, a red \(G\) or a blue \(H\) occurs as an induced subgraph of \(F\). Induced Ramsey numbers are defined by \(r^*(G,H) = \min\{|V(F)| : F \longmapsto (G,H)\}\).
The value of \(r^*(G,H)\) is finite for all graphs, and good upper bounds on induced Ramsey numbers in general, and for particular families of graphs are known. Most of these results, however, use the probabilistic method, and therefore do not yield explicit constructions. This paper provides several constructions for upper bounds on \(r^*(G,H)\), including:\(r^*(C_n) = r^*(C_n,C_n) \leq c^{(logn)^2}\), \(r^*(T,K_n) \leq |T|n^{|T|log|T|}\), \(r^*(B,C_n) \leq |B|^{\lceil log n \rceil +4}\) ,where \(T\) is a tree, \(B\) is bipartite, \(K_n\) is the complete graph on \(n\) vertices, and \(C_n\) is a cycle on \(n\) vertices. We also have some new upper bounds for small graphs: \(r^*(K_3 + e) \leq 21\), and \(r^*(K_4 – e) \leq 46\).