Catálogo de publicaciones - libros

We give an explicit construction of a three-coloring of in which no is monochromatic for = , where ε > 0 is a constant.

An ordered graph is a graph together with a linear order on its vertices. A hereditary property of ordered graphs is a collection of ordered graphs closed under taking order-preserving isomorphisms of the vertex set, and order-preserving induced subgraphs. If is a hereditary property of ordered graphs, then denotes the collection , and the function is called the speed of .

The possible speeds of a hereditary property of labelled graphs have been extensively studied (see [BBW00] and [Bol98] for example), and more recently hereditary properties of other combinatorial structures, such as oriented graphs ([AS00], [BBM06+c]), posets ([BBM06+a], [BGP99]), words ([BB05], [QZ04]) and permutations ([KK03], [MT04]), have also attracted attention. Properties of ordered graphs generalize properties of both labelled graphs and permutations.

In this paper we determine the possible speeds of a hereditary property of ordered graphs, up to the speed 2. In particular, we prove that there exists a jump from polynomial speed to speed , the Fibonacci numbers, and that there exists an infinite sequence of subsequent jumps, from to (where () is a polynomial and are the generalized Fibonacci numbers) converging to 2. Our results generalize a theorem of Kaiser and Klazar [KK03], who proved that the same jumps occur for hereditary properties of permutations.

Our aim is to exhibit a short algebraic proof for the Erdös-Ko-Rado theorem. First, we summarize the method of linearly independent polynomials showing that if ,..., ⊂ [] are sets such that does not satisfy any of the set of intersection conditions but satisfies at least one condition in Rj for all > then . The EKR theorem is follows by carefully choosing the intersection properties and adding extra polynomials. We also prove generalizations for non-uniform families with various intersection conditions.

We show that any cubic bridgeless graph with edges contains two perfect matchings that cover at least 3/5 edges, and three perfect matchings that cover at least 27/35 edges.

We study various properties of a random graph , drawn uniformly at random from the class of all simple graphs on labelled vertices that satisfy some given property, such as being planar or having tree-width at most κ. In particular, we show that if the class is’ small’ and ‘addable’, then the probability that is connected is bounded away from 0 and from 1. As well as connectivity we study the appearances of subgraphs, and thus also vertex degrees and the numbers of automorphisms. We see further that if is’ smooth’ then we can make much more precise statements for example concerning connectivity.

Szemerédi’s regularity lemma asserts that every graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type, yielding the so-called counting lemma for graphs. The combined application of these two lemmas is known as the and has proved useful in graph theory, combinatorial geometry, combinatorial number theory and theoretical computer science.

Recently, the graph regularity method was extended to hypergraphs by Gowers and by Skokan and the authors. The has been successfully employed in a handful of combinatorial applications, including alternative proofs to well-known density theorems of Szemerédi and of Purstenberg and Katznel-son. In this paper, we apply the hypergraph regularity method to a few extremal hypergraph problems of Ramsey and Turán flavor.

Property-testers are fast randomized algorithms for distinguishing between graphs (and other combinatorial structures) satisfying a certain property, from those that are far from satisfying it. In many cases one can design property-testers whose running time is in fact of the size of the input. In this paper we survey some recent results on testing graph properties. A common thread in all the results surveyed is that they rely heavily on the simple yet useful notion of graph homomorphism. We mainly focus on the combinatorial aspects of property-testing.

Counting homomorphisms between graphs (often with weights) comes up in a wide variety of areas, including extremal graph theory, properties of graph products, partition functions in statistical physics and property testing of large graphs.

In this paper we survey recent developments in the study of homomorphism numbers, including the characterization of the homomorphism numbers in terms of the semidefiniteness of “connection matrices”, and some applications of this fact in extremal graph theory.

We define a distance of two graphs in terms of similarity of their global structure, which also reflects the closeness of (appropriately scaled) homomorphism numbers into the two graphs. We use homomorphism numbers to define convergence of a sequence of graphs, and show that a graph sequence is convergent if and only if it is Cauchy in this distance. Every convergent graph sequence has a limit in the form of a symmetric measurable function in two variables. We use these notions of distance and graph limits to give a general theory for parameter testing.

The convergence can also be characterized in terms of mappings of the graphs into fixed small graphs, which is strongly connected to important parameters like ground state energy in statistical physics, and to weighted maximum cut problems in computer science.

We study the fixed parameter tractability of the restrictive -coloring and the restrictive list -coloring problems, introduced in [DST01]. The parameter-izations are defined by fixing the number of pre-images of a subset of the vertices in through a partial weight assignment (). We define two families of partially weighted graphs: the and the . For the class of simple partially weighted graphs, we show the fixed parameter tractability of the list ()-coloring problem. For the more general class of plain partially weighted graphs, we prove the fixed parameter tractability of the ()-coloring problem.

Graph colourings may be viewed as special constraint satisfaction problems. The class of -colouring problems enjoys a well known dichotomy of complexity — these problems are polynomial time solvable when ≤ 2, and NP-complete when ≥ 3. For general constraint satisfaction problems such dichotomy was conjectured by Feder and Vardi, but has still not been proved in full generality. We discuss some results and techniques related to this Dichotomy Conjecture. We focus on the effects of a new concept of ‘fullness’, and how it affects the complexity of constraint satisfaction problems and their dichotomy. Full constraint satisfaction problems may then be specialized back to graph colourings, yielding an interesting novel class of problems in graph theory, related to the study of graph perfection.