On the number of non-isomorphic matroids

Let f(n) denote the number of non-isomorphic matroids on an n-element set. In 1969, Welsh conjectured that, for all non-negative integers m and n, f(m+n)f(m)f(n). In this paper, we prove this conjecture.     

On the number of -equivalent non-isomorphic models

We prove that if is consistent then is consistent with the following statement: There is for every a model of cardinality which is -equivalent to exactly non-isomorphic models of cardinality . In order to get this result we introduce ladder systems and colourings different from the ``standard' counterparts, and prove the following purely combinatorial result: For each prime number and positive integer it is consistent with that there is a ``good' ladder system having exactly pairwise nonequivalent colourings.

     

On the number of unique subgraphs

Entringer and Erdös introduced the concept of a unique subgraph of a given graph G and obtained a lower bound for the maximum number of unique subgraphs in any n-point graph, which we now improve.     

On the number of unique subgraphs of a graph

A question of Entringer and Erdös concerning the number of unique subgraphs of a graph is answered.     

On the number of homogeneous subgraphs of a graph

Let us defineG(n) to be the maximum numberm such that every graph onn vertices contains at leastm homogeneous (i.e. complete or independent) subgraphs. Our main result is exp (0.7214 log² n) ≧G(n) ≧ exp (0.2275 log² n), the main tool is a Ramsey—Turán type theorem. We formulate a conjecture what supports Thomason’s conjecture R(k, k)^1/k = 2.     

On the number of maximal bipartite subgraphs of a graph

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105^n/10 ≈ 1.5926ⁿ; such subgraphs show an upper bound of O(12^n/4) = O(1.8613ⁿ) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005     

On the number of complete subgraphs contained in certain graphs

We count the number of complete graphs of order 4 contained in certain graphs.     

On the maximal number of certain subgraphs inK r -free graphs

Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T ₂(n)), whereT ₂(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK _r -free graphG withn vertices. In particular, in the class of allK _r -free graphs withn vertices the complete balanced (r – 1)-partite graphT _r–1(n) has the largest number of subgraphs isomorphic toK _t (t < r),C ₄,K _2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday     

On graphs with small subgraphs of large chromatic number

Bollobás, Erdös, Simonovits, and Szemerédi conjectured [1] that for each positive constantc there exists a constantg(c) such that ifG is any graph which cannot be made 3-chromatic by the omission ofcn ² edges, thenG contains a 4-chromatic subgraph with at mostg(c) vertices. Here we establish the following generalization which was suggested by Erdös [2]: For each positive constantc and positive integerk there exist positive integersf _k(c) andn _o such that ifG is any graph with more thann _o vertices having the property that the chromatic number ofG cannot be made less thank by the omission of at mostcn ² edges, thenG contains ak-chromatic subgraph with at mostf _k(c) vertices.     

On the number of certain subgraphs contained in graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphsG, H, letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also, forl≧0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We determineN(l, H) precisely for alll≧0 whenH is a disjoint union of two stars, and also whenH is a disjoint union ofr≧3 stars, each of sizes ors+1, wheres≧r. We also determineN(l, H) for sufficiently largel whenH is a disjoint union ofr stars, of sizess ₁≧s ₂≧…≧s _r>r, provided (s ₁−s _r)²<s ₁+s _r−2r. We further show that ifH is a graph withk edges, then the ratioN(l, H)/l ^k tends to a finite limit asl→∞. This limit is non-zero iffH is a disjoint union of stars.     

On the number of connected convex subgraphs of a connected acyclic digraph

A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.     

The number of non-isomorphic models of an unstable first-order theory

It is proved that ifT is an unstable (first-order) theory,λ>|T|+ℵ₀, thenT has exactly 2 ^λ non-isomorphic models of cardinalityλ. In fact we have stronger results: this is true for pseudo-elementary classes, and for almost everyλ≧|T|+ℵ₁. The preparation of this paper was sponsored in part by NSF Grant GP-22937. This work was supported in part by NSF Grant GP-22794.     

On the number of subgraphs of prescribed type of graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For a graphH=〈V(H),E(H)〉 and forS ⊂V(H) defineN(S)={x ∈V(H):xy ∈E(H) for somey ∈S}. Define alsoδ(H)= max {|S| − |N(S)|:S ⊂V(H)},γ(H)=1/2(|V(H)|+δ(H)). For two graphsG, H letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also forl>0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We investigate the asymptotic behaviour ofN(l, H) for fixedH asl tends to infinity. The main results are:Theorem A. For every graph H there are positive constants c ₁, c₂ such that {fx116-1}. Theorem B. If δ(H)=0then {fx116-2},where |AutH|is the number of automorphisms of H. (It turns out thatδ(H)=0 iffH has a spanning subgraph which is a disjoint union of cycles and isolated edges.) This paper forms part of an M.Sc. Thesis written by the author under the supervision of Prof. M. A. Perles from the Hebrew University of Jerusalem.     

On the distance between non-isomorphic groups

A result of Ben-Or, Coppersmith, Luby and Rubinfeld on testing whether a map between two groups is close to a homomorphism implies a tight lower bound on the distance between the multiplication tables of two non-isomorphic groups.     

The number of non-isomorphic models in quasi-varieties of semigroups

Define \( n_K (\lambda )\) tobe eitherω, or the number of non-isomorphic algebras in \(K\) ] having cardinality λ, whichever cardinal is larger. It is proved here that if \(K\) ] is a quasi-variety (universal Horn class) of semigroups, then \(n_K\) is one of four functions. Each of these functions satisfies: \(n_K (\omega ) = \omega\) or \(n_K (\omega ) = 2^\omega\) . If \(n_K (\lambda )< 2^\lambda\) for some infinite λ then \(K\) ] is a residually finitevariety.     

On the number of edges in induced subgraphs of a special distance graph

We obtain new estimates for the number of edges in induced subgraphs of a special distance graph.     

The maximal number of inducedr-partite subgraphs

In this paper, we extend earlier results concerning the maximal number of induced completer-partite graphs in a graphG of ordern. In particular, we show that ift > 1 + logr, then the maximal number of inducedK _r (t)'s is achieved in the case of the Turán graphT _r (n), and that this bound ont is essentially best possible.