6
$\begingroup$

A graph is bipartite if and only if it does not contain odd cycles. Is there a similar criterion for hypergraphs? (A hypergraph is called bipartite if its vertices can be colored in two colors so that no hyperedge is monochromatic.)

My guess is that the answer is "no" but, maybe, there are results in this direction I am not aware of. Thanks!

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
6
$\begingroup$

No, there isn't because deciding whether a hypergraph is bipartite (2-colorable) or not is NP-complete (reduction from NAE-SAT) already for 3-uniform hypergraphs. Of course if by similar you mean something that is not necessarily verifiable in polynomial time, then the answer might be yes...

Improve this answer
$\endgroup$
2
  • $\begingroup$ I had some theoretical application in mind, so I do not care about complexity. Thanks anyway! $\endgroup$
    – Seva
    Commented Dec 26, 2012 at 14:15
  • 1
    $\begingroup$ This is not just about complexity, it shows that no "simple" formulation can be given, as simple things are checkable in P. $\endgroup$
    – domotorp
    Commented Dec 27, 2012 at 9:37
3
$\begingroup$

If one instead starts with the definition of bipartite as not containing any odd cycles, then there are results for hypergraphs in this direction. Indeed we can define a cycle in a hypergraph as a sequence of distinct alternating vertices and hyperedges $C:=v_1, E_1, v_2, E_2, \dots, v_n, E_n, v_1, E_1$, where $v_i \in E_i \cap E_{i+1}$ for all $i$ (mod $n$). The length of $C$ is $n$. The following is a theorem of Gyarfas, Jacobson, Kezdy and Lehel.

Theorem. Let $\mathcal{H}$ be a hypergraph where each hyperedge contains at least 3 vertices. If $\mathcal{H}$ contains no odd length cycles, then $$ \sum_{e \in E(\mathcal{H})} (|e|-1) \leq 2|V(\mathcal{H})| -2. $$ Moreover, equality holds if and only if $\mathcal{H}$ is the disjoint union of two identical uniform hypertrees.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks - good to know, but not exactly what I am looking for. The definition is that the vertices can be partitioned into two subsets so that no edge is monochromatic, and I need a criterion for this in the spirit of the familiar no-odd-cycles condition. $\endgroup$
    – Seva
    Commented Dec 23, 2012 at 20:36
  • $\begingroup$ You're welcome. Yes, this is not exactly what you are looking for, but it shows that such a characterization of bipartite hypergraphs in terms of lack of odd cycles will be tricky to come by. For example, the above theorem shows that hypergraphs with no odd cycles contain only a few edges, while bipartite hypergraphs can contain exponentially many edges. $\endgroup$
    – Tony Huynh
    Commented Dec 23, 2012 at 20:46
3
$\begingroup$

In "matching theory", by Lovasz and Plummer, I found the following page, which may be helpful:

enter image description here

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Thank you. This definitely seems relevant but, unfortunately, there is no way I can recall now what I needed this for eight years ago. $\endgroup$
    – Seva
    Commented Jun 20, 2020 at 19:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .