On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

Largest bipartite subgraphs in triangle-free graphs with maximum degree three

Let G be a triangle-free, loopless graph with maximum degree three. We display a polynomial algorithm which returns a bipartite subgraph of G containing at least ? of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3-regular, triangle-free, loopless, connected graphs for which no bipartite subgraph has more than this proportion.     

A matching problem with side conditions

Given a graph G, a 2-matching is an assignment of nonnegative integers to the edges of G such that for each node i of G, the sum of the values on the edges incident with i is at most 2. A triangle-free 2-matching is a 2-matching such that no cycle of size 3 in G has the value 1 assigned to all of its edges. In this paper we describe explicity the convex hull of triangle-free 2-matchings by means of its extreme points and of its facets. We give a polynomially bounded algorithm which maximizes a linear function over the set of triangle-free 2-matchings. Finally we discuss some related problems.     

On Schönhage's algorithm and subquadratic integer gcd computation

We describe a new subquadratic left-to-right GCD algorithm, inspired by Schönhage's algorithm for reduction of binary quadratic forms, and compare it to the first subquadratic GCD algorithm discovered by Knuth and Schönhage, and to the binary recursive GCD algorithm of Stehlé and Zimmermann. The new GCD algorithm runs slightly faster than earlier algorithms, and it is much simpler to implement. The key idea is to use a stop condition for HGCD that is based not on the size of the remainders, but on the size of the next difference. This subtle change is sufficient to eliminate the back-up steps that are necessary in all previous subquadratic left-to-right GCD algorithms. The subquadratic GCD algorithms all have the same asymptotic running time, .

     

Riemann surfaces with longest systole and an improved Voronoï algorithm

In this paper we introduce a new method in order to find the Riemann surface M of a fixed topological type with the longest systole; it is based on a cell decomposition of the Teichmüller space of M. The method also works in the Euclidean case and is similar to the so-called Voronoï algorithm for positive definite quadratic forms, or equivalently, for lattice sphere packings. In particular, we give a new proof of Rogers' theorem.     

Efficient Testing of Large Graphs

Let P be a property of graphs. An e\epsilon -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than en²\epsilon n^2 edges to make it satisfy P. The property P is called testable, if for every e\epsilon there exists an e\epsilon -test for P whose total number of queries is independent of the size of the input graph. Goldreich, Goldwasser and Ron [8] showed that certain individual graph properties, like k-colorability, admit an e\epsilon -test. In this paper we make a first step towards a complete logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type ``"$\forall \exists ' are always testable, while we show that some properties containing this alternation are not.     

Orbifolds and analytic torsions

In this paper, we calculate the behavior of the Quillen metric by orbifold immersions. We thus extend a formula of Bismut-Lebeau to the orbifold case.

R´ESUMÉ. Dans cet article, on calcule le comportement de métrique de Quillen par immersions d'orbifold. On étend ainsi une formule de Bismut-Lebeau au cas d'orbifold.

     

Total Dual Integrality of Matching Forest Constraints

Let G=(V, E, A) be a mixed graph. That is, (V, E) is an undirected graph and (V, A) is a directed graph. A matching forest (introduced by R. Giles) is a subset F of EèAE\cup A such that F contains no circuit (in the underlying undirected graph) and such that for each v ? Vv\in V there is at most one e ? Fe\in F such that v is head of e. (For an undirected edge e, both ends of e are called head of e.) Giles gave a polynomial-time algorithm to find a maximum-weight matching forest, yielding as a by-product a characterization of the inequalities determining the convex hull of the incidence vectors of the matching forests. We prove that these inequalities form a totally dual integral system. It is equivalent to an ``all-integer' min-max relation for the maximum weight of a matching forest. Our proof is based on an exchange property for matching forests, and implies Giles' characterization.     

Small Triangle-Free Configurations of Points and Lines

In the paper we show that all combinatorial triangle-free configurations for v ≤ 18 are geometrically realizable. We also show that there is a unique smallest astral (18₃) triangle-free configuration and its Levi graph is the generalized Petersen graph G(18,5). In addition, we present geometric realizations of the unique flag transitive triangle-free configuration (20₃) and the unique point transitive triangle-free configuration (21₃).     

The Four-in-a-Tree Problem in Triangle-Free Graphs

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n ⁴) whether three given vertices of a graph belong to an induced tree. Here, we study four-in- a-tree for triangle-free graphs. We give a structural answer to the following question: what does a triangle-free graph look like if no induced tree covers four given vertices? Our main result says that any such graph must have the “same structure”, in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete.     

A characterization of triangle-free tolerance graphs

We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).     

On 3-choosability of triangle-free plane graphs

It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in it is adjacent to a 4-or a 5-cycle.This improves some known results in this direction.     

Sur l'ideal d'ordre des operateurs AM-compacts

We give different necessary and sufficient conditions so that the space of AM-compact operators is an order ideal and we deduce some consequences. R´ESUME. Nous donnons différentes conditions nécessaires et suffisantes pour que l'espace des opérateurs AM-compacts soit un idéal d'ordre et nous déduisons quelques conséquences.

     

Almost all triangle-free triple systems are tripartite

A triangle in a triple system is a collection of three edges isomorphic to {123,124,345}. A triple system is triangle-free if it contains no three edges forming a triangle. It is tripartite if it has a vertex partition into three parts such that every edge has exactly one point in each part. It is easy to see that every tripartite triple system is triangle-free. We prove that almost all triangle-free triple systems with vertex set [n] are tripartite. Our proof uses the hypergraph regularity lemma of Frankl and R?dl [13], and a stability theorem for triangle-free triple systems due to Keevash and the second author [15].     

On the equivariant structure of ideals in abelian extensions of local fields (with an appendix by W. Bley)

Let p be an odd rational prime and K a finite extension of \Bbb Q_p {\Bbb Q}_p . We give a complete classification of those finite abelian extensions L/K L/K in which any ideal of the valuation ring of L is free over its associated order in \Bbb Q_p[Gal(L/K)] {\Bbb Q}_p[Gal(L/K)] . In an appendix W. Bley describes an algorithm which can be used to determine the structure of Galois stable ideals in abelian extensions of number fields. The algorithm is applied to give several new and interesting examples.     

How to decrease the diameter of triangle-free graphs

Assume that G is a triangle-free graph. Let be the minimum number of edges one has to add to G to get a graph of diameter at most d which is still triangle-free. It is shown that for connected graphs of order n and of fixed maximum degree. The proof is based on relations of and the clique-cover number of edges of graphs. It is also shown that the maximum value of over (triangle-free) graphs of order n is . The behavior of is different, its maximum value is . We could not decide whether for connected (triangle-free) graphs of order n with a positive ε. Received: October 12, 1997     

Triangle-free graphs with no six-vertex induced path

The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication).     

Lie p-algebras of finite p-subalgebra rank

We say that a Lie p-algebra L has finite p-subalgebra rank if the minimal number of generators required to generate every finitely generated p-subalgebra is uniformly bounded by some integer r. This paper is concerned with the following problem: does L being of finite p-subalgebra rank force ad(L) to be finite-dimensional? Although this seems unlikely in general, we show that this is indeed the case for Lie p-algebras in a large class including all locally, residually, and virtually soluble Lie p-algebras.