Uniqueness and faithfulness of embedding of toroidal graphs

A topological generalization of the uniqueness of duals of 3-connected planar graphs will be obtained. A graph G is uniquely embeddable in a surface F if for any two embeddings $\text{?}{}_1$, $\text{?}{}_2\text{:G → F}$, there are an autohomeomorphism h:F → F and an automorphism σ:G → G such that $\text{h°?}{}_1\text{= ?}{}_2\text{°σ}$. A graph G is faithfully embedabble in a surface F if there is an embedding $\text{?:G → F}$ such that for any automorphism σ:G → G, there is an autohomeomorphism h:F → F with $\text{h°? = f°σ}$. Our main theorems state that any 6-connected toroidal graph is uniquelly embeddable in a torus and that any 6-connected toroidal graph with precisely three exceptions is faithfully embeddable in a torus. The proofs are based on a classification of 6-regular torus graphs.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

Equicontinuity and balanced topological groups

It was proved by V.G. Pestov in 1988 that a locally compact group G is balanced if and only if any countable subset of G is thin in G. This unexpected result was obtained by using a non-elementary transfinite induction involving properties of infinite ordinals. In the present work, this result is reconsidered in a more general context by using an approach which is comparable, in spirit, to Pestov's, but uses a notably simplified technique. Let X be a topological space, Y a uniform space and $\text{H}$ a set of continuous mappings of X into Y. First, new conditions concerning X are given under which $\text{H}$ is equicontinuous provided its countable subsets are. Next, X and Y are supposed equal to a topological group equipped with its right uniform structure, and the set $\text{H}$ taken into account is the group of all its inner automorphisms. We then obtain theorems such as the following which includes, as a special case, Pestov's result: Let G be a topological group; let us suppose that the space G is strongly functionally generated by the set of all its subspaces of countable o-tightness; then G is balanced if and only if any right uniformly discrete countable subset of G is thin in G. As an application, it is proved that if G satisfies the above hypothesis and is non-Archimedean, then G is balanced if and only if G is strongly functionally balanced.     

Unbounded derivations tangential to compact groups of automorphisms,II

Let G be a compact abelian group, and τ an action of G on a C¹-algebra $\text{U}$, such that $\text{U}$^τ(γ)$\text{U}$^τ(γ)¹ = $\text{U}$^τ(0) $\text{U}$^τ for all $\text{γ ?}\text{G}\text{?}$, where $\text{U}$^τ(γ) is the spectral subspace of $\text{U}$ corresponding to the character γ on G. Derivations δ which are defined on the algebra $\text{U}$_F of G-finite elements are considered. In the special case δ¦_{$\text{U}$^τ} = 0 these derivations are characterized by a cocycle on $\text{G}\text{?}$ with values in the relative commutant of $\text{U}$^τ in the multiplier algebra of $\text{U}$, and these derivations are inner if and only if the cocycles are coboundaries and bounded if and only if the cocycles are bounded. Under various restrictions on G and τ properties of the cocycle are deduced which again give characterizations of δ in terms of decompositions into generators of one-parameter subgroups of τ(G) and approximately inner derivations. Finally, a perturbation technique is devised to reduce the case δ($\text{U}$_F) ? $\text{U}$_F to the case δ($\text{U}$_F) ? $\text{U}$_F and δ¦_{$\text{U}$^τ} = 0. This is used to show that any derivation δ with D(δ) = $\text{U}$_F is wellbehaved and, if furthermore G = T¹ and δ($\text{U}$_F) ? $\text{U}$_F the closure of δ generates a one-parameter group of ¹-automorphisms of $\text{U}$. In the case G = T^d, d = 2, 3,… (finite), and δ($\text{U}$_F) ? $\text{U}$_F it is shown that δ extends to a generator of a group of ¹-automorphisms of the σ-weak closure of $\text{U}$ in any G-covariant representation.     

Spectra of ergodic transformations

We study the group properties of the spectrum of a strongly continuous unitary representation of a locally compact Abelian group G implementing an ergodic group of ¹-automorphisms of a von Neumann algebra $\text{R}$. It is shown that in many cases the spectrum equals the dual group of G; e.g. if G is the integers and $\text{R}$ not finite dimensional and Abelian, then the spectrum is the circle group.     

On a general class of graph polynomials

Let $\text{F}$ be a family of connected graphs. With each element α ∈ $\text{F}$, we can associate a weight w_α. Let G be a graph. An F-cover of G is a spanning subgraph of G in which every component belongs to $\text{F}$. With every F-cover we can associate a monomial π(C) = Π_αw_α, where the product is taken over all components of the cover. The F-polynomial of G is Σπ(C), where the sum is taken over all F-covers in G. We obtain general results for the complete graph and complete bipartite graphs, and we show that many of the well-known graph polynomials are special cases of more general F-polynomials.     

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.).     

Représentations de Gelfand–Graev pour les groupes réductifs non connexesGelfand–Graev representations for non connected reductive groups

Let G be a connected reductive group defined over $\text{F}{}_{\mathrm{q}}$ and let F be the corresponding Frobenius endomorphism. Let σ be a quasi-central rational automorphism of G. We define in this article Gelfand–Graev representations of the group $\text{G}{}^{\mathrm{F}}\text{=G}{}^{\mathrm{F}}\text{.〈σ〉}$ when σ is unipotent and when it is semi-simple. We show that they have similar properties to Gelfand–Graev representations of the group G^F. To cite this article: K Sorlin, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 179–184.     

Balancing signed graphs

A signed graph based on F is an ordinary graph F with each edge marked as positive or negative. Such a graph is called balanced if each of its cycles includes an even number of negative edges. Psychologists are sometimes interested in the smallest number d=d(G) such that a signed graph G may be converted into a balanced graph by changing the signs of d edges. We investigate the number D(F) defined as the largest d(G) such that G is a signed graph based on F. We prove that $\text{1}\text{2}\text{m?}\text{nm}\text{≤D(F)≤}\text{1}\text{2}\text{m}$ for every graph F with n vertices and m edges. If F is the complete bipartite graph with t vertices in each part, then $\text{D(F)≤}\text{1}\text{2}\text{t}{}^2\text{?ct}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}$ for some positive constant c.     

First countability, tightness, and other cardinal invariants in remainders of topological groups

We consider the following natural questions: when a topological group G has a first countable remainder, when G has a remainder of countable tightness? This leads to some further questions on the properties of remainders of topological groups. Let G be a topological group. The following facts are established. 1. If Gω has a first countable remainder, then either G is metrizable, or G is locally compact. 2. If G has a countable network and a first countable remainder, then either G is separable and metrizable, or G is σ-compact. 3. Under (MA+¬CH) every topological group with a countable network and a first countable remainder is separable and metrizable. Some new open problems are formulated.     

Compact G-Fuzzy topological spaces

Considering complete Boolean algebras $\text{G}$ as sets of truth values a new concept of compactness—so-called probabilistic compactness — is introduced to $\text{G}$-fuzzy topological spaces. The aim of this paper is to show that the most important theorems of the theory of ordinary compact spaces remain true; e.g. probabilistic compactness is preserved under projective limits, every probabilistic compact space has an unique $\text{G}$-fuzzy uniformity being compatible with the underlying $\text{G}$-fuzzy topology, etc. Finally using the selection theorem due to Kuratowski and Ryll-Nardzewski a non-trivial example of a probabilistic compact space is given.     

Minimal codes in abelian group algebras

In this paper we show that two minimal codes $\text{M}$₁ and $\text{M}$₂ in the group algebra $\text{F}$₂[G] have the same (Hamming) weight distribution if and only if there exists an automorphism θ of G whose linear extension to $\text{F}$₂[G] maps $\text{M}$₁ onto $\text{M}$₂. If θ(M₁) = M₂, then $\text{M}$₁ and $\text{M}$₂ are called equivalent. We also show that there are exactly τ(l) inequivalent minimal codes in $\text{F}$₂[G], where ? is the exponent of G, and τ(?) is the number of divisors of ?.     

Automorphisms and holomorphic differentials in characteristic p

Let G be a group of automorphisms of a function field F of genus g_F over an algebraically closed field K. The space $\text{Ω}{}_{\mathrm{F}}$ of holomorphic differentials of F is a g_F^? dimensional K-space. In response to a query of Hecke, Chevalley and Weil (Abh. Math. Sem. Univ. Hamburg, 10 (1934), 358–361) completely determined the structure of $\text{Ω}{}_{\mathrm{F}}$ as representation space for G in the classical case. They carried out the proof for the special case in which F is unramified over the fixed field of G. The case of cyclic ramified extensions had been previously considered by Hurwitz (Math. Ann., 41 (1893), 37–45). Weil (Abh. Math. Sem. Univ. Hamburg, 11 (1935), 110–115) gave a proof in the general case. The treatment in the last two papers is analytical. In characteristic p, the problem is open. If G is cyclic and F is unramified over the fixed field E of G, Tamagawa (Proc. Japan Acad., 27 (1951), 548–551) proved that the representation is the direct sum of one identity representation of degree 1 and g_E ? 1 regular representations. The principal object of this paper is an extension of Tamagawa's result to arbitrary cyclic extensions of p-power degree. The number of times an indecomposable representation of given degree occurs in the representation of G on $\text{Ω}{}_{\mathrm{F}}$ is explicitly determined in terms of g_E and the Witt vector characterizing the extension $\text{F}\text{E}$. The paper also contains a purely algebraic proof of the result of Chevalley and Weil for arbitrary cyclic extensions of degree relatively prime to p. Using character theory, it can be extended to arbitrary groups of order relatively prime to the characteristic.     

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.     

Diophantine problems in variables restricted to the values 0 and 1

Let $\text{F}$x₁,…,x_s be a form of degree d with integer coefficients. How large must s be to ensure that the congruence $\text{F}$(x₁,…,x_s) ≡ 0 (mod m) has a nontrivial solution in integers 0 or 1? More generally, if $\text{F}$ has coefficients in a finite additive group G, how large must s be in order that the equation $\text{F}$(x₁,…,x_s) = 0 has a solution of this type? We deal with these questions as well as related problems in the group of integers modulo 1 and in the group of reals.     

Caractères des groupes de Lie

Let G be a real Lie group with Lie algebra $\text{G}$. M. Duflo has constructed irreducible unitary representations of G associated to some G-orbits Ω in the dual $\text{G}$¹ of $\text{G}$. We prove a character formula when Ω is tempered, closed, and of maximal dimension.     

Convex polyhedra of doubly stochastic matrices: II. Graph of Ωn

Properties of the graph $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ of the polytope $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices are studied. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is not a k-dimensional rectangular parallelotope for k ≥ 2, then G($\text{F}$) is Hamilton connected. Prime factor decompositions of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ relative to Cartesian product are investigated. In particular, if $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then the number of prime graphs in any prime factor decomposition of G($\text{F}$) equals the number of connected components of the neighborhood of any vertex of G($\text{F}$). Distance properties of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ are obtained. Faces $\text{F}$ of $\text{Ω}{}_{\mathrm{n}}$ for which G($\text{F}$) is a clique of $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ are investigated.     

A note on realizing homomorphisms of category algebras

The complete Boolean homomorphisms from the category algebra $\text{C}$(X) of a complete matrix space X to the category algebra $\text{C}$(Y) of a Baire topological space Y are characterized as those σ-homomorphisms which are induced by continuous maps from dense G₈-subsets of Y into X. This result is used to deduce a series of related results in topology and measure theory (some of which are well-known). Finally a similar result for the complete Boolean homomorphisms from the category algebra $\text{C}$(X) of a compact Hausdorff space X tothe category algebra $\text{C}$(Y) of a Baire topological space Y is proved.