Fokszámsorozatok realizációjának mintavételezése (DegreeSampling)  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
126853
típus KH
Vezető kutató Erdos Péter
magyar cím Fokszámsorozatok realizációjának mintavételezése (DegreeSampling)
Angol cím Sampling degree sequence realizations (DegreeSampling)
magyar kulcsszavak hálózatelmélet, kombinatorika, fokszámsorozatok, mintavételezés
angol kulcsszavak network theory, combinatorics, degree sequences, sampling
megadott besorolás
Matematika (Élettelen Természettudományok Kollégiuma)100 %
Ortelius tudományág: Kombinatorika
zsűri Matematika–Számítástudomány
Kutatóhely Rényi Alfréd Matematikai Kutatóintézet
résztvevők Gyori Ervin
Mezei Tamás Róbert
Miklós István
Soltész Dániel
projekt kezdete 2017-12-01
projekt vége 2019-11-30
aktuális összeg (MFt) 16.435
FTE (kutatóév egyenérték) 3.00
állapot aktív projekt





 

Zárójelentés

 
kutatási eredmények (magyarul)
A projekt fő témája a grafikus fokszámsorozatok realizációinak vizsgálata a switch (swap) Markov láncok módszerével. Tradicionálisan ez 3 fő modellt foglal magába: az egyszerű, a páros illetve az irányított modellt. A téma a valós életben (társadalom tudományok, biológia, mérnöki tudományok, fizika, stb.) felmerülő komplex hálózatok vizsgálatában játszik központi szerepet. (8 cikk.) Négy fő területen sikerült eredményeket elérnünk: 1./ Egységesítettük a témában eddig használt módszereket. 2./ A 2018-ig ismert összes pozitív eredmény egy közös általánosítását bizonyítottuk be "P-stabil" fokszám sorozatokra. 3./ Beláttuk, hogy ez az új fogalom még nem jelöl áttörhetetlen akadályt a switch Markov láncokkal kapcsolatban. 4./ Részt vettünk egy véletlen reguláris gráfok növő sorozatát előállító új gráf-dinamika kifejlesztésében. Folytattuk korábbi munkáinkat extremális gráfelméleti problémákon (11 cikk). Több, phylogenetikus hálózatokkal kapcsolatos, kutatásba kapcsolódtunk be. Bevezettük az "orchard" hálózatok fogalmát, és több hálózat típus összefüggőségi tulajdonságait vizsgáltuk lokális operációk használatával (4 cikk). Végezetül több sporadikus kutatásba is bekapcsolódtunk. (További 4 publikáció.) Ezek közül a legfontosabb Miklós István megjelent monográfiája.
kutatási eredmények (angolul)
The main goal of this project was to study the switch (swap) Markov chain based sampling process of the realizations of graphic degree sequences. Traditionally it means three main models: the simple, the bipartite, and the directed degree sequence models. This study emerged from the need of analysing real-life complex networks, originating from social sciences, biology, engineering, physics, etc (8 papers). We achieved four contributions: 1./ Successful unification of the proof techniques in the above mentioned models. 2./ We found a common generalization of all previously known partial results for the class of "P-stable" degree sequence classes. 3./ We have also shown that the P-stability means a natural obstacle for the applicability of the original method, but we proved that this obstacle is not a hard border. 4./ Finally we participated in the introduction of a new, random network growing dynamics that does not change the degree of any, already introduced vertex. So it is suitable for generating a growing series of random regular networks. Furthermore, we continued our research in classical extremal graph theory (11 papers). We also got involved in research on phylogenetic networks. We introduced the class of orchard networks, and studied the connectivity problems of phylogenetic networks under different local operations (4 papers). Finally, we also participated in some sporadic researches, including the writing an important research monograph (by Miklos).
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=126853
döntés eredménye
igen





 

Közleményjegyzék

 
Erdős Péter L. ; A. Francis ; L. van Iersel ; Mezei Tamás Róbert: The tree-based, rooted binray phylogentics networks are closed under rNNI moves, in preparation, 2020
Colucci L., Erdős Péter L., Gyóri Ervin, Mezei Tamás Róbert: Terminal- Pairability in Complete Bipartite Graph of Non-Bipartite Demands, Theoretical Computer Science, DOI: 10.1016/j.tcs.2018.12.007, 2018
Ergemlidze B. , Győri Ervin, A. Methuku: Characterizing directed graphs with every edge in a fixed number of cycles, Manuscript, 2018
Győri Ervin , Katona Y. Gyula, Papp László F.: Optimal pebbling number of the square grid, submitted to Graphs and Combinatorics, arXiv:1810.05266, 2018
Győri Ervin, M.D. Plummer, Dong Ye, Xiaoya Zha: A Cycle Traversability Theorem for Claw-free Graphs, submitted to Combinatorica, arXiv 1803.04466v1, 2018
Colucci L., Erdős Péter L., Győri Ervin, Mezei Tamás Róbert: Terminal- Pairability in Complete Bipartite Graph of Non-Bipartite Demands, Theoretical Computer Science, 775, 16--25., 2019
Colucci L., Győri Ervin: On L(2,1)‐labelings of oriented graphs, arXiv:1902.05467, 2019
Colucci L., Győri Ervin, A. Methuku: Edge colorings of graphs without monochromatic stars, arXiv:1903.04541, 2019
Erdős Péter L., M. Ferrara, S.G. Hartke: Navigating Between Packings of Graphic Sequences, Discrete Applied Mathematics, 266 252--258., 2019
Erdős Péter L., C. Greenhill, Mezei Tamás Róbert, Miklós István, Soltész Dániel, Soukup Lajos: The mixing time of switch Markov chains: a unified approach, arXiv:1903.06600, 2019
Erdős Péter L., C. Greenhill, Mezei Tamás Róbert, Miklós István, Soltész Dániel, Soukup Lajos: Mixing time of the Swap Markov chain and P-Stability, Proc. EUROCOMB 2019, Acta Math. Univ. Comenianae, 88 (3) 659--665., 2019
Erdős Péter L., Győri Ervin, Mezei Tamás Róbert, Miklós István, Soltész Dániel: A non-P-stable class of degree sequences for which the swap Markov chain is rapidly mixing, arXiv:1909.02308, 2019
Erdős Péter L., C. Semple, M. Steel: A Class of Phylogenetic Networks Reconstructable from Ancestral Profiles, Mathematical Biosciences, 313, 33-40., 2019
Erdős Péter L.; L. van Iersel; M. Jones: Not all phylogenetic networks are leaf-reconstructible, Journal of Mathematical Biology, 79 (5) 1623--1638, 2019
Fang, Chunqiu ; Győri Ervin ; Xiao, Jimeng: Minimal colorings for properly colored subgraphs in complete graphs, arXiv:1911.04358, 2019
Fang, Chunqiu ; Győri Ervin, Mei Lu ; Jimeng Xiao: On the anti‐Ramsey number of forests, arXiv:1908.04129, 2019
Győri Ervin, Nika Salia, Oscar Zamora: Connected Hypergraphs without long Berge paths, arXiv:1910.01322, 2019
Győri Ervin, Nika Salia, Casey Tompkins, Oscar Zamora: Turan numbers of Berge trees, arXiv:1904.06728, 2019
Miklós István: Computational Complexity of Counting and Sampling, Chapman and Hall/CRC , ISBN 9781138035577, 2018
Győri Ervin, Nathan Lemons, Nika Salia, Oscar Zamora: The Structure of Hypergraphs without long Berge cycles, arXiv:1812.10737, 2018
B. Ergemlidze, Győri Ervin, A. Methuku: Characterizing directed graphs with every edge in a fixed number of cycles, Manuscript, 2018
Győri Ervin, M.D. Plummer, Dong Ye, Xiaoya Zha: A Cycle Traversability Theorem for Claw-free Graphs, submitted to Combinatorica, 2018
Győri Ervin , Katona Y. Gyula, Papp László F.: Optimal pebbling number of the square grid, submitted to Graphs and Combinatorics, 2018
Erdős Péter L.; L. van Iersel; M. Jones: Not all phylogenetic networks are leaf-reconstructible, arXiv 1803.03197, submitted, 2018
Erdős Péter L, Mezei Tamás Róbert, Miklós István, Soltész Dániel: Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs, PLOS One, 13 (8) e0201995, 2018
Erdős Péter L., M. Ferrara, S.G. Hartke: Navigating Between Packings of Graphic Sequences, Discrete Applied Mathematcs, in press, 2018
Janssen R., Jones M., Erdős Péter L., van Iersel L., Scornavacca C.: Exploring the tiers of rooted phylogenetic network space using tail moves, Bulletin of Mathematical Biology, 80, 2177–-2208, 2018
Erdős Péter L., Mezei Tamás Róbert, Miklós István: Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences, arXiv 1712.01709, 21 oldal, 2017
Hartarsky I., Mezei Tamás Róbert: Computing the Difficulty of Critical Bootstrap Percolation Models is NP-hard, arXiv 1809.01525v1, 13 oldal, submitted, 2018
Soltész Dániel: Even cycle creating paths, arXiv 1801.00737v1, 10 oldal, submitted, 2018
Harcos Gergely, Soltész Dániel: New Bounds On Even Cycle Creating Hamiltonian Paths Using Expander Graphs, arXiv:1904.04601, 2019
S. Kharel, Mezei Tamás Róbert, S. Chung, Soltász Dániel, Erdős Péter L., Z. Toroczkai: Degree-preserving network growth, manuscript, 2019
Krenn M., Gu X., Soltész Dániel: Questions On The Structure Of Perfect Matchings Inspired By Quantum Physics, Proceedings of the 2nd Croatian Combinatorial Days, DOI:10.5592/CO/CCD.2018, 2019
Soltész Dániel: Even cycle creating paths, Journal of Graph Theory, https://doi.org/10.1002/jgt.22490, 2019





 

Projekt eseményei

 
2017-11-27 08:57:47
Résztvevők változása




vissza »