The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

Equivalence of Room designs. II

The relation of equivalence of Room designs is investigated with respect to the class of Room designs formed from starters with adders in the conventional way. It is shown that, if p^k = 3 + 4t, $\text{s = t ? 2[}\text{t}\text{2}\text{]}$, and $\text{I = (}\text{1}\text{k}\text{) ∑}{}_{\mathrm{<mtext>d</mtext><mtext>k</mtext>}}\text{P}{}^{\mathrm{d}}\text{φ}$ ($\text{k}\text{d}$), then it is possible to construct, without duplication, at least $\text{(I + (?3)}{}^{\mathrm{1–8}}\text{)}\text{8}$ inequivalent patterned Room designs of side p^k. This result implies, for instance, the existence of at least 11 equivalence classes of Room designs of side 87 which contain a patterned Room design; it also implies the existence of at least 5 · 10⁵ equivalence classes of Room designs of side 7⁹ which contain a patterned Room design. Some additional results are obtained.     

Fuzzy topological spaces and fuzzy compactness

It is the purpose of this paper to go somewhat deeper into the structure of fuzzy topological spaces. In doing so we found we had to alter the definition of a fuzzy topology used up to now. We shall also introduce two functors $\text{}\text{?}$gw and $\text{}\text{?}$gi which will allow us to see more clearly the connection between fuzzy topological spaces and topological spaces. Finally we shall introduce the concept of fuzzy compactness as the generalization of compactness in topology. It will be shown in a following publication that contrary to the results obtained up to now, the Tychonoff-product theorem is safeguarded with fuzzy compactness.     

Fast algorithms for generating all maximal independent sets of interval,circular-arc and chordal graphs

In this paper we give fast algorithms for generating all maximal independent sets of three special classes of graphs—interval, circular-arc, and chordal graphs. The worst-case running times of our algorithms are O(n² + β) for interval and circular-arc graphs, and $\text{O((n + e)}{}^1\text{α)}$ for chordal graphs, where n, e, and α are the numbers of vertexes, edges, and maximal independent sets of a graph, and β is the sum of the numbers of vertexes of all maximal independent sets. Our algorithms compare favorably with the fastest known algorithm for general graphs which has a worst-case running time of $\text{O(n}{}^1\text{e}{}^1\text{α)}$.     

A classification theorem for essentially binormal operators

An essentially binormal operator on Hilbert space is an operator which is unitarily equivalent to a 2 × 2 matrix of essentially commuting, essentially normal operators. A natural invariant of essentially binormal operators up to unitary equivalence in the Calkin Algebra is the reducing essential 2 × 2 matricial spectrum. A nonempty compact subset X of the set of 2 × 2 matrices is called hypoconvex, if it is the reducing essential 2 × 2 matricial spectrum of an operator on Hilbert space. The set EN₂(X) is then defined to be the set of all equivalence classes (up to unitary equivalence in the Calkin algebra) of essentially binormal operators whose reducing essential 2 × 2 matricial spectrum coincides with X. The aim of this paper is to prove a result that enables one to compute EN₂(X) in terms of the topological structure of the space $\text{X}\text{?}$ of unitary orbits of X. Indeed, it is shown that for every hypoconvex subset X of the set of 2 × 2 matrices, there exists a natural homomorphism from $\text{Ext}\text{(}\text{X}\text{?}\text{)}$ onto EN₂(X). Also, a six term cyclic exact sequence is obtained, which produces a characterization of the kernel of the above-mentioned homomorphism.     

Fell-Bündel und verallgemeinerte L1-algebren

The relation between cross-sectional algebras of homogeneous Banach-1-algebraic bundles in the sense of Fell [5] and generalized $\text{L}$¹-algebras, as defined in slightly different ways by Leptin [7], Busby and Smith [2], and others, has been studied by Busby in [3]. We give an extension of his result, using a different method for obtaining topological group extensions. Instead of first constructing the abstract group extension from the given factor system and then topologizing it, we work in a natural topological setting and define a topological group which turns out to be the group extension belonging to the given factor system. As a consequence we obtain (without separability assumptions) that for any measurable factor system of a locally compact group with values in some other locally compact group the corresponding abstract group extension can be topologized to give a topological (and hence locally compact) group extension.     

On exotic characteristic classes for spherical fibrations

We define for every so-called admissible relation r in the Steenrod algebra $\text{A}$ and for every oriented spherical fibration ξ over a CW-space an exotic characteristic class (mod 2) ε(r)(ξ), which is primitive and vanishes for sphere bundles. The set of exotic classes associated with the universal spherical fibration and the admissible Adem relations are compared with the algebra generators of H¹(BSG;$\text{Z}$₂) due to Milgram. Moreover, their behaviour under the action of $\text{A}$ is computed. Finally, we give a secondary Wu formula for exotic classes of special Poincaré duality spaces.     

Descriptions of equivalence of O-connectivity

We first study some properties of the subspace, and investigate into the relationship of separation between a fuzzy topological space (fts) and its subspace. Then we obtain the equivalence conditions for O-connectivity. The results on O-connectivity and separation are very similar to those in general topology. Finally we discuss the relationship of connectivity between an O-connected set A in the fts (X, ω ($\text{T}$)) induced by the crisp topological space (X, $\text{T}$) and the crisp set A₀ (=supp A) in (X, $\text{T}$).     

Structure spaces of approximately finite-dimensional C1-algebras

A necessary and sufficient condition for a topological space Y to be the primitive ideal space of an approximately finite dimensional C¹-algebra is proved. The condition is that Y can be obtained from a second countable, totally disconnected, compact Hausdorff space X by equipping X with a topology τ coarser than the original topology and setting Y = (X, τ)/~. ~ is the equivalence relation on X defined by x ~ y iff all sets $\text{o}$ ? τ that contain x also contain y, and conversely. The topology τ must satisfy some additional requirements.     

The automorphisms of convolution algebras of C∞ functions

We find the automorphisms and the spectra of several different topological convolution algebras of C^∞-functions on the real line. Starting with the convolution algebra of compactly supported C^∞-functions, equipped with the usual LF-topology, we define a corresponding convolution algebra of C^∞-functions of arbitrarily fast exponential decay at ∞; and convolution algebras of a given finite degree r of exponential decay at ∞. These algebras may be described topologically as “hyper Schwartz spaces.” With a natural Frechet topology, which we define, they get a structure as locally m-convex algebras. The continuous automorphisms and spectra of these algebras are described completely. We show that the algebra of C^∞-functions of infinitly fast exponential decay at ∞, $\text{H J}$, on the one hand, and the algebra of C^∞-functions of only a finite degree $\text{e}{}^{\mathrm{?r¦x¦}}$ decay at ∞, $\text{J}$_r⁰, on the other hand, have quite different automorphisms, although $\text{H J}$ = ∩_r$\text{J}$_r⁰. As an application, we show that the conformal group is canonically represented as the full group of automorphisms of $\text{J}$_r⁰, and that this representation does not extend to a representation on the Banach algebra L¹($\text{R}$).     

On the number of conjugacy classes in SL(2,Z)

Let $\text{H}\text{(t)}$ be the number of conjugacy classes of elements in SL(2, $\text{L}$) with trace t, and let $\text{h}\text{(n)}$ be the number of equivalence classes of binary quadratic forms with discriminant n. Then for t≠±2, $\text{H}\text{(t)=}\text{h}\text{(t}{}^2\text{?4)}$. For all real θ > 0 there is a T(θ) such that whenever |t|>T(θ), $\text{H}\text{(t)>|t|}{}^{\mathrm{1?\theta }}$. There is a c>0 such that for those t such that t²?4 is squarefree, $\text{H}\text{(t)≤c|t|}$.     

Representation and index theory for C1-algebras generated by commuting isometries

We discuss here representation and Fredholm theory for C¹-algebras generated by commuting isometries. More particularly, for n commuting isometries {V_j: 1 ? j ? n} on separable Hilbert space we give a representation resembling the well-known representation for a single isometry. Our representation permits an analysis of the C¹-algebras $\text{Ol}$=$\text{Ol}$(V_j:1?j?n) generated by the {V_j}. The commutator ideal in $\text{Ol}$ is identified precisely and, under certain additional hypotheses, the Fredholm operators in $\text{Ol}$ are also precisely determined. Finally, we obtain formulas in terms of topological data for the index of Fredholm operators in some interesting algebras of the type $\text{Ol}$(V_j:1?j?n).     

Computing the boxicity of a graph by covering its complement by cointerval graphs

If $\text{F}$ is a family of sets, its intersection graph has the sets in $\text{F}$ as vertices and an edge between two sets if and only if they overlap. This paper investigates the concept of boxicity of a graph G, the smallest n such that G is the intersection graph of boxes in Euclidean n-space. The boxicity, b(G), was introduced by Roberts in 1969 and has since been studied by Cohen, Gabai, and Trotter. The concept has applications to niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. These applications will be described briefly. While the problem of computing boxicity is in general a difficult problem (it is NP-complete), this paper develops techniques for computing boxicity which give useful bounds. They are based on the simple observation that b(G)≤k if and only if there is an edge covering of $\text{G}$ by spanning subgraphs of $\text{G}$, each of which is a cointerval graph, the complement of an interval graph (a graph of boxicity ≤1.).     

Hamiltonicity in (0–1)-polyhedra

The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? $\text{R}$ⁿ is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? $\text{R}$ⁿ has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? $\text{R}$^d having (0–1)-valued vertices such that $\text{G(P) ? G(P′)}$. Some combinatorial consequences of these results are also discussed.     

The asymptotic probability that a random graph is a unit interval graph,indifference graph,or proper interval graph

Let G be a graph on v labelled vertices with E edges, without loops or multiple edges. Let v → ∞ and let E=E(v) be a function of v such that lim $\text{E(v)}\text{v}{}^{\mathrm{<mtext>2</mtext><mtext>3</mtext>}}\text{=c}$. The limit of the probability that a random graph is a unit interval graph, indifference graph or proper interval graph is exp(?$\text{4}\text{3}$c³).     

The behaviour of (k,…,kn,n−ik)ci/i! is asymptotically normal

Let N(n,i) = (k,…,kⁿ,n?ik)c^i/i, i = O.…,[n/k]. We prove that the random variable X_n such that $\text{P(X}{}_{\mathrm{<mtext>n</mtext>}}\text{= i) =}\text{N(n, i)}\text{Σ}{}_{\mathrm{<mtext>j</mtext>}}\text{N(n, j)}$ has asymptotically (n → ∞) a normal distribution and we give some combinatorial applications of this result.We also improve a result of Godsil [3] dealing with matchings in graph.     

L2 multipliers with power weights

Necessary and sufficient conditions are found for a multiplier operator to be bounded on L² of the line with weight |x|^2α. This paper is concerned primarily with the case $\text{α>}\text{1}\text{2}$. Multiplier operators are defined on these spaces by using the usual definition on a subspace that is shown to be dense in the space. The case $\text{α < ?}\text{1}\text{2}$ is treated by duality; $\text{|α| <}\text{1}\text{2}$ is briefly treated using a recent result on fractional integrals. The periodic case is also sketched.