On the existence of uncountably many matroidal families

A matroidal family is a set $\text{F}$ ≠ ? of connected finite graphs such that for every finite graph G the edge-sets of those subgraphs of G which are isomorphic to some element of $\text{F}$ are the circuits of a matroid on the edge-set of G. Simões-Pereira [5] shows the existence of four matroidal families and Andreae [1] shows the existence of a countably infinite series of matroidal families. In this paper we show that there exist uncountably many matroidal families. This is done by using an extension of Andreae's theorem, a construction theorem, and certain properties of regular graphs. Moreover we observe that all matroidal families so far known can be obtained in a unified way.     

Rectangular arrays

In this paper we studied m×n arrays with row sums $\text{nr}\text{(n,m)}$ and column sums $\text{mr}\text{(n,m)}$ where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function H_m,n(r), which enumerates m×n arrays with row sums and column sums $\text{nr}\text{(m,n)}$ and $\text{mr}\text{(n,m)}$ respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function G_m,n(y) = Σ_r?0H_m,n(r)y^r, it was found to be rational of degree less than zero. The denominator of G_m,n(y) is of the form (1?y)^(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation.     

Connected matroids with the smallest whitney numbers

In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if _X(G) = Σμ(0, x)λ^{r ? r(x)} = Σ (?1)^{r ? k}W_kλ^k is the characteristic polynomial of G, then

$\text{w}{}_{\mathrm{k}}\text{?}\text{r}\text{k}\text{+n}\text{r?1}\text{k}$

Thus γ(G) ? 2^{r ? 1} (n+2), where γ(G) = Σw_k. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then

$\text{w}{}_{\mathrm{i}}\text{?}\text{r}\text{i}\text{+ n}\text{r}\text{i+1}\text{for i>1; w}{}_1\text{?r+n}\text{r}\text{2}\text{? 1;}$

|μ| ? (r? 1)n; and γ ? (2^{r ? 1} ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, $\text{r(G) = r(}\text{G}\text{?}\text{) = 4}$, and $\text{n(G) = n(}\text{G}\text{?}\text{) = 3}$ then $\text{(w}{}_1\text{(G))}{}^4{}_{\mathrm{t-G}}\text{? (w}{}_1\text{(}\text{G}\text{?}\text{)) = (8, 20, 18, 7, 1)}$. Further, if β is the Crapo invariant,

$\text{β(G)=}\text{d}{}_{\mathrm{X}}\text{(G)}\text{dλ}\text{(1)}\text{,}$

then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network.     

Infinite subgraphs as matroid circuits

A matroidal family $\text{C}$ is defined to be a collection of graphs such that, for any given graph G, the subgraphs of G isomorphic to a graph in $\text{C}$ satisfy the matroid circuit-axioms. Here matroidal families closed under homeomorphism are considered. A theorem of Simöes-Pereira shows that when only finite connected graphs are allowed as members of $\text{C}$, two matroids arise: the cycle matroid and bicircular matroid. Here this theorem is generalized in two directions: the graphs are allowed to be infinite, and they are allowed to be disconnected. In the first case four structures result and in the second case two infinite families of matroids are obtained. The main theorem concerns the structures resulting when both restrictions are relaxed simultaneously.     

Generalizations of magic graphs

A graph is magic if the edges are labeled with distinct nonnegative real numbers such that the sum of the labels incident to each vertex is the same. Given a graph finite G, an Abelian group $\text{g}$, and an element r(v) ∈ $\text{g}$ for every v ∈ V(G), necessary and sufficient conditions are given for the existence of edge labels from $\text{g}$ such that the sum of the labels incident to v is r(v). When there do exist labels, all possible labels are determined. The matroid structure of the labels is investigated when $\text{g}$ is an integral domain, and a dimensional structure results. Characterizations of several classes of graphs are given, namely, zero magic, semi-magic, and trivial magic graphs.     

The number of Hamiltonian circuits

G = 〈V(G), E(G)〉 denotes a directed graph without loops and multiple arrows. $\text{K}$(G) denotes the set of all Hamiltonian circuits of G. Put H(n, r) = max{|E(G)|, |V(G)| = n, 1 ≤ |$\text{K}$(G)| ≤ r}. Theorem: $\text{H(n, 1) = (}\text{n}{}^2\text{2}\text{) + (}\text{n}\text{2}\text{) ?1}$. Further, H(n, 2),…, H(n, 5) are given.     

Arbres avec un nombre maximum de sommets pendants

This article is an attempt to study the following problem: Given a connected graph G, what is the maximum number of vertices of degree 1 of a spanning tree of G? For cubic graphs with n vertices, we prove that this number is bounded by $\text{1}\text{4}\text{n}$ and $\text{1}\text{2}\text{(n ? 2)}$.     

Minimum number of edges in graphs that are both P2- and Pi-connected

A simple graph with n vertices is called P_i-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P₂- and P_i-connected are obtained. Namely if $\text{i?}\text{1}\text{2}\text{(n+1)}$, then |E(G)|?((4i?5)/(2i?2))(n?1), and if $\text{i >}\text{1}\text{2}\text{(n+ 1)}$, then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former.     

On the trace of finite sets

For a family $\text{T}$ of subsets of an n-set X we define the trace of it on a subset Y of X by T_$\text{T}$(Y) = {F∩Y:F?$\text{T}$}. We say that (m,n) → (r,s) if for every $\text{T}$ with |$\text{T| ?m}$ we can find a Y?X|Y| = s such that |T_$\text{T}$(Y)| ? r. We give a unified proof for results of Bollobàs, Bondy, and Sauer concerning this arrow function, and we prove a conjecture of Bondy and Lovász saying $\text{(?}\text{n}{}^2\text{4}\text{? + n + 2,n)→ (3,7)}$, which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle.     

On quasigroups rich in associative triples

Let G be a group and $\text{G(1)}$ a quasigroup on the same underlying set. Let dist($\text{G, G(1)}$) denote the number of pairs (x, y) ?G² such that $\text{xy ≠ x 1 y}$. For a finite quasigroup Q, n = card(Q), let t = dist(Q) = min dist(G, Q), where G runs through all groups with the same underlying set, and s = s(Q) the number of non-associative triples. Then 4tn?2t²?24t?s?4tn. If 1 ? s < 3n²/32, then 3tn < s holds as well. Let n ? 168 be an even integer and let σ = min s(Q), where Q runs through all non-associative quasigroups of order n. Then σ = 16n?64.     

On the analytic continuation of a certain Dirichlet series

A Dirichlet series associated with a positive definite form of degree δ in n variables is defined by

$\text{D}{}_{\mathrm{F}}\text{(s,p,α)}\text{=}\text{∑}\text{α∈Z}{}^{\mathrm{n}}\text{?{0}}\text{F(α)}{}^{\mathrm{?s}}\text{e(ρF(α)+〈α, α〉)}$

where ? ∈ $\text{Q}$, α ∈ $\text{Q}$ⁿ, 〈x, y〉 = x₁y₁ + ? + x_ny_n, e(a) = exp (2πia) for a ∈ $\text{R}$, and s = σ + ti is a complex number. The author proves that: (1) D_F(s, ?, α) has analytic continuation into the whole s-plane, (2) D_F(s, ?, α), ? ≠ 0, is a meromorphic function with at most a simple pole at $\text{s =}\text{n}\text{δ}$. The residue at $\text{s =}\text{n}\text{δ}$ is given explicitly. (3) ? = 0, α ? $\text{Z}$ⁿ, D_F(s, 0, α) is analytic for $\text{α>,}\text{n}\text{(δ ? 1)}$.     

Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.     

Fixing subgraphs and Ulam's conjecture

A spanning subgraph U of a graph G belongs to the set $\text{J}$(G) of fixing subgraphs (see [5]) of G if every embedding of U into G can be extended to an automorphism of G. Clearly G ∈ $\text{J}$(G). G is free if …$\text{J}$(G)… = 1. We establish a connection between Ulam's conjecture and free graphs and continue with an investigation of free graphs.     

On decomposition of r-partite graphs into edge-disjoint hamilton circuits

Let K(n;r) denote the complete r-partite graph K(n, n,…, n). It is shown here that for all even n(r ? 1) ? 2, K(n;r) is the union of $\text{n(r ? 1)}\text{2}$ of its Hamilton circuits which are mutually edge-disjoint, and for all odd n(r ? 1) ? 1, K(n;r) is the union of $\text{(n(r ? 1) ? 1)}\text{2}$ of its Hamilton circuits and a 1-factor, all of which are mutually edge-disjoint.     

On Sperner families in which no K sets have an empty intersection

Let n(r, k) denote the maximal cardinality of Sperner families on a r-element set in which no k ? 3 sets have an empty intersection. Frankl determined n(r, 3) for r sufficiently large. In this paper we prove

$\text{n(r,k)=}\text{r ? 1}\text{[}\text{r ? 1}\text{2}\text{]}$

for k ? 4 and r arbitrary and for k = 3 when r is odd except for 12 values of r. For k = 3 when r? {4, 6, 7} or sufficiently large (e.g. r ? 400)

$\text{n(r,k)=}\text{r ? 1}\text{[}\text{r ? 1}\text{2}\text{]}\text{+ 1}$

is proven. The extremal families are determined also.     

Some tree-star Ramsey Numbers

The Ramsey Number r(G₁, G₂) is the least integer N such that for every graph G with N vertices, either G has the graph G₁ as a subgraph or $\text{G}$, the complement of G, has the graph G₂ as a subgraph.In this paper we embed the paths P_m in a much larger class $\text{T}$ of trees and then show how some evaluations by T. D. Parsons of Ramsey numbers r(P_m, K_1,n), where K_1,n is the star of degree n, are also valid for r(T_m, K_1,n) where T_m ∈ $\text{T}$.     

Third order efficiency of conditional tests for exponential families

Let P_η, η = (θ, γ) ∈ Θ × Γ ? $\text{R}$ × $\text{R}$^k, be a (k + 1)-dimensional exponential family. Let $\text{?}{}_{\mathrm{n}}{}^1$, n ∈ $\text{N}$, be an optimal similar test for the hypothesis {P_(θ,γ)ⁿ: γ ∈ Γ} (θ ∈ Θ fixed) against alternatives P_(θ1,γ1)ⁿ, θ₁ > θ, γ₁ ∈ Γ. It is shown that (?_n¹)_{n∈$\text{N}$} is third order efficient in the class of all test-sequences that are asymptotically similar of level α + o(n^?1) (locally uniformly in the nuisance parameter γ).     

On r-potent linear mappings

Let L(E) be the set of all linear mappings of a vector space E. Let Z₊ be the set of all positive integers. A nonzero element ? in L(E) is called an r-potent if $\text{?}{}^{\mathrm{r}}\text{=?}\text{and}\text{?}{}^{\mathrm{i}}\text{≠?}\text{for}\text{1<i<r (i,r∈Z}{}_{\mathrm{+}}\text{)}$. We prove that $\text{S(E)= {?∈L(E): ?}\text{is singular}\text{}}$ is a semigroup generated by the set of all r-potents in S(E), where r is a fixed positive integer with 2?r?n=dim(E).     

Cogrowth and amenability of discrete groups

Let G be a group and g₁,…, g_t a set of generators. There are approximately (2t ? 1)ⁿ reduced words in g₁,…, g_t, of length ?n. Let $\text{}\text{?}\text{gg}{}_{\mathrm{n}}$ be the number of those which represent 1_G. We show that $\text{γ =}\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{(}\text{}\text{?}\text{gg}{}_{\mathrm{n}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ exists. Clearly 1 ? γ ? 2t ? 1. $\text{η =}\text{(}\text{log}\text{γ)}\text{(}\text{log}\text{(2t ? 1))}$ is the cogrowth. 0 ? η ? 1. In fact $\text{η ∈ {0} ∪ (}\text{1}\text{2}\text{, 1¦}$. The entropic dimension of G is shown to be 1 ? η. It is then proved that d(G) = 1 if and only if G is free on g₁,…, g_t and d(G) = 0 if and only if G is amenable.