A problem

I seem to have too many balls in the air at the moment. So let me drop one here. Any thoughts very welcome.

A k-hypergraph consists of a set X of vertices and a collection of k-element subsets called edges. It is k-partite if there is a partition of the vertices into k parts so that every edge is a transversal to this partition, which I will call a k-partition.

Clearly there is a tension between edges and k-partitions; you would expect that more k-partitions would imply fewer edges. In one special case this is true. The existence of a second k-partition implies the existence of two vertices x,y which lie in the same part of one of the k-partitions and different parts of the other; then no edge can contain x and y.

My conjecture is very specific:

Suppose that the k-hypergraph on n vertices has at least kr k-partitions, for some positive integer r. Then there is a k-partite k-hypergraph H1 on n−r vertices which has at least as many edges as H.

The hypotheses are not pulled out of the air. Adding an isolated vertex v to a k-partite k-hypergraph multiplies the number of k-partitions by k, since v can be added to any one of the parts. So the conjecture is true if the hypergraph has r isolated vertices.

The conjecture is true if k = 2. For a connected bipartite graph has a unique bipartition; so a graph with 2r bipartitions has at least r connected components, and a simple calculation gives the result.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics and tagged . Bookmark the permalink.

4 Responses to A problem

  1. Luke Pebody says:

    Might the conjecture be true if there are at least k^(r-1)+1 r-partitions?

    • Luke Pebody says:

      Proof for r = 1

      If there are at least 2 k-partitions, there are two vertices u and v which are in the same piece in one partition (P) but not in the other (Q).

      Since u and v are in the same partition in P, they are not together in any edge. Further, since they are in different partitions in Q, there are no two edges which only differ in that one contains u and one contains v. Thus if we coalesce u and v into a single vertex, we have an k-partite (P is still a k-partition) k-uniform hypergraph with one fewer vertex and the same number of edges.

      To prove for general r it would be sufficient to show that if there are at least (sk+1) k-partitions, then there are two vertices u and v which are in the same piece in at least (s+1) of the partitions but not in all of them. Then if we coalesce u and v we will have at least (s+1) partitions in the new graph.

  2. Luke Pebody says:

    And to complete my proof:

    If there are at least ks+1 distinct k-partitions (and at least one edge), there must be two vertices which are in the same piece in at least s+1 of the k-partitions but not all of them.

    Let vertices v_1, v_2, …, v_k form an edge. We can label all the k-partitions so that vertex v_i is coloured with colour i in each k-partition for all i.

    Then since there are at least 2 distinct k-partitions, there is some vertex which is not labelled the some colour in all of the partitions. But there are ks+1 k-partitions and by the pigeonhole principle, at least s+1 of them must use the same colour c. That puts it in the same piece in those s+1 pieces as vertex v_c, but not all of them.

    This combined with my previous comment proves the result.

  3. Thank you Luke, problem solved!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.