Skip to main content
Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Authoritative reference needed by Michał Oszmaniec
Bounty Started worth 100 reputation by Michał Oszmaniec
minor typos corrected, expanded link (automatically) to its title instead of hyperlinking the word “this”, no need to add tag name to the title as well
Source Link

Reference request - graphs Graphs constructed from sums of perfect matchings

Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices.

Let $V$ be the set of vertices of cardinality $|V|=2n$ and let $\mathcal{M}=\lbrace{M_1,M_2,\ldots, M_k\rbrace}$ be a collection of perfect matchings of vertices in $V$ (understoood as graphs whose edges form a partition of $V$ into two element disjoint subsets). Let $E(\mathcal{M})=\cup_{i=1}^k E(M_i)$$E(\mathcal{M})=\bigcup_{i=1}^k E(M_i)$ be the union of all the edges appearing in perfect mathingsmatchings in $\mathcal{M}$. We now define a graph whose edge set is precisely $E(\mathcal{M})$, i.e. $G(\mathcal{M})=(V,E(\mathcal{M}))$.

Question: Does this construction have a name in the literature? If so, were the graphs constructed in this way studied from the perspective of extremeextremal graph theory.? I have in mind results in which the size of the collection $\mathcal{M}$ plays an analogous role asto the number of edges in classical results in that field, like Erdos-Stonethe Erdős–Stone or Kővári–Sós–Turán theorems.

Remark: Although it is possible to lower bound the number of edges in a graph based on the number of prefect matchings (see for example discussion in thisthe question Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs), I suspect that stronger results concerning forbidden subgraphs could be derived for the class of graphs constructed in this way. Specifically, classical results on forbidden subgraphs assumed that subgraphs whose existence we want to exclude have fixed size, while the number of vertices of the ambient graph increases. I hope that this limitation can be lifted for the class of graphs considered here.

Reference request - graphs constructed from sums of perfect matchings

Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices.

Let $V$ be the set of vertices of cardinality $|V|=2n$ and let $\mathcal{M}=\lbrace{M_1,M_2,\ldots, M_k\rbrace}$ be a collection of perfect matchings of vertices in $V$ (understoood as graphs whose edges form a partition of $V$ into two element disjoint subsets). Let $E(\mathcal{M})=\cup_{i=1}^k E(M_i)$ be the of all the edges appearing in perfect mathings in $\mathcal{M}$. We now define a graph whose edge set is precisely $E(\mathcal{M})$ i.e. $G(\mathcal{M})=(V,E(\mathcal{M}))$.

Question: Does this construction have a name in the literature? If so, were the graphs constructed in this way studied from the perspective of extreme graph theory. I have in mind results in which the size of the collection $\mathcal{M}$ plays an analogous role as number of edges in classical results in that field, like Erdos-Stone or Kővári–Sós–Turán theorems.

Remark: Although it is possible to lower bound the number of edges in a graph based on the number of prefect matchings (see for example discussion in this question), I suspect that stronger results concerning forbidden subgraphs could be derived for the class of graphs constructed in this way. Specifically, classical results on forbidden subgraphs assumed that subgraphs whose existence we want to exclude have fixed size, while the number of vertices of the ambient graph increases. I hope that this limitation can be lifted for the class of graphs considered here.

Graphs constructed from sums of perfect matchings

Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices.

Let $V$ be the set of vertices of cardinality $|V|=2n$ and let $\mathcal{M}=\lbrace{M_1,M_2,\ldots, M_k\rbrace}$ be a collection of perfect matchings of vertices in $V$ (understoood as graphs whose edges form a partition of $V$ into two element disjoint subsets). Let $E(\mathcal{M})=\bigcup_{i=1}^k E(M_i)$ be the union of all the edges appearing in perfect matchings in $\mathcal{M}$. We now define a graph whose edge set is precisely $E(\mathcal{M})$, i.e. $G(\mathcal{M})=(V,E(\mathcal{M}))$.

Question: Does this construction have a name in the literature? If so, were the graphs constructed in this way studied from the perspective of extremal graph theory? I have in mind results in which the size of the collection $\mathcal{M}$ plays an analogous role to the number of edges in classical results in that field, like the Erdős–Stone or Kővári–Sós–Turán theorems.

Remark: Although it is possible to lower bound the number of edges in a graph based on the number of prefect matchings (see for example discussion in the question Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs), I suspect that stronger results concerning forbidden subgraphs could be derived for the class of graphs constructed in this way. Specifically, classical results on forbidden subgraphs assumed that subgraphs whose existence we want to exclude have fixed size, while the number of vertices of the ambient graph increases. I hope that this limitation can be lifted for the class of graphs considered here.

Source Link

Reference request - graphs constructed from sums of perfect matchings

Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices.

Let $V$ be the set of vertices of cardinality $|V|=2n$ and let $\mathcal{M}=\lbrace{M_1,M_2,\ldots, M_k\rbrace}$ be a collection of perfect matchings of vertices in $V$ (understoood as graphs whose edges form a partition of $V$ into two element disjoint subsets). Let $E(\mathcal{M})=\cup_{i=1}^k E(M_i)$ be the of all the edges appearing in perfect mathings in $\mathcal{M}$. We now define a graph whose edge set is precisely $E(\mathcal{M})$ i.e. $G(\mathcal{M})=(V,E(\mathcal{M}))$.

Question: Does this construction have a name in the literature? If so, were the graphs constructed in this way studied from the perspective of extreme graph theory. I have in mind results in which the size of the collection $\mathcal{M}$ plays an analogous role as number of edges in classical results in that field, like Erdos-Stone or Kővári–Sós–Turán theorems.

Remark: Although it is possible to lower bound the number of edges in a graph based on the number of prefect matchings (see for example discussion in this question), I suspect that stronger results concerning forbidden subgraphs could be derived for the class of graphs constructed in this way. Specifically, classical results on forbidden subgraphs assumed that subgraphs whose existence we want to exclude have fixed size, while the number of vertices of the ambient graph increases. I hope that this limitation can be lifted for the class of graphs considered here.