Top

2006 | Book

Topics in Discrete Mathematics

Name: Topics in Discrete Mathematics
ISBN: 978-3-540-33698-3

Dedicated to Jarik Nešetřil on the Occasion of his 60th Birthday

Read first chapter

Book Series: Algorithms and Combinatorics

Editors: Martin Klazar, Jan Kratochvíl, Martin Loebl, Jiří Matoušek, Pavel Valtr, Robin Thomas

Publisher: Springer Berlin Heidelberg

Print ISBN: 978-3-540-33698-3

Electronic ISBN: 978-3-540-33700-3

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Get access Table of Contents

About this book

The book offers the readers a collection of high quality papers in selected topics of Discrete Mathematics, to celebrate the 60th birthday of
Professor Jarik Nešetril. Leading experts have contributed survey and research
papers in the areas of Algebraic Combinatorics, Combinatorial
Number Theory, Game theory, Ramsey Theory, Graphs and Hypergraphs,
Homomorphisms, Graph Colorings and Graph Embeddings.

Frontmatter

Algebra, Geometry, Numbers

Frontmatter

Countable Almost Rigid Heyting Algebras

Abstract

For non-trivial Heyting algebras H ₁, H ₂ one always has at least one homomorphism H ₁ →H ₂; if H ₁ = H ₂ there is at least one non-identical one. A Heyting algebra H is almost rigid if ∣ End(H)∣ = 2 and a system of almost rigid algebras ℌ is said to be discrete if ∣ Hom(H ₁, H ₂)∣ = 1 for any two distinct H ₁, H ₂ ∈ ℌ. We show that there exists a discrete system of 2^ω countable almost rigid Heyting algebras.

Michael E. Adams, Aleš Pultr

Piecewise-Bohr Sets of Integers and Combinatorial Number Theory

Abstract

We use ergodic-theoretical tools to study various notions of “large” sets of integers which naturally arise in theory of almost periodic functions, combinatorial number theory, and dynamics. Call a subset of N a Bohr set if it corresponds to an open subset in the Bohr compactification, and a piecewise Bohr set (PWB) if it contains arbitrarily large intervals of a fixed Bohr set. For example, we link the notion of PWB-sets to sets of the form A+B, where A and B are sets of integers having positive upper Banach density and obtain the following sharpening of a recent result of Renling Jin.

Theorem. If A and B are sets of integers having positive upper Banach density, the sum set A+B is PWB-set.

Vitaly Bergelson, Hillel Furstenberg, Benjamin Weiss

A Generalization of Conway Number Games to Multiple Players

Abstract

We define an analogue of the the concept of J. H. Conway’s number games for games of multiple players. We define the value of such number game as an element of a vector space over the Conway field. We interpret the value in terms of the strategy of the game, and prove that all possible values in the vector space can occur.

Christopher Cunningham, Igor Kriz

Two Isoperimetric Problems for Euclidean Simplices

Abstract

Best possible estimates for the lengths of a Hamiltonian path and of a Hamiltonian polygon on a Euclidean simplex of given volume are given. The extreme cases are described.

Miroslav Fiedler

On Finitely Generated Varieties of Distributive Double p-algebras and their Subquasivarieties

Abstract

A quasivariety ℚ is Q-universal if, for any quasivariety \( \mathbb{V} \) of algebraic systems of a finite similarity type, the lattice L(\( \mathbb{V} \)) of all subquasivarieties of \( \mathbb{V} \) is isomorphic to a quotient lattice of a sublattice of the lattice L(ℚ) of all subquasivarieties of ℚ. We investigate Q-universality of finitely generated varieties of distributive double p-algebras. In an earlier paper, we proved that any finitely generated variety of distributive double p-algebras categorically universal modulo a group is also Q-universa1. Here we consider the remaining finitely generated varieties of distributive double p-algebras and state a problem whose solution would complete the description of all Q-universal finitely generated varieties of distributive double p-algebras.

Václav Koubek, Jiří Sichler

The F-triangle of the Generalised Cluster Complex

Abstract

The F-triangle is a refined face count for the generalised cluster complex of Fomin and Reading. We compute the F-triangle explicitly for all irreducible finite root systems. Furthermore, we use these results to partially prove the “F = M Conjecture” of Armstrong which predicts a surprising relation between the F-triangle and the Möbius function of his m-divisible partition poset associated to a finite root system.

Christian Krattenthaler

Ramsey Theory

Frontmatter

Monochromatic Equilateral Right Triangles on the Integer Grid

Abstract

For any coloring of the N × N grid using fewer than log log N colors, one can always find a monochromatic equilateral right triangle, a triangle with vertex coordinates (x, y), (x + d, y), and (x,y + d).

Ron Graham, József Solymosi

One-sided Coverings of Colored Complete Bipartite Graphs

Abstract

Assume that the edges of a complete bipartite graph K(A, B) are colored with r colors. In this paper we study coverings of B by vertex disjoint monochromatic cycles, connected matchings, and connected subgraphs. These problems occur in several applications.

András Gyárfás, Miklós Ruszinkó, Gábor N. Sárközy, Endre Szemerédi

Nonconstant Monochromatic Solutions to Systems of Linear Equations

Abstract

The systems of linear equations (homogeneous or inhomogeneous) that are partition regular, over ℕ or ℤ or ℚ, were characterized by Rado. Our aim here is to characterize those systems for which we can guarantee a nonconstant, or injective, solution. It turns out that we thereby recover an equivalence between ℕ and ℤ that is normally lost when one passes from homogeneous to inhomogeneous systems.

Neil Hindman, Imre Leader

On the Induced Ramsey Number IR(P 3, H)

Abstract

The induced Ramsey number IR(G, H) is the least positive integer N such that there exists an N-vertex graph F with the property that for each 2-coloring of its edges with red and blue, either some induced in F subgraph isomorphic to G has all its edges colored red, or some induced in F subgraph isomorphic to H has all its edges colored blue. In this paper, we study IR(P ₃, H) for various H, where P ₃ is the path with 3 vertices. In particular, we answer a question by Gorgol and Luczak by constructing a family {H _n _n=1 ^∞ such that \( \mathop {lim}\limits_{n \to \infty } \sup \tfrac{{IR(P_3 ,H_n )}} {{IR_w (P_3 ,H_n )}} > 1 \), where IR _w(G, H) is defined almost as IR(G,H), with the only difference that G should be induced only in the red subgraph of F (not in F itself) and H should be induced only in the blue subgraph of F.

Alexandr Kostochka, Naeem Sheikh

On Explicit Ramsey Graphs and Estimates of the Number of Sums and Products

Abstract

We give an explicit construction of a three-coloring of K _N,N in which no K _r,r is monochromatic for r = N ^1/2−ε, where ε > 0 is a constant.

Pavel Pudlák

Graphs and Hypergraphs

Frontmatter

Hereditary Properties of Ordered Graphs

Abstract

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 P is a hereditary property of ordered graphs, then P _n denotes the collection \( \left\{ {G \in \mathcal{P}:V(G) = [n]} \right\} \), and the function \( n \mapsto \left| {\mathcal{P}_n } \right| \) is called the speed of P.

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 F _n, the Fibonacci numbers, and that there exists an infinite sequence of subsequent jumps, from p(n)F _n,k to F _n,k+1 (where p(n) is a polynomial and F _n,k 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.

József Balogh, Béla Bollobás, Robert Morris

A Proof and Generalizations of the Erdős-Ko-Rado Theorem Using the Method of Linearly Independent Polynomials

Abstract

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 X ₁,..., X _m ⊂ [n] are sets such that X _i does not satisfy any of the set of s intersection conditions R _i but X _i satisfies at least one condition in Rj for all j > i then \( m \leqslant \left( {\begin{array}{*{20}c} n \\ s \\ \end{array} } \right) + \left( {\begin{array}{*{20}c} n \\ {s - 1} \\ \end{array} } \right) + \cdot \cdot \cdot + \left( {\begin{array}{*{20}c} n \\ 0 \\ \end{array} } \right) \). 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.

Zoltán Füredi, Kyung-Won Hwang, Paul M. Weichsel

Unions of Perfect Matchings in Cubic Graphs

Abstract

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

Tomáš Kaiser, Daniel Král’, Serguei Norine

Random Graphs from Planar and Other Addable Classes

Abstract

We study various properties of a random graph R _n, drawn uniformly at random from the class \( \mathcal{A}_n \) of all simple graphs on n 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 \( \mathcal{A} \) is’ small’ and ‘addable’, then the probability that R _n 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 \( \mathcal{A} \) is’ smooth’ then we can make much more precise statements for example concerning connectivity.

Colin McDiarmid, Angelika Steger, Dominic J. A. Welsh

Extremal Hypergraph Problems and the Regularity Method

Abstract

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 regularity method for graphs 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 hypergraph regularity method 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.

Brendan Nagle, Vojtěch Rödl, Mathias Schacht

Homomorphisms

Frontmatter

Homomorphisms in Graph Property Testing

Abstract

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

Noga Alon, Asaf Shapira

Counting Graph Homomorphisms

Abstract

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.

Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Katalin Vesztergombi

Efficient Algorithms for Parameterized H-colorings

Abstract

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

Josep Díaz, Maria Serna, Dimitrios M. Thilikos

From Graph Colouring to Constraint Satisfaction: There and Back Again

Abstract

Graph colourings may be viewed as special constraint satisfaction problems. The class of k-colouring problems enjoys a well known dichotomy of complexity — these problems are polynomial time solvable when k ≤ 2, and NP-complete when k ≥ 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.

Pavol Hell

Graph Colorings

Frontmatter

Thresholds for Path Colorings of Planar Graphs

Abstract

A graph is path k-colorable if it has a vertex k-coloring in which the subgraph induced by each color class is a disjoint union of paths. A graph is path k-choosable if, whenever each vertex is assigned a list of k colors, such a coloring exists in which each vertex receives a color from its list.

It is known that every planar graph is path 3-colorable [Poh90, God91] and, in fact, path 3-choosable [Har97]. We investigate which planar graphs are path 2-colorable or path 2-choosable. We seek results of a “threshold” nature: on one side of a threshold, every graph is path 2-choosable, and there is a fast coloring algorithm; on the other side, determining even path 2-colorability is NP-complete.

We first consider maximum degree. We show that every planar graph with maximum degree at most 4 is path 2-choosable, while for k ≥ 5 it is NP-complete to determine whether a planar graph with maximum degree k is path 2-colorable.

Next we consider girth. We show that every planar graph with girth at least 6 is path 2-choosable, while for k ≤ 4 it is NP-complete to determine whether a planar graph with girth k is path 2-colorable. The case of girth 5 remains open.

Glenn G. Chappell, John Gimbel, Chris Hartman

Chromatic Numbers and Homomorphisms of Large Girth Hypergraphs

Abstract

We consider the problem of determining the minimum chromatic number of graphs and hypergraphs of large girth which cannot be mapped under a homomorphism to a specified graph or hypergraph. More generally, we are interested in large girth hypergraphs that do not admit a vertex partition of specified size such that the subhypergraphs induced by the partition blocks have a homomorphism to a given hypergraph. In the process, a general probabilistic construction of large girth hypergraphs is obtained, and general definitions of chromatic number and homomorphisms are considered.

Dwight Duffus, Vojtěch Rödl, Bill Sands, Norbert Sauer

Acyclic 4-Choosability of Planar Graphs Without Cycles of Specific Lengths

Abstract

A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper acyclic coloring c of G such that c(v) ∈ L(v) for all v ∈ V. If G is acyclically L-list colorable for any list assignment with |L(v)| ≥ k for all v ∈ V, then G is acyclically k-choosable.

Let G be a planar graph without 4-cycles and 5-cycles. In this paper, we prove that G is acyclically 4-choosable if G furthermore satisfies one of the following conditions: (1) without 6-cycles; (2) without 7-cycles; (3) without intersecting triangles.

Mickaël Montassier, André Raspaud, Weifan Wang

On the Algorithmic Aspects of Hedetniemi’s Conjecture

Abstract

We present a polynomial algorithm, implicit in the work of El-Zahar and Sauer, which inputs a 3-colouring of a categorical product of two graphs and outputs a 3-colouring of one of the factors. We raise a question about the existence of polynomial algorithms for colouring the vertices of some graphs in terms of intrinsic succint description of the vertices rather than in terms of the (exponential) size of the graph.

Claude Tardif

Recent Developments in Circular Colouring of Graphs

Abstract

The study of circular chromatic number _Xc(G) of a graph G, which is a refinement of its chromatic number, has been very active in the past decade. Many nice results are obtained, new techniques are developed, and connections to other fields are established. This paper presents a glimpse of the recent progress on this subject. Besides presenting the results, some of the ideas and tools in the proofs are explained, although no detailed proofs are contained.

Xuding Zhu

Graph Embeddings

Frontmatter

Regular Embeddings of Multigraphs

Abstract

We prove that the vertex set of any twin-free loopless multigraph G has an embedding into some point set P of some Euclidean space ℝ ^k, such that the automorphism group of G is isomorphic to the isometry group of ℝ ^k globally preserving P.

Hubert de Fraysseix, Patrice Ossona de Mendez

Quadrangulations and 5-critical Graphs on the Projective Plane

Abstract

Let Q be a nonbipartite quadrangulation of the projective plane. Youngs [You96] proved that Q cannot be 3-colored. We prove that for every 4-coloring of Q and for any two colors a and b, the number of faces F of Q, on which all four colors appear and colors a and b are not adjacent on F, is odd. This strengthens previous results that have appeared in [You96, HRS02, Moh02, CT04]. If we form a triangulation of the projective plane by inserting a vertex of degree 4 in every face of Q, we obtain an Eulerian triangulation T of the projective plane whose chromatic number is 5. The above result shows that T is never 5-critical. We show that sometimes one can remove two, three, or four, vertices from T and obtain a 5-critical graph. This gives rise to an explicit construction of 5-critical graphs on the projective plane and yields the first explicit family of 5-critical graphs with arbitrarily large edge-width on a fixed surface.

Bojan Mohar

Crossing Number of Toroidal Graphs

Abstract

It is shown that if a graph of n vertices can be drawn on the torus without edge crossings and the maximum degree of its vertices is at most d, then its planar crossing number cannot exceed cdn, where c is a constant. This bound, conjectured by Brass, cannot be improved, apart from the value of the constant. We strengthen and generalize this result to the case when the graph has a crossing-free drawing on an orientable surface of higher genus and there is no restriction on the degrees of the vertices.

János Pach, Géza Tóth

Regular Maps on a Given Surface: A Survey

Abstract

Regular maps are cellular decompositions of closed surfaces with the highest ‘level of symmetry’, meaning that the automorphism group of the map acts regularly on flags. We survey the state-of-the-art of the problem of classification of regular maps on a given surface and outline directions of future research in this area.

Jozef Širáň

Part VII

Frontmatter

On Six Problems Posed by Jarik Nešetřil

Without Abstract

Jørgen Bang-Jensen, Bruce Reed, Mathias Schacht, Robert Šámal, Bjarne Toft, Uli Wagner

Title: Topics in Discrete Mathematics
Publisher: Springer Berlin Heidelberg
Print ISBN: 978-3-540-33698-3
Electronic ISBN: 978-3-540-33700-3
DOI: https://doi.org/10.1007/3-540-33700-8
Editors:: Martin Klazar
Jan Kratochvíl
Martin Loebl
Jiří Matoušek
Pavel Valtr
Robin Thomas

Premium Partner

Image Credits