A conglomerate of exponential supercategories of the category of finitely generated topological spaces

Summary For every ordinaln > 1 we define a categoryT _n of topological spaces in ech's sense which is isomorphic to a category ofn-ary monorelational systems. We show that every categoryT _n is an exponential supercategory of the categoryB of finitely generated topological spaces, which means that well-behaved function spacesG ^H can be defined inT _n wheneverG B.     

Smallest maximal snakes of translates of convex domains

LetK be a convex domain. A maximal snake of sizen is a set of non-overlapping translatesK ₁, ...,K _N ofK, whereK _i touchesK _j if and only if |i –j|=1 and no translate ofK can touchK ₁ orK _n without intersecting an additionalK _i ,i=1, ...,n. The size of the smallest maximal snake is proved to be 11 ifK is a parallelogram and to be 10 otherwise.     

Matrix semigroups—generators and relations

Some presentations for the semigroups of all 2×2 matrices and all 2×2 matrices of determinant 0 or 1 over the field GF(p) (p prime) are given. In particular, if <a, b, c‖ R> is any (semigroup) presentation for the general linear group in terms of generators $$A = \left( {\begin{array}{*{20}c} 1 & 0 \\ 1 & 1 \\ \end{array} } \right),B = \left( {\begin{array}{*{20}c} 1 & 1 \\ 0 & 1 \\ \end{array} } \right),C = \left( {\begin{array}{*{20}c} 1 & 0 \\ 0 & \xi \\ \end{array} } \right),$$ where ζ is a primitive root of 1 modulop, then the presentation $$\langle a,b,c,t|R,t^2 = ct = tc = t,tba^{p - 1} t = 0,b^{\xi - 1} atb = a^{\xi - 1} tb^\xi a^{1 - \xi - 1} \rangle $$ defines the semigroup of all 2×2 matrices over GF (2,p) in terms of generatorsA, B, C and $$T = \left( {\begin{array}{*{20}c} 1 & 0 \\ 0 & 0 \\ \end{array} } \right).$$ Generating sets and ranks of various matrix semigroups are also found.     

A note on packing paths in planar graphs

Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths.Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Seb (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.Research partially supported by the Hungarian National Foundation for Scientific Research Grants OTKA 2118 and 4271.     

Tight upper bounds for the discrepancy of half-spaces

We show that the discrepancy of anyn-point setP in the Euclideand-space with respect to half-spaces is bounded byC _d n ^1/2−1/2d , that is, a mapping χ:P→{−1,1} exists such that, for any half-space γ, γ, |Σ _p∈P⋂γ χ(p)|≤C _d n ^1/2-1/2d . In fact, the result holds for arbitrary set systems as long as theprimal shatter function isO(m ^d ). This matches known lower bounds, improving previous upper bounds by a factor. Part of this research was done at the Third Israeli Computational Geometry Workshop in Ramot and during a visit at Tel Aviv University in December 1993. Also supported in part by Charles University Grant No. 351 and Czech Republic Grant GAČR 201/93/2167.     

Lines of curvature near umbilical points on surfaces immersed in R4

LetM be a compact orientable surface,I:M R⁴ an immersion of classC ^r and a normal unitary smooth vector field. We prove that in the space of pairs (I, ) the family of pairs all whose umbilical points are Darbouxian is generic.     

The Dold-Lashof-Fuchs construction revisited

Sia dato uno spazio topologicoE con azione di un monoide topologicoH e siaE→B una funzione continue che, su ogni apertoU di una partizione dell'unità diB, sia, a meno di omotopia, la proiezioneU×H→U (ovvero una fibrazione numerabile). Un classico risultato di A. Dold e R. Lashof (1959) permette di costruire, a partire daE→B, una funzione continuaE _∞→B_∞, conE _∞ debolmente contraibile e munito di azione diH: laH-fibrazione universale associata daH. Tale funzione, in generale, non è purtroppo numerabile e quindi non si presta alla classificazione delleH-fibrazioni numerabili. Successivamente (1971), M. Fuchs ha trovato un modo di modificare la costruzione di Dold-Lashof per recuperare la numerabilità. La costruzione di Dold-Lashof-Fuchs è, da allora, uno dei principali strumenti nella teoria degli spazi classificanti di monoidi topologici, anche se vi è un uso di topologie alquanto complesse e quindi poco maneggevoli. In questo lavoro ci proponiamo di mostrare come, lavorando nella categoria conveniente deik-spazi, sia possibile descrivere la costruzione di Dold-Lashof-Fuchs in modo estremamente semplificato ed adattarla anche alla classificazione delleF-fibrazioni numerabili.

---

Conferenza tenuta da R. Piccinini il 15 maggio 1995     

Kneser-type oscillation criteria for self-adjoint two-term differential equations

It is proved that the even-order equationy ⁽²ⁿ⁾ +p(t)y=0 is (n,n) oscillatory at if

On the capacity of boolean graph formulæ

In a recent paper we have solved several well-known combinatorial problems treating them as special cases of our generalization of Shannon's notion of graph capacity. We present a new simple formalism to deal with all such problems in a unified manner, considering graphs or families of graphs as special formulæ the variables of which are pairs of vertices of their common vertex sets. In all of these problems, the maximum size of a set ofn-length sequences from a fixed alphabet is to be determined under various restrictions on the element pairs present in the same coordinate of any two sequences from the set. For sufficiently homogeneous formulæ capacity becomes computable.New applications include generalizations of our result on the maximum number of pairwise qualitatively independentk-partitions of ann-set from independence to various forms of qualitative dependence.Work partially supported by the Italian Ministry of the University and Scientific Research, Project: Algoritmi, Modelli di Calcolo e Strutture Informative.     

Spectra of graphs and fractal dimensions II

This paper continues the study of exponentsd(x), d (x), d _R (x) andd (x) for graphG; and the nearest neighbor random walk {X _n } _nN onG, if the starting pointX ₀=x is fixed. These exponents are responsible for the geometric, resistance, diffusion and spectral properties of the graph. The main concern of this paper is the relation of these exponents to the spectral density of the transition matrix. A series of new exponentse, e ,e _R ,e are introduced by allowingx to vary along the vertices. The results suggest that the geometric and resistance properties of the graph are responsible for the diffusion speed on the graph.