Properties of Unique Degree Sequences of 3-Uniform Hypergraphs
In 2018 Deza et al. proved the NP-completeness of deciding wether there exists a 3-uniform hypergraph compatible with a given degree sequence. A well known result of Erdös and Gallai (1960) shows that the same problem related to graphs can be solved in polynomial time. So, it becomes relevant to det...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| منشور في: |
2021
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://dspaceusad7.4science.cloud/handle/123456789/1231 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1857415063226286081 |
|---|---|
| author | Tarsissi, Lama |
| author_facet | Tarsissi, Lama |
| author_role | author |
| dc.creator.none.fl_str_mv | Tarsissi, Lama |
| dc.date.none.fl_str_mv | 2021-12-19T09:08:05Z 2021-12-19T09:08:05Z 2021 |
| dc.identifier.none.fl_str_mv | https://dspaceusad7.4science.cloud/handle/123456789/1231 10.1007/978-3-030-76657-3_22 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Lecture Notes in Computer Science Discrete Geometry and Mathematical Morphology Discrete Geometry and Mathematical Morphology 0302-9743 1611-3349 |
| dc.subject.none.fl_str_mv | Hypergraph Graphic sequence Uniqueness problem Analysis of algorithms |
| dc.title.none.fl_str_mv | Properties of Unique Degree Sequences of 3-Uniform Hypergraphs |
| dc.type.none.fl_str_mv | Controlled Vocabulary for Resource Type Genres::text::book::book part |
| description | In 2018 Deza et al. proved the NP-completeness of deciding wether there exists a 3-uniform hypergraph compatible with a given degree sequence. A well known result of Erdös and Gallai (1960) shows that the same problem related to graphs can be solved in polynomial time. So, it becomes relevant to detect classes of uniform hypergraphs that are reconstructible in polynomial time. In particular, our study concerns 3-uniform hypergraphs that are defined in the NP-completeness proof of Deza et al. Those hypergraphs are constructed starting from a non-increasing sequence s of integers and have very interesting properties. In particular, they are unique, i.e., there do not exist two non isomorphic 3-uniform hypergraphs having the same degree sequence ds . This property makes us conjecture that the reconstruction of these hypergraphs from their degree sequences can be done in polynomial time. So, we first generalize the computation of the ds degree sequences by Deza et al., and we show their uniqueness. We proceed by defining the equivalence classes of the integer sequences determining the same ds and we define a (minimal) representative. Then, we find the asymptotic growth rate of the maximal element of the representatives in terms of the length of the sequence, with the aim of generating and then reconstructing them. Finally, we show an example of a unique 3-uniform hypergraph similar to those defined by Deza et al. that does not admit a generating integer sequence s. The existence of this hypergraph makes us conjecture an extended generating algorithm for the sequences of Deza et al. to include a much wider class of unique 3-uniform hypergraphs. Further studies could also include strategies for the identification and reconstruction of those new sequences and hypergraphs. |
| id | sorbonner_385d4890d3aa47f28ad047d63a8536d0 |
| identifier_str_mv | 10.1007/978-3-030-76657-3_22 |
| language_invalid_str_mv | en |
| network_acronym_str | sorbonner |
| network_name_str | Sorbonne University Abu Dhabi repository |
| oai_identifier_str | oai:depot.sorbonne.ae:20.500.12458/1231 |
| publishDate | 2021 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Properties of Unique Degree Sequences of 3-Uniform HypergraphsTarsissi, LamaHypergraphGraphic sequenceUniqueness problemAnalysis of algorithmsIn 2018 Deza et al. proved the NP-completeness of deciding wether there exists a 3-uniform hypergraph compatible with a given degree sequence. A well known result of Erdös and Gallai (1960) shows that the same problem related to graphs can be solved in polynomial time. So, it becomes relevant to detect classes of uniform hypergraphs that are reconstructible in polynomial time. In particular, our study concerns 3-uniform hypergraphs that are defined in the NP-completeness proof of Deza et al. Those hypergraphs are constructed starting from a non-increasing sequence s of integers and have very interesting properties. In particular, they are unique, i.e., there do not exist two non isomorphic 3-uniform hypergraphs having the same degree sequence ds . This property makes us conjecture that the reconstruction of these hypergraphs from their degree sequences can be done in polynomial time. So, we first generalize the computation of the ds degree sequences by Deza et al., and we show their uniqueness. We proceed by defining the equivalence classes of the integer sequences determining the same ds and we define a (minimal) representative. Then, we find the asymptotic growth rate of the maximal element of the representatives in terms of the length of the sequence, with the aim of generating and then reconstructing them. Finally, we show an example of a unique 3-uniform hypergraph similar to those defined by Deza et al. that does not admit a generating integer sequence s. The existence of this hypergraph makes us conjecture an extended generating algorithm for the sequences of Deza et al. to include a much wider class of unique 3-uniform hypergraphs. Further studies could also include strategies for the identification and reconstruction of those new sequences and hypergraphs.2021-12-19T09:08:05Z2021-12-19T09:08:05Z2021Controlled Vocabulary for Resource Type Genres::text::book::book parthttps://dspaceusad7.4science.cloud/handle/123456789/123110.1007/978-3-030-76657-3_22enLecture Notes in Computer ScienceDiscrete Geometry and Mathematical MorphologyDiscrete Geometry and Mathematical Morphology0302-97431611-3349oai:depot.sorbonne.ae:20.500.12458/12312024-03-19T11:13:23Z |
| spellingShingle | Properties of Unique Degree Sequences of 3-Uniform Hypergraphs Tarsissi, Lama Hypergraph Graphic sequence Uniqueness problem Analysis of algorithms |
| title | Properties of Unique Degree Sequences of 3-Uniform Hypergraphs |
| title_full | Properties of Unique Degree Sequences of 3-Uniform Hypergraphs |
| title_fullStr | Properties of Unique Degree Sequences of 3-Uniform Hypergraphs |
| title_full_unstemmed | Properties of Unique Degree Sequences of 3-Uniform Hypergraphs |
| title_short | Properties of Unique Degree Sequences of 3-Uniform Hypergraphs |
| title_sort | Properties of Unique Degree Sequences of 3-Uniform Hypergraphs |
| topic | Hypergraph Graphic sequence Uniqueness problem Analysis of algorithms |
| url | https://dspaceusad7.4science.cloud/handle/123456789/1231 |