We give an overview of a combinatorial tool that has proved to be successful in attacking optimization problems regarding finite sets of points in the plane. As our main example, we present recent results for the Directions or Slope Problem, where the goal is to minimize the number of slopes determined by the connecting lines of a nontrivial set of points in the plane (not all the points are collinear). In 1982, Ungar completely settled this minimum as conjectured by Scott in 1970: a nontrivial set of n > 3 points in the plane determines at least n -1 directions if n is odd, and at least n directions if n is even. The focus of current research is now on the classification of optimal configurations.

We study the puzzle graphs of hexagonal sliding puzzles of various shapes and with various numbers of holes. The puzzle graph is a combinatorial model which captures the solvability and the complexity of sequential mechanical puzzles. Questions relating to the puzzle graph have been previously studied and resolved for the 15 Puzzle which is the most famous, and unsolvable, square sliding puzzle of all times. The puzzle graph is also a discrete model for the configuration space of hard tiles (hexagons or squares) moving on different tessellation-based domains. Understanding the combinatorics of the puzzle graph leads to understanding some aspects of the topology of these configuration spaces.

Ramsey’s theorem states that for any positive integer t, if n is large enough, then any 2-edge-coloring of K_n contains a monochromatic copy of K_t. Concerning non-monochromatic color-patters, the following is a natural question to ask:  which color patterns (if any) are unavoidable in every  2-edge-coloring of K_n where n is large enough and each color appears in a positive fraction of E(K_n)?  It was conjectured by Bollobás, and shown by Cutler and Montágh, that in such a case the existence of one of two patterns is unavoidable. More precisely, for any positive integer t, if n is large enough,  then any 2-edge coloring of K_n with a positive fraction of E(K_n) in each color class contains a complete graph of order 2t where one color forms either a clique of order t, or two disjoint cliques of order t. In this talk, we will see how unavoidable patterns evolve from the case without restriction in the coloring (given by Ramsey's theorem) to the highest possible restriction.This is a joint work with Yair Caro and Adriana Hansberg.

One of the beautiful theorems in discrete geometry is due to Tverberg, and says that a set with sufficiently many points in R^d can always be partitioned into m parts so that the (m-1) simplex is the (nerve) intersection pattern of the convex hulls of the parts. In this talk we will discuss some generalizations of this Theorem, and some new results on its relations with word representable graphs.

A graph whose edges are colored red and blue is called balanced if half of its edges are red and the other half is blue (±1). We say that a graph G is balanceable if, for n large enough, every balanced complete graph K_n contains a balanced copy of G. Similarly, a graph G is omnitonal if, for n large enough, every balanced K_n contains a copy of G with r red edges and b blue edges for any pair r, b such that r+b = e(G). In this talk, I will present different families of graphs that are balanceable or omnitonal, and I will introduce an interesting Ramsey-Turán problem that emerges from this setting.

A c-partite tournament is the orientation of a complete c-partite graph, the c-partite tournaments with c ≥ 3 form a family of generalized tournaments. A strongly connected tournament is vertex pancyclic, that is, through any vertex pases cycles of any length. This property is not preserved in the family of c-partite tournaments, not even in regular c-partite tournaments.

The problem of determining whether a cycle of length m passes through every vertex, for m < c , has been studied in strongly connected regular and quasi-regular c-partite tournaments.

In 1999 and 2002 Volkmann proposed the following problems:

• How regular should the c-partite tournament be to ensure a c-order subtournament?

• Determine sufficient conditions for every vertex of a strongly connected c-partite tournament to be in an m-cycle for every m ∈ {3,4, ..., c}.

In a  survey from 2007, Volkmann shows how regularity affects properties and structures in multiparty tournaments. The global irregularity is defined as

ig (D) =  max_(x,y ∈V(D)) {max{d+(x),d- (x)}- min{d+ (y) - d-(y) } }

In this talk I am going to give an overview of the results we have obtained for the number of C3-free vertices in 3-partite tournaments, the relationship between global irregularity in a c-partite tournament and pan-cyclicity, the existence of strongly connected c-subtournaments and packings into strongly connected c-tournaments.

Abstract to come.