Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2014 | Book

Tensors, colours, octahedra Read chapter Read first chapter

Geometry, Structure and Randomness in Combinatorics

Editors: Jiří Matoušek, Jaroslav Nešetřil, Marco Pellegrini

Publisher: Scuola Normale Superiore

Book Series : CRM Series

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

Login to get access
insite
SEARCH

About this book

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

Table of Contents

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 < k ≤ n/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 1 ∩A 2 = ∅, B 1 ∩ B 2 = ∅). Define the distance of these pairs by d({A 1 ∣, A 2},{B 1, B 2}) = min {∣A 1 − B 1 ∣ + ∣A 2 − B 2∣, ∣A 1 − B 2∣+∣A 2 − B 1∣}. This is the minimum number of elements of A 1 ∪ A 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
Metadata
Title
Geometry, Structure and Randomness in Combinatorics
Editors
Jiří Matoušek
Jaroslav Nešetřil
Marco Pellegrini
Copyright Year
2014
Publisher
Scuola Normale Superiore
Electronic ISBN
978-88-7642-525-7
Print ISBN
978-88-7642-524-0
DOI
https://doi.org/10.1007/978-88-7642-525-7

Premium Partner

    Image Credits