Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
1  
Does this contain anything of interest to you? sciencedirect.com/science/article/pii/0012365X9591426Q –  Benjamin Dickman Dec 23 '12 at 8:28

2 Answers 2

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...

share|improve this answer
    
I had some theoretical application in mind, so I do not care about complexity. Thanks anyway! –  Seva Dec 26 '12 at 14:15
1  
This is not just about complexity, it shows that no "simple" formulation can be given, as simple things are checkable in P. –  domotorp Dec 27 '12 at 9:37

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.

share|improve this answer
    
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. –  Seva Dec 23 '12 at 20:36
    
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. –  Tony Huynh Dec 23 '12 at 20:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.