Skip to main content
main-content

Über dieses Buch

​This book collects some surveys on current trends in discrete mathematics and discrete geometry. The areas covered include: graph representations, structural graphs theory, extremal graph theory, Ramsey theory and constrained satisfaction problems.

Inhaltsverzeichnis

Frontmatter

Tensors, colours, octahedra

Abstract
Several theorems in combinatorial convexity admit colourful versions. This survey describes old and new applications of two methods that can give such colourful results. One is the octahedral construction, the other is Sarkaria’s tensor method.
Imre Bárány

Cliques and stable sets in undirected graphs

Abstract
The cochromatic number of a graph G is the minimum number of stable sets and cliques of G covering the vertex-set of G. In this paper we survey some resent results and techniques developed in an attempt to answer the question: excluding which induced subgraphs causes a graph to have bounded cochromatic number?
Maria Chudnovsky

A taste of nonstandard methods in combinatorics of numbers

Abstract
By presenting the proofs of a few sample results, we introduce the reader to the use of nonstandard analysis in aspects of combinatorics of numbers.
Mauro Di Nasso

A coding problem for pairs of subsets

Abstract
Let X be an n-element finite set, 0 < kn/2 an integer. Suppose that {A 1, A 2} and {B 1, B 2} are pairs of disjoint k-element subsets of X (that is, ∣A 1∣ = ∣A 2∣ = ∣B 1∣ = B 2∣ = k, A 1A 2 = ∅, B 1B 2 = ∅). Define the distance of these pairs by d({A 1 ∣, A 2},{B 1, B 2}) = min {∣A 1B 1 ∣ + ∣A 2B 2∣, ∣A 1B 2∣+∣A 2B 1∣}. This is the minimum number of elements of A 1A 2 one has to move to obtain the other pair {B 1, B 2}. Let C(n, k, d) be the maximum size of a family of pairs of disjoint k-subsets, such that the distance of any two pairs is at least d.
Here we establish a conjecture of Brightwell and Katona concerning an asymptotic formula for C(n,k, d) for k, d are fixed and n → ∞. Also, we find the exact value of C(n, k, d) in an infinite number of cases, by using special difference sets of integers. Finally, the questions discussed above are put into a more general context and a number of coding theory type problems are proposed.
Béla Bollobás, Zoltán Füredi, Ida Kantor, Gyula O. H. Katona, Imre Leader

String graphs and separators

Abstract
String graphs, that is, intersection graphs of curves in the plane, have been studied since the 1960s. We provide an expository presentation of several results, including very recent ones: some string graphs require an exponential number of crossings in every string representation; exponential number is always sufficient; string graphs have small separators; and the current best bound on the crossing number of a graph in terms of pair-crossing number. For the existence of small separators, the proof includes generally useful results on approximate flow-cut dualities.
Jiří Matoušek

On first-order definable colorings

Abstract
We address the problem of characterizing H-coloring problems that are first-order definable on a fixed class of relational structures. In this context, we give also several characterizations of a homomorphism dualities arising in a class of structures.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Combinatorial applications of the subspace theorem

Abstract
The Subspace Theorem is a powerful tool in number theory. It has appeared in various forms and been adapted and improved over time. Its applications include diophantine approximation, results about integral points on algebraic curves and the construction of transcendental numbers. But its usefulness extends beyond the realms of number theory. Other applications of the Subspace Theorem include linear recurrence sequences and finite automata. In fact, these structures are closely related to each other and the construction of transcendental numbers. The Subspace Theorem also has a number of remarkable combinatorial applications. The purpose of this paper is to give a survey of some of these applications including bounds on unit distances, sum-product estimates and a result about the structure of complex lines. The presentation will be from the point of view of a discrete mathematician. We will state a number of variants and a corollary of the Subspace Theorem and give a proof of a simplified special case of the corollary which is still very useful for many problems in discrete mathematics.
Ryan Schwartz, József Solymosi

Can connected commuting graphs of finite groups have arbitrarily large diameter?

Abstract
We present a two-parameter family, of finite, non-abelian random groups and propose that, for each fixed k, as m → ∞ the commuting graph of G m,k is almost surely connected and of diameter k. As well as being of independent interest, our groups would, if our conjecture is true, provide a large family of counterexamples to the conjecture of Iranmanesh and Jafarzadeh that the commuting graph of a finite group, if connected, must have a bounded diameter.
Peter Hegarty, Dmitry Zhelezov

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise