## Return to Question

4 edited tags
3 added 1 characters in body

I have the following problem:

Let $\mathcal{G} = (G_{i}){i} G_{i})_{i}$ be a collection of graphs. I would like to find a "system of representative edges" $f : \mathcal{G} \rightarrow \bigcup{i} 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$.

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.

This clearly looks very similar to special case of a system of distinct representatives for hypergraphs. However, as noted above, in my case the edges need not be distinct.

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

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

I will be most grateful for your help.

2 deleted 9 characters in body; edited tags; added 1 characters in body

I have the following problem:

Let $\mathcal{G} = { G_{i} }(G_{i}){i=1..n} 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$.

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.

This clearly looks very similar to special case of a system of distinct representatives for hypergraphs. However, as noted above, in my case the edges need not be distinct.

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

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

I will be most gratful grateful for your help.

1

# A non-distinct system of representative edges.

I have the following problem:

Let $\mathcal{G} = { G_{i} }{i=1..n}$ 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$.

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.

This clearly looks very similar to special case of a system of distinct representatives for hypergraphs. However, as noted above, in my case the edges need not be distinct.

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

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

I will be most gratful for your help.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9444983601570129, "perplexity_flag": "head"}