A classical proof due to Dirac shows that the if a graph has a minimum degree at least d, then there exists a path of size at least d. The project we worked on is a simple relaxation of these criteria; rather than insisting that every vertex of the graph have a certain degree, insist only that some vertices have a particularly large degree, and ignore the degrees of the rest. The idea, naturally, is to retain some of understanding about the graph (i.e. being able to guarantee that it has a path of a particular size) while relaxing properties describing it from local to global criteria. In this case, we still seek a long path, but rather than insist that at every vertex there be at least d vertices adjacent to it, insist that there are only SOME vertices with degree d.
can we find a path through the red points, or at least some fraction of them, even if they are not necessarily adjacent to each other?
Notations:
G is a graph on n+l vertices
L(£) := {x in G so that deg(x) is at least £}
|L(£)| = l, the order of L(£).
When we first conceptualize this graph; it looks like a set of stars connecting to the set of vertices. Since we cannot guarantee that any points in G\L(£) are adjacent to each other, it is natural to seek our long path as a long connecting "chain" through the large-degree vertices in L(£). First lets look at some simple cases:
we seek connections between the neighborhoods of each large-degree vertex, finding these connections when the neighborhoods intersect. There vertices exist which are adjacent to both large-degree points.
The most natural reaction is to experiment with variations of £; picking variations of this degree gives a feeling for what sorts of difficulty there are in the general case for any £. So lets look at a blatently trivial case: £ = n.
if £=n, then every vertex in L(£) is adjacent to every vertex of G\L(£). This is really just the complete bipartite graph between a set of vertices of order l and a set of vertices of order n. So, as long as l is at most as large as n, then we can always find a path through every single vertex of L(£), the difficulty with l>n being that the (l-n)th vertex would not have an unused vertex of G\L(£) to continue the path into. Clearly, we can see that, as a result, if £=n, then there always exists a path of length 2l, unless l>n, in which case we can only find a path of length 2(l-n).
The point here is to illustrate that it is possible to start at any point in the set £=n, and greedily (randomly) select any new vertex also in £=n, and still be able to find an un-used vertex (e.g. a vertex not already in the path) in G\L(£) which is adjacent to both of them. This illustrates the greedy principle through this path-existance demonstration - we will always seek a way to ensure the existance of a path through some fraction of L(£) without having to concern ourselves with problems in the future; if we start drawing the path through several vertices and have so far ended up at a vertex in L(£) we want to be able to pick randomly out of the remaining vertices in that fraction of L(£) without concern for the existance of a intermediary vertex in G\L(£) whcih connects the two; because we know it's there already. (which is clear in the preceding example). This means that in the future; if we consider the neighborhoods of vertices which each vertex in L(£) is adjacent with, then in that fraction of L(£), we will insist that all of these neighborhoods intersect with each other in at least a few vertices so that we can pick as greedily as we do. The next case, as we relax conditions on £ is a little more complicated, but still simple:
Suppose £>n/2.
For £>n/2, the situation is a little more problematic; no longer is the intersection of neighborhoods between any two vertices in L(£) the whole of G; rather it only has to be a single vertex in G\L(£). This means that as we draw our path through , we can still find a vertex in the intersection between any two elements of L(£), but a problem arises with greedily choosing a next vertex in L(£); it is possible that the third vertex could only have a neighborhood which intersects with the neighborhood of the second in precisely the point which was used to connect the first and the second points in L(£). With £>n/2, paths no longer have to be accessible in any order, and our greedy habits break down. If we simply tighten our requirements on £ however, changing it from £>n/2 to (£+k)>n/2; that is, adding a constant number of vertices to the neighborhood of any vertex in L(£), we can force the intersection betwen any two vertices in L(£) to be greater than 1. in fact, we can force it to be as large as we need; so insist that we chose k so that the intersection is at least as large as l; then we can again find a 2l path through the vertices of L(£), as before.
To get "hard" numbers for this hurdle, the problem becomes an exercise in combinatorics; correlate each neighborhood of a vertex in L(£) with a subset of v(G) which is of order £>n/p (p was 2 in the previous case, but the problem is better with general p). The statement of the problem is as follows; find the minimum number of arbitrarily chosen subsets of G of this order (£>n/p) so that J of them share an intersection of size at least l. This exercize is not terribly difficult, and is left to the reader; hint: it's something like 2p subsets.
When £>n/3, the situation becomes still more complicated; while results from the assist us, we naturally seek a sort of "worst case", as is typical in extremal graph theory. if £>n/3, then we no longer can guarantee the intersection of the neighborhoods of any two vertices by any means; However, between the neighborhoods of any 3 vertices, two of them must intersect - since each is of order larger than n/3. This leads to the intuition that while a path cannot be found throughout every vertex in L(£), that we can find a path through at least half of the vertices in L(£). We can imagine that the vertices in L(£) are divided into two groups; one half has neighborhoods intersecting every other neighborhood in it's half, and the other half has neighborhoods intersecting every other vertex in it's half, and yet there is no x in L(£) such that it's neighborhood intersects with neighborhoods in both halves. Hence our passage from one side of L(£) to the other, while drawing a path, is blocked, meaning that we can only guarantee a path of size 2*(l/2)
unpassable barriers can exist that ruin chances for a really long path
1) the vertex set of H is L(£), the set of high degree vertices in G.
2)the edge set is defined as follows: x and y are adjacent in H if their neighborhoods intersect by at least k vertices.
This approach results in a much simplified description of the situation with £>n/3. If we hypothesize our "worst case" again, we realize that in H, the graph appears as two disjoint cliques. And our gut feeling is correct; we can find a path of length (l/2), so in G, we can find a path of length 2*(l/2) In general, our problem is solved with an application of a theorem due to Chvatál (Ramsey Theory,Graham, Rothschild, Spencer, 1977): This theorem state that there exists a path of size P in H so that:
where a is the independance number of H - the largest number of vertices which are non adjacent from each other in H.
So, applied to G, if £>(n+k)/p, then P is at least 2((|v(H)|/a)-1).