Információelmélet és alkalmazásai  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
120706
típus K
Vezető kutató Simonyi Gábor
magyar cím Információelmélet és alkalmazásai
Angol cím Information Theory and its Applications
magyar kulcsszavak információelmélet, matematikai statisztika, mértékkoncentráció, kombinatorika, gráfelmélet
angol kulcsszavak Information theory, mathematical statistics, measure concentration, combinatorics, graph theory
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Valószínűségelmélet
zsűri Matematika–Számítástudomány
Kutatóhely HUN-REN Rényi Alfréd Matematikai Kutatóintézet
résztvevők Csiszár Imre
Farkas Lóránt
Gujgiczer Anna
Kói Tamás
Marton Katalin
Soltész Dániel
projekt kezdete 2016-12-01
projekt vége 2023-06-30
aktuális összeg (MFt) 13.569
FTE (kutatóév egyenérték) 15.73
állapot aktív projekt





 

Zárójelentés

 
kutatási eredmények (magyarul)
A klasszikus információelmélet területén több eredményt sikerült bizonyítani a többszörös hozzáférésű csatornán történő aszinkron információtovábbítással kapcsolatban. Az egyik fő eredmény annak felismerése, hogy a kontrolláltan aszinkron működtetés jobb hibaexponenst eredményezhet mint a szinkron működtetés. További észrevétel, hogy a többszörös hozzáférésű csatorna egy kontrolláltan aszinkron kódja egy egyadós trellis kódot eredményez. Információelméleti módszerek segítségével sikerült log-Sobolev egyenlőtlenséget bizonyítani és használtunk ilyen módszereket pénzügyi és statisztikai problémákhoz is. Számos eredmény született az információelméleti kombinatorikának nevezhető területen. Ezek közül több is korlátokat vagy pontos eredményeket ad a rögzített n csúcson megadható olyan Hamilton utak számára, melyek közül bármely kettő uniója tartalmaz egy előírt részgráfot. Sikerült megválaszolni Tardif egy kérdését Kneser gráfokba irányuló bizonyos gráfhomomorfizmusokkal kapcsolatban. Szükséges illetve elégséges feltételeket bizonyítottunk Schrijver gráfok éleinek színkritikusságával kapcsolatban és sikerült megadni Schrijver gráfoknak egy a tört kromatikus számra nézve kritikus feszített részgráfját. Bevezettünk gráfokból álló kódokat és éles eredményeket bizonyítottunk róluk számos speciális esetben. A Shannon-féle gráfkapacitás Hedetniemi-típusú egyenlőséggel kapcsolatos vizsgálatát kezdeményeztük, illetve vizsgáltuk a gráfkapacitást Ramsey-típusú tételekkel kapcsolatban is.
kutatási eredmények (angolul)
In the area of classical information theory several results were proven concerning asynchromous transmission over a multiple access channel (MAC). One of the main findings was that controlled asynchronism may outperform synchronism as far as the error exponents are concerned. It was also observed that a controlled asynchronous code for a MAC gives rise to a one-sender trellis code. Information theoretic techniques were also used to prove a log-Sobolev inequaity and to problems related to finance and statistics. Several results were proven in the are of information theory related combinatorics. Some of these give bounds or exact results about the maximum number of Hamiltonian paths on a given set of n vertices that have the property that the union of any two of them contains a prescribed subgraph. A question of Tardif was answered about the existence of certain graph homomorphisms into Kneser graphs. Criteria about the color-criticality of edges in Schrijver graphs were proven and the criticality of a certain induced subgraph of Schrijver graphs was shown with respect to the fractional chromatic number. Graph codes were introduced and tight results about their maximum possible size were proven in several special cases. Investgations about the behaviour of the Shannon capacity of graphs and a Hedetniemi-type equality were initiated. Shannon's graph capacity problem was also investigated in relation with Ramsey type results.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=120706
döntés eredménye
igen





 

Közleményjegyzék

 
L. Farkas, T. Kói: Universal random access error exponents for codebooks of different word-lengths, IEEE Transactions on Information Theory, vol. 64., pp. 2240-2252., 2018
D. Soltész: New bounds on Simonyi's conjecture, European Journal of Combinatorics, Vol. 70, pp. 251-267., 2018
Anna Gujgiczer, Gábor Simonyi: On multichromatic numbers of widely colorable graphs,, J. Graph Theory, vol. 100, pp. 346-351., 2022
Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, Gábor Simonyi: Structured codes of graphs, SIAM J. Discrete Math., accepted for publication, 2022
Anna Gujgiczer, Gábor Simonyi: Critical subgraphs of Schrijver graphs for the fractional chromatic number, submitted, 2022
Eszter Uhrin, Zsuzsanna Domokos, László Márk Czumbel, Tamás Kói, Péter Hegyi , Péter Hermann, Judit Borbély, Bianca Golzio Navarro Cavalcante, Orsolya Németh: Teledentistry: A Future Solution In The Diagnosis Of Oral Lesions: A Diagnostic Meta-Analysis And Systematic Review, Telemedicine and e-Health, accepted, 2022
L. Farkas, T. Kói, I. Csiszár: Error exponents for sparse communication, Proceedings of IEEE International Symposium on Information Theory, pp. 3145-3149., 2017
Gergely Harcos, Daniel Soltész: New bounds on even cycle creating Hamiltonian paths using expander graphs, Combinatorica 40, 435-454, 2020
Lóránt Farkas: Trellis Code Error Exponent From Results for Asynchronous Multiple Access Channels, ISITA2020 (A01-10.), http://www.isita.ieice.org/2020/technical_program_all.html, 2020
Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, Gábor Simonyi: Structured codes of graphs, SIAM J. Discrete Math., 37, 379-403;, 2023
Eszter Uhrin, Zsuzsanna Domokos, László Márk Czumbel, Tamás Kói, Péter Hegyi , Péter Hermann, Judit Borbély, Bianca Golzio Navarro Cavalcante, Orsolya Németh: Teledentistry: A Future Solution In The Diagnosis Of Oral Lesions: A Diagnostic Meta-Analysis And Systematic Review, Telemedicine and e-Health, accepted (published online 28 Mar 2023), 2023
Anna Gujgiczer, Reza Naserasr, Rohini S, S Taruni: Winding number and circular 4-coloring of signed graphs, submitted, 2023
Anna Gujgiczer, Gábor Simonyi, Gábor Tardos: On the generalized Myczielskian of complements of odd cycles, Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 485-488., 2023
A. Sali, G. Simonyi, G. Tardos: Partitioning transitive tournaments into isomorphic digraphs, Order, 2020
G. Simonyi: On colorful edge triples in edge-colored complete graphs, Graphs and Combinatorics 36, 1623–1637., 2020
D. Soltész: Even cycle creating paths, J. Graph Theory 93 (3), 350-362, 2020
Gergely Harcos, Daniel Soltész: New bounds on even cycle creating Hamiltonian paths using expander graphs, Combinatorica 40, 435-454, 2020
Gábor Simonyi: Shannon capacity and the categorical product, arXiv:1911.00944 [math.CO] (submitted for publication), 2019
Gábor Simonyi, Gábor Tardos: On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges, Acta Math. Hungar. 161 (2: Special issue dedicated to Endre Szemerédi's 80th birthday), 583–617, 2020
Imre Csiszár, Lóránt Farkas, Tamás Kói: Error exponents for asynchronous multiple access channels. controlled asynchronism may outperform synchronism, arXiv:1907.05139 [cs.IT], v2:2020, 2019
Lóránt Farkas: Trellis Code Error Exponent From Results for Asynchronous Multiple Access Channels, ISITA2020 (A01-10.), http://www.isita.ieice.org/2020/technical_program_all.html, 2020
A. Sali, G. Simonyi, G. Tardos: Partitioning transitive tournaments into isomorphic digraphs, Order, vol. 38, pp. 211-228., 2021
Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei, István Miklós, Dániel Soltész: Half-graphs, other non-stable degree sequences, and the switch Markov chain, Electronic Journal of Combinatorics, Volume 28, Issue 3 (2021) P3.7, 2021
Péter L. Erdős, Catherine Greenhill, Tamás Róbert Mezei, István Miklós, Dániel Soltész, Lajos Soukup: The mixing time of switch Markov chains: a unified approach, European Journal of Combinatorics 99, #103421, 2022
Gábor Simonyi: Shannon capacity and the categorical product, Electronic Journal of Combinatorics, Volume 28, Issue 1, #P1.51, 2021
Imre Csiszár, Lóránt Farkas, Tamás Kói: Error exponents for asynchronous multiple access channels. controlled asynchronism may outperform synchronism, IEEE Transactions on Information Theory, vol. 67, no. 12, pp. 7684-7707., 2021
Anna Gujgiczer, Gábor Simonyi: On multichromatic numbers of widely colorable graphs,, J. Graph Theory, to appear; online already appeared at https://doi.org/10.1002/jgt.22785, 2021
L. Farkas, T. Kói: Universal random access error exponents for codebooks of different word-lengths, Proceedings of IEEE International Symposium on Information Theory, pp. 3150-3154, 2017
L. Farkas, T. Kói, I. Csiszár: Error exponents for sparse communication, Proceedings of IEEE International Symposium on Information Theory, pp. 3145-3149., 2017
I. Kovács, D. Soltész: Triangle-different Hamiltonian paths, Journal of Combinatorial Theory Series B, in press, available online, 2017
L. Farkas, T. Kói: Universal random access error exponents for codebooks of different word-lengths, IEEE Transactions on Information Theory, vol. 64., pp. 2240-2252., 2018
I. Kovács, D. Soltész: Triangle-different Hamiltonian paths, Journal of Combinatorial Theory Series B, Volume 129, pp. 1-17., 2018
I. Csiszár, T. Breuer: Expected value minimization in information theoretic multiple priors models, IEEE Transactions on Information Theory, vol. 64., pp. 1957-1974., 2018
L. Farkas, T. Kói: Contributions to successive decoding for multiple access channels, International Symposium on Information Theory and Its Applications (ISITA) Proceedings, 602-606., 2018
R. Aharoni, D. Soltész: Independent sets in the union of two Hamiltonian cycles, Electronic Journal of Combinatorics, Volume 25, Issue 4, 2018
P. L. Erdős, T. R. Mezei, I. Miklós, D. Soltész: Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs, PLoS ONE 13(8): e0201995, 2018
L. Farkas, T. Kói,: An Improved Packing Lemma for Asynchronous Multiple Access Channel,, International Symposium on Information Theory (ISIT), 26 (2018), recent result poster session, 2018
D. Soltész: New bounds on Simonyi's conjecture, European Journal of Combinatorics, Vol. 70, pp. 251-267., 2018
A. Sali, G. Simonyi, G. Tardos: Partitioning transitive tournaments into isomorphic digraphs, arXiv:1806.00729 [math.CO] (submitted for publication), 2018
G. Simonyi: On colorful edge triples in edge-colored complete graphs, arXiv:1812.06706 [math.CO] (submitted for publication), 2018
I. Kovács, D. Soltész: On k-neighbor separated permutations, arXiv:1711.07524 [math.CO] (submitted for publication), 2017
D. Soltész: Even cycle creating paths, arXiv:1801.00737 [math.CO] (submitted for publication), 2018
I. Kovács, D. Soltész: Triangle-different Hamiltonian paths, Journal of Combinatorial Theory Series B, Volume 129, pp. 1-17., 2018
L. Farkas, T. Kói,: Two contributions to error exponents for asynchronous multiple access channel, International Symposium on Information Theory Proceedings (ISIT), 27 (2019), 2664 - 2668., 2019
A. Sali, G. Simonyi, G. Tardos: Partitioning transitive tournaments into isomorphic digraphs, arXiv:1806.00729 [math.CO] (preprint), 2018
I. Kovács, D. Soltész: On k-neighbor separated permutations, SIAM J. Discrete Math. 33(3), 1691–1711; https://doi.org/10.1137/17M1158744, 2019
D. Soltész: Even cycle creating paths, J. Graph Theory; https://doi.org/10.1002/jgt.22490, (accepted for publication), 2019
Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei, István Miklós, Dániel Soltész: A non-P-stable class of degree sequences for which the swap Markov chain is rapidly mixing, arXiv:1909.02308 [math.CO] (submitted for publication), 2019
Péter L. Erdős, Catherine Greenhill, Tamás Róbert Mezei, István Miklós, Dániel Soltész, Lajos Soukup: The mixing time of the switch Markov chains: a unified approach, arXiv:1903.06600 [math.CO] (submitted for publication), 2019
Gergely Harcos, Daniel Soltész: New bounds on even cycle creating Hamiltonian paths using expander graphs, arXiv:1904.04601 [math.CO] (submitted for publication), 2019
Gábor Simonyi: Shannon capacity and the categorical product, arXiv:1911.00944 [math.CO] (submitted for publication), 2019
Gábor Simonyi, Gábor Tardos: On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges, arXiv:1912.03724 [math.CO] (submitted for publication), 2019
Katalin Marton: Logarithmic Sobolev inequalities in discrete product spaces, Combin. Probab. Comput. 28, no. 6, 919–935., 2019
Lóránt Farkas, Tamás Kói: Error exponents for asynchronous multiple access channels. controlled asynchronism may outperform synchronism, arXiv:1907.05139 [cs.IT], 2019





 

Projekt eseményei

 
2021-01-08 13:48:10
Résztvevők változása




vissza »