A non-distinct system of representative edges. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T13:44:01Z http://mathoverflow.net/feeds/question/91373 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91373/a-non-distinct-system-of-representative-edges A non-distinct system of representative edges. julkiewicz 2012-03-16T15:13:31Z 2012-03-16T16:57:36Z <p>I have the following problem:</p> <p>Let $\mathcal{G} = (G_{i})_{i}$ be a collection of graphs. I would like to find a "system of representative edges" $f : \mathcal{G} \rightarrow \bigcup_{i} E(G_{i})$ such that $f(G_{i}) \in E(G_{i})$ and for each $i, j$ either $f(G_{i}) = f(G_{j})$ or $f(G_{i}) \cap f(G_{j}) = \emptyset$.</p> <p>In other words, out of each graph we choose one representative edge. Edges $e_{1}$ and $e_{2}$ chosen for any two graphs need to either be non-overlapping or identiacal.</p> <p>This clearly looks very similar to special case of a system of <em>distinct</em> representatives for hypergraphs. However, as noted above, in my case the edges need not be distinct.</p> <p>An even more specialized case of this problem, where each $G_{i}$ is a biclique naturally emerges when considering CNF formulae (in this case the two partitions contain positive and negative literals respectively).</p> <p><strong>Questions:</strong> Has such or similar problem been considered in the literature? What theorems apart from Kőnig's theorem and Hall's marriage theorem could serve as existence criteria or analysis tools for the presented problem.</p> <p>I will be most grateful for your help.</p>