graph distances, paths and other ideas …

The graph geodesics is a shortest path between two graph vertices of a graph. There may be more than one different shortest paths, all of the same length. Graph geodesics may be found using an existing famous algorithms such as: breadth-first traversal or Dijkstra’s algorithm.

The graph distance between two vertices denoted with is the length of the shortest, or minimal, path between them. (The notion of distance applies only to connected components of graphs see figure 1).

The graph diameter of a graph is the longest distance you can find in the graph. It is a measure of the length of the longest minimal path. (A path is not minimal if the two vertices at its endpoints could be connected by a shorter path). So the length of the maximum geodesic in a given graph is called the graph diameter, and the length of the minimum geodesic is called the graph radius.

The diameter of a graph stands the same way in Euclidean geometry (where the diameter of the circle is the largest distance inside a circle between any two points). Consider now the graph radius as the distance from the center to the outer edge. We can stretch and bend this concept into that of the radius of a graph.

The eccentricity of a vertex is the length of the longest minimal path from that vertex to some vertex in the graph. You can think of the eccentricity of a vertex as the longest distance in the graph from there to somewhere (see figure 2).

The graph center of a graph is the collection of vertices (called the central vertices) whose eccentricity is least. In other words, it’s the collection of vertices whose longest distance to all other vertices is the smallest.

The graph radius of a graph is the length of the shortest eccentricity in the graph. It’s the eccentricity of each central vertex.

Now the inspiration problem of the day is from an old russian graph theory problem that askes:

Problem: Given n points can one build n-1 roads, so that each road joins two points, the shortest distance between any two points along the roads belongs to {1, 2, 3, … , n(n-1)/2 }, and given any element of {1, 2, 3, … , n(n-1)/2 } one can find two points such that the shortest distance between them along the roads is that element? a) for n=6, b) for n=1986.

a beetle trapped … (for Katerina :-))

(Infinite pigeonhole principle) Given an infinite set of objects, if they are arranged in a finite number of places, there is at least one place with an infinite number of objects.

PROBLEM:

A 100 × 100 board is divided into unit squares. In every square there is an arrow that points up, down, left or right. The board square is surrounded by a wall, except for the right side of the top right corner square. A beetle is placed in one of the squares. Each second, the insect moves one unit in the direction of the arrow in its square. When the beetle moves, the arrow of the square it was in moves 90 degrees clockwise. If the indicated movement cannot be done, the beetle does not move that second, but the arrow in its squares does move. Is it possible that the beetle never leaves the board?

this is nice ” yeah, yeah, yeah” as the Beatles sing …

Problem:

small insects move inside a unit square. Prove that it is always possible to find of them that are inside a circle of radius

 

another nice easy one from combinatorics geometry. If any reader likes a clue I would be glad to give one…

Problem:

23 friends want to play soccer. For this they choose a referee and the others split into two teams of 11 persons each. They want to do this so that the total weight of each team is the same. We know that they all have integer weights and that, regardless of who is the referee, it is possible to make the two teams. Prove that they all have the same weight.

over invariants again. It seems they are the only (mathematical) problems that I’m interested in, now days 😛 …

Coloring problem’s

I recently came across Sperner’s Lemma. Again. Sperner’s lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. A fast description goes like this: Take a triangle RGB (R red, G green, B blue) labelled counterclockwise, and subdivide it into smaller triangles in whatever way you like (see the picture below). Then label all the new vertices as follows:

• vertices along RG may be labelled either R or G, but not B
• vertices along BC may be labelled either G or B, but not R
• vertices along CA may be labelled either B or R, but not G
• vertices inside triangle ABC may be labelled R or G or B.

Now shade in every small triangle in the subdivision that has three different labels.
Use two different shadings to distinguish the triangles which have been labelled counterclockwise (i.e. in the same sense as triangle RGB) from the triangles which have been labelled clockwise (i.e. in the sense opposite to that of as triangle RGB).

Then there will be exactly one more counterclockwise triangle than clockwise triangles. In particular, the number of shaded triangles will be odd.

For a nice proof and more details take a look here

So two problems I tried that have to do with coloring and combinatorics:

Problem 1: (All Russian Math Olympiad 1980) Some unit squares in an infinite sheet of squared paper are colored red so that every 2 x 3 and 3 x 2 rectangle contains exactly two red squares. How many red squares are there in a 9 x 11 rectangle?

Problem 2: (JBO 2004)  Consider a convex polygon having vertices, We arbitrarily decompose the polygon into triangles having all the vertices among the vertices of the polygon, such that no two of the triangles have interior points in common. We paint in black the triangles that have two sides that are also sides of the polygon, in red if only one side of the triangle is also a side of the polygon and in white those triangles that have no sides that are sides of the polygon.

Prove that there are two more black triangles that white ones.

a brouwer theorem problem

Brouwer’s fixed point theorem is a fixed point theorem in topology, named after Luitzen Brouwer. It states that for any continuous function f with certain properties there is a point x₀ such that f(x₀) = x₀. The simplest form of Brouwer’s theorem is for continuous functions f from a disk D to itself. A more general form is for continuous functions from a convex compact subset K of Euclidean space to itself.

Among hundreds of fixed point theorems,^[1] Brouwer’s is particularly well known, due in part to its use across numerous fields of mathematics. In its original field, this result is one of the key theorems characterizing the topology of Euclidean spaces, along with the Jordan curve theorem, the hairy ball theorem or the Borsuk–Ulam theorem.^[2] This gives it a place among the fundamental theorems of topology.^[3] The theorem is also used for proving deep results about differential equations and is covered in most introductory courses on differential geometry. It appears in unlikely fields such as game theory. In economics, Brouwer’s fixed point theorem and its extension, the Kakutani fixed point theorem, play a central role in the proof of existence of general equilibrium in market economies as developed in the 1950s by economics Nobel prize winners Gerard Debreu and Kenneth Arrow.

Several nice applications of the BFPT exist like this : Take two sheets of paper, one lying directly above the other. If you crumple the top sheet, and place it on top of the other sheet, then Brouwer’s theorem says that there must be at least one point on the top sheet that is directly above the corresponding point on the bottom sheet (fig1)

Fig 1: Brouwer theorem at a piece of paper

Brouwer at a cup of coffee (for more info click here….

The three dimensional case was apparently proposed by Brouwer himself as he drank a cup of coffee, although Henri Poincaré and P. Bohl actually proved parts of the theorem before Brouwer. The consequence of the Brouwer fixed point theorem in three dimensions is that no matter how much you stir a cup of coffee, some point of the liquid will return to its original position. That is, assuming that none of the liquid was spilled (fig2)

Fig 2: Brouwer theorem at a cup of coffee.

And here is a problem from all russian math olympiad 1991 4th round which is related to all above (or so I think):

Fig 3: The flies change each time there position at the the vertices of the cube.

At each vertex of a cube there is a fly. At one moment, each fly moves to another vertex, one fly to each vertex. Show that there exist three flies which form a triangle congruent to the one they formed initially (fig3).