Discrete and Continuous: interfaces between graph theory, algebra, analysis and geometry  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
67867
Type NK
Principal investigator Lovász, László
Title in Hungarian Diszkrét és folytonos: a gráfelmélet, algebra, analízis és geometria találkozási pontjai
Title in English Discrete and Continuous: interfaces between graph theory, algebra, analysis and geometry
Keywords in Hungarian gráfsorozatok, gráfhomomorfizmusok, Markov láncok, polinom módszer, gömbelhelyezések
Keywords in English graph sequences, graph homomorphisms, Markov chains, polynomial method, ball packing
Discipline
Mathematics (Council of Physical Sciences)100 %
Panel Mathematics and Computing Science
Department or equivalent Department of Computer Science (Eötvös Loránd University)
Participants Bárász, Mihály
Bezdek, Károly
Böröczky, Károly
Csikós, Balázs
Csóka, Endre
Elekes, György
Fancsali, Szabolcs
Gács, András
Geleji, János
Grolmusz, Vince
Gyenes, Zoltán
Héger, Tamás
Horváth, Gábor
Iván, Gábor
Jordán, Tibor
Károlyi, Gyula
Király, Tamás
Király, Zoltán
Kiss, György
Kovácsné Becker, Johanna Cecília
Kun, Gábor
Laczkovich, Miklós
Lippner, Gábor
Miklós, Zoltán
Nagy, Dániel
Ördög, Rafael
Pach, Péter Pál
Pálvölgyi, Dömötör
Pap, Júlia
Patkós, Balázs
Pluhár, Gabriella
Sikolya, Eszter
Szabadka, Zoltán
Szabó, Csaba
Szakács, László
Sziklai, Péter
Szőnyi, Tamás
Végh, László
Vértesi, Vera
Vesztergombi, Katalin
Weiner, Zsuzsanna
Starting date 2007-01-01
Closing date 2010-06-30
Funding (in million HUF) 59.900
FTE (full time equivalent) 36.92
state closed project
Summary in Hungarian
A matematikát két fő ágra szokás osztani: folytonosra és diszkrétre. Ez a felosztás azonban több szempontból félrevezető. Egyrészt a matematika fejlődését nagy mértékben befolyásoló természettudományok sok olyan jelenséget vizsgálnak, melyet diszkrét és folytonos módon is lehet modellezni és a két modell csak együtt képes valamennyire leírni a jelenséget, másrészt rengeteg alapvető módszert ismerünk, melynek van diszkrét és folytonos megfelelője.

Jelen projekt olyan módszerek vizsgálatával/alkalmazásával/továbbfejlesztésével kíván foglalkozni, melyet a diszkrét matematika tanult a folytonostól vagy fordítva, és melynek megjelenése a kérdéses területen sok nyitott problémánál hozott áttörést.

A kérdéses trükkök megértéséhez és használatához több matematikai ág ismeretére van szükség, ezért a projektben különböző területekről jövő kutatóknak kell együtt dolgozniuk. Sok olyan publikáció van már, melynek szerzői közt a pályázat több tagja szerepel jelezve, hogy ez a közös munka lehetséges.

Az eredményeket (a matematikában megszokott módon) folyóirat-közleményekben és konferenciaelőadásokon kívánjuk ismertetni. A résztvevők korábbi tevékenysége mutatja, milyen gyümölcsöző hatása lehet egy új módszer elterjedésének egy adott területen.

A szenior résztvevők Ph.D. diákjai közül is részt vennének néhányan a pályázatban, így fiatal kutatóknak már pályájuk elején lehetősége nyílna területük határainak szélesítésére és más területek fő problémáinak megismerésére.
Summary
Traditionally mathematics is divided to two main branches: discrete and continuous. This division is misleading for several reasons. On the one hand, natural sciences (which have always provided the main motivating problems for mathematics) study phenomena that have both discrete and continuous models and the two different models together yield a better understanding of the problem in question; on the other hand, we know a lot of methods for which there is a discrete and a continuous version.

In this project we wish to understand/apply/develop methods, that discrete mathematics learned from the continuous or vice versa, and the application of which turned out to be crucial in attacking problems that seemed to be hopeless previously.

To understand these ideas, one needs to know several branches of mathematics, hence in the project people of different background will have to cooperate. There exist already many publications with several authors of our project showing that these people can work together.

As it is usual in mathematics, we want to publish our results in international mathematical journals and give conference talks about them. Previous results of the participants show that sometimes spreading a new method in the mathematical community can be very fruitful.

There would also be Ph.D. students of the senior participants taking part in the project. This could help young researchers to widen their background already at the beginning of their carrier and also helps them understand the most improtant problems of other areas of mathematics.




 

Final report

  
Results in Hungarian
Sok eredmény született a gráfok növekvő konvergens sorozataival és azok limesz-objektumaival, ill. az ezek vizsgálatára szolgáló gráf-algebrákkal kapcsolatban. Kidolgozásra kerültek a nagyon nagy sűrű gráfok (hálózatok) matematikai elméletének alapjai, és ezek alkalmazásai az extremális gráfelmélet területén. Aktív és eredményes kutatás folyt a diszkrét matematika más, klasszikus matematikai területekkel való kapcsolatával kapcsolatban: topológia (a topológiai módszer alkalmazása gráfok magjára, ill a csomók elmélete), geometriai szerkezetek merevsége (a Molekuláris Sejtés bizonyítása 2 dimenzióban), diszkrét geometriai (Bang sejtésének bizonyítása), véges geometriák (lefogási problémák, extremális problémák q-analogonjai), algebra (félcsoport varietások, gráfhatványok színezése), számelmélet (additív számelmélet, Heilbronn probléma), továbbá gráfalgoritmusok (stabilis párosítások, biológiai alkalmazások)) területén.
Results in English
Several results were obtained in connection with convergent growing sequences of graphs and their limit objects, and with graph algebras facilitating their study. Basic concepts for the study of very large dense graphs were worked out, along with their applications to extremal graph theory. Active and successful research was conducted concerning the interaction of discrete mathematics with other, classical areas of mathematics: topology (applications of topology in the study of kernels of graphs, and the theory of knots), rigidity of geometric structures (proof of the Molecular Conjecture in 2 dimensions), discrete geometry (proof of the conjecture of Bang), finite geometries (blocking problems, q-analogues of extremal problems), algebra (semigroup varieties, coloring of graph powers), number theory (additive number theory, heilbronn problem), and graph algorithms (stable matchings, applications in biology).
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=67867
Decision
Yes





 

List of publications

  
P.P. Pach, Cs. Szabó: On the minimal distance of a polynomial code, Discrete Mathematics and Theoretical Computer Science special issue, to appear, 2010
Gábor Iván, Zoltán Szabadka, Vince Grolmusz: A Hybrid Clustering of A Hybrid Clustering of Protein Binding Sites, FEBS Journal, Vol. 277, No. 6. pp. 1494-1502., 2010
B. Dorn, V. Keicher, E. Sikolya: Asymptotic periodicity of recurrent flows in infinite networks, Math. Z. 263, 69-87., 2009
K.-J. Engel, M. Kramar Fijavž, B. Klöss, R. Nagel, E. Sikolya: Maximal controllability for boundary control problems, Applied Mathematics and Optimization, to appear, 2010
E. Horváth, G. Horváth, Z. Németh, Cs. Szabó: The number of square islands on a rectangular sea, Acta Sci. Math., to appear, 2010
L. Lovász, B. Szegedy: Random graphons and a weak Positivstellensatz for graphs, http://arxiv.org/abs/0902.1327, 2009
L. Lovász: Very large graphs, Current Developments in Mathematics 2008, International Press, Somerville, MA, 67-128., 2009
G. Elek, G. Lippner: Sofic equivalence relations, J. Func. Anal., elfogadva, 2009
G. Elek, G. Lippner: Borel oracles. An analytical approach to constant-time algorithms, Proc. Amer. Math. Soc., elfogadva, 2009
T. Király, J. Pap: A note on kernels and Sperner's Lemma, Discrete Applied Mathematics, Volume 157, Issue 15, 3327-3331., 2009
T. Király, J. Pap: Kernels, stable matchings, and Scarf's Lemma, RIMS Kôkyuroku Bessatsu, elfogadva, 2009
Z. Király: Maximum Number of Cycles and Hamiltonian Cycles in Sparse Graphs, 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, 2009
G. Iván, Z. Szabadka, V. Grolmusz: A hybrid clustering of protein binding sites, FEBS Journal, elfogadva, 2009
G. Iván, Z. Szabadka, V. Grolmusz: On the asymmetry of the residue compositions of the binding sites on protein surfaces, Journal of Bioinformatics and Computational Biology, Vol. 3 No. 10, 413-414, 2009
D. Bánky, R. Ördög, V. Grolmusz: NASCENT: An automatic protein interaction network generation tool for non-model organisms, Bioinformation, Vol. 3 No. 8, 361-363, 2009
R. Ördög, V. Grolmusz: On the bond graphs in the Delaunay-tetrahedra of the simplicial decomposition of spatial protein structures, Proceedings of the International Workshop on Practical Applications of Computational Biology & Bioinformatics (IWPACBB'09), LNCS 5518, 2009
G. Iván, Z. Szabadka, R. Ördög, V. Grolmusz, G. Náray-Szabó: Four spatial points that define enzyme families, Biochemical and Biophysical Research Communications, Vol. 383, No. 4, 417-420, 2009
Gy. Károlyi: The polynomial method in additive combinatorics, Combinatorial Number Theory and Additive Group Theory, Advanced Courses in Mathematics CRM Barcelona, Birkhauser, pp. 267-277, 2009
G. Kun, M. Szegedy: A new line of attack on the dichotomy conjecture, 41st Symposium on the Theory of Computing, 725-734, 2009
G. Kun, B. Larose: Stable sets of maximal size in Kneser-type graphs, European Journal of Combinatorics, , Vol. 30 (1), 17-29, 2009
K.J. Böröczky, B. Csikós: A new version of L. Fejes Tóth's Moment Theorem, Studia Sci. Hung., to appear, 2010
Z. Daróczy, M. Laczkovich: On functions taking the same value on many pairs of points, Real Analysis Exch. 33 (2), 385-393, 2008
A. Blokhuis, A. E. Brouwer, T. Szőnyi: Covering all points except one, Journal of Algebraic Combinatorics, elfogadva, 2009
N. Harrach, K. Metsch, T. Szőnyi, Zs. Weiner: Small pointsets of PG(n,p^{3h}), intersecting each line in 1 mod p^h point, J. of Geometry, benyújtva, 2009
B. Csikós, Gy. Kiss, K.J. Swanepoel, O. de Wet: Large antipodal families, Periodica Mathematica Hungarica, 58(2), 129-138, 2009
G. Kós, P. Ligeti, P. Sziklai: Reconstructing matrices from submatrices, Math. Comput., 78, 1733-1747., 2009
M. Lavrauw, L. Storme, P. Sziklai, G. Van de Voorde: An empty interval in the spectrum of small weight codewords in the code from points and k-subspaces of PG(n,q), J. Combin. Th. Ser A., elfogadva, 2009
A. Gács, T. Szőnyi, Zs. Weiner: Characterizing small weight codewords of the linear code of PG(2,q), kézirat, 2009
A. Gács, T. Héger: On (k,6)-graphs arising from projective planes, kézirat, 2009
L. Lovász, L. Szakács: Limits of multigraphs, in preparation, 2009
D. Pálvölgyi, G. Tóth: Convex polygons are cover-decomposable, Discrete & Computational Geometry 43(3), 483-496, 2010
Gy. Kiss, P.O. de Wet: Notes on the illumination parameters of convex polytopes, Contrib. Discrete Math., to appear, 2010
Gy. Kiss, B. Csajbók: Notes on semiarcs, Mediterr. J. Math., to appear, 2010
D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, D. Pálvölgyi, B. Patkós: Polychromatic colorings of arbitrary rectangular partitions, Discrete Mathematics 310, 21-30., 2010
L. A. Végh: Augmenting undirected node-connectivity by one, Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC) 2010, pp. 563-572., 2010
T. Harks, L. A. Végh: Nonadaptive selfish routing with online demands, CAAN 2007, pp. 27-45, 2007
G. Elek, G. Lippner: Borel oracles. An analytical approach to constant time algorithms, Proc Amer Math Soc 138, 2939-2947., 2010
Gy. Károlyi: Incidence geometry in combinatorial arithmetic. In memoriam Gyorgy Elekes, Eotvos Annales, to appear, 2010
G. Harcos, Gy. Károlyi, G. Kós: Remarks to Arsovski's proof of Snevily's conjecture, Eotvos Annales, to appear, 2010
K.J. Böröczky, B. Csikós: Approximation of smooth convex bodies by circumscribed polytopes with respect to the surface area, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 79(2), 229-264, 2009
L. Lovász, Balázs Szegedy: Left and right convergence of graphs with bounded degree, submitted, http://arxiv.org/abs/1002.0115, 2010
L. Lovász, B. Szegedy: Random Graphons and a Weak Positivstellensatz for Graphs, submitted, http://arxiv.org/abs/0905.3806, 2010
L. Lovász: Subgraph densities in signed graphons and the local Sidorenko conjecture, http://arxiv.org/abs/1004.3026, 2010
P. Valtr, G. Lippner, Gy. Károlyi: Empty convex polygons in almost convex sets, Periodica Mathematica Hungarica 55 (2007) 121-127, 2007
Gy. Károlyi, T. Keleti, G. Kós, I. Z. Ruzsa: Periodic decomposition of integer valued functions,, Acta Mathematica Hungarica, 119 (2008) 227-242, 2008
G. Horváth, Ch. L. Nehaniv, Cs. Szabó: An assertion concerning functionally complete algebras and NP-completeness, Theoretical Computer Science, 407, 591-595., 2008
D. Pálvölgyi: Sequential search using question-sets with bounded intersections, Journal of Statistical Theory and Practice Vol 1, Num 2, 2007
D. Pálvölgyi, B. Keszegh, J. Pach, and G. Tóth: Drawing cubic graphs with at most five slopes, Graph Drawing 2006, Lecture Notes in Computer Science 4372, Springer, 2007, 114-125., 2007
K. Böröczky, K.J. Böröczky: Polytopes of minimal volume with respect to a shell - another characterization of the octahedron and the icosahedron, Disc. Comp. Geom., 38, 231-241., 2007
K. Böröczky, K.J. Böröczky: A stability property of the octahedron and the icosahedron, Publ. Math. Debrecen, 71, 449-466., 2007
A. Frank, Z. Király, B. Kotnyek: An algorithm for node-capacitated ring routing, Operations Research Letters, 35, Issue 3, pp. 385-391, 2007
Z. Király: $\lambda$-supermodular functions, The 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, April 3-5, 2007, Sendai, 2007
A. Gács, T. Szőnyi: Random constructions and density results, Designs, Codes and Cryptography, 47 (2008), no. 1-3, 267--287., 2008
G. Pluhár, Cs. Szabó: The free spectrum of the variety of bands, Semigroup Forum, to appear, 2007
G. Pluhár, J. Wood: The free spectra of varieties generated by idempotent semigroups, Algebra and Discrete Mathematics (2008) 89-100, 2008
K. Kátai, Cs. Szabó: The pn sequence of semigroup varieties generated by combinatorial 0-simple semigroups, Algebra Universalis, 59 (2008) 435-446, 2008
G. Korchmáros, T. Szőnyi: Affinely regular polygons in an affine plane, Contributions to Discrete Math. (electronic), 3 (2008), no. 1, 20--38., 2008
G. Korchmáros, T. Szőnyi: Egy egyszerű transzformációval származtatott nem-desarguesi affin sík, KöMaL 57, 258-266., 2007
T. Király: Applications of Eulerian splitting-off, Proceedings of 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 298-307., 2007
T. Király, J. Pap: Total dual integrality of Rothblum's description of the stable marriage polyhedron, Mathematics of Operations Research, to appear, 2007
G. Kun, V. Vértesi: The membership problem in finite hypergraph algebras, International Journal of Algebra and Computation 17, pp. 449-459, 2007
G. Kun, C. Tardif: Duals and homomorphisms of random paths, European Journal of Combinatorics, to appear, 2009
G. Kun, J. Nesetril: Lifts and shadows (NP and CSP for combinatorialists), European Journal of Combinatorics, to appear, 2007
G. Kun, J. Nesetril: NP for combinatorialists, EUROCOMB07, to appear, 2007
G. Kun, J. Nesetril: NP by means of lifts and shadows, 32nd International Symposium on Mathematical Foundations of Computer Science, to appear, 2007
Z. Szabadka, G. Iván, V. Grolmusz: Analyzing the Residue-Composition of Metal Binding Sites in the Whole Protein Data, Bank. Mol. Biol. Cell 17(suppl), 535. (CD-ROM), 2007
Z. Szabadka, V. Grolmusz: High Throughput Processing of the Structural Information of the Protein Data Bank, Journal of Molecular Graphics and Modeling, 25, pp. 831-836, 2007
Z. Szabadka, R. Ördög, V. Grolmusz: The Ramachandran Map of More Than 6,500 Perfect Polypeptide Chains, Biophysical Reviews and Letters, to appear, 2007
Z. Szabadka, R. Ördög, V. Grolmusz: Analyzing the Simplicial Decomposition of Spatial Protein Structures, BMC Bioinformatics, to appear, 2007
Z. Szabadka, G. Iván, V. Grolmusz: Being a Binding-Site: Characterizing Residue-Composition of Binding Sites on Proteins, Bioinformatics, to appear, 2007
Gy. Kiss: A survey on semiovals, Contrib. Discrete Math., 3 (2008), 81-95., 2008
K.-J. Engel, M. Kramar Fijavz, R. Nagel, E. Sikolya: Vertex control of flows in networks, Networks and Heterogeneous Media 3, 709-722, 2008
C. Borgs, J. Chayes, L. Lovász, V. T. Sós, K. Vesztergombi: Convergent Graph Sequences I: Subgraph frequencies, metric properties, and testing, Advances in Math. 219 (2008), no. 6, 1801--1851., 2008
C. Borgs, J.Chayes, L. Lovász, V.Sós, K.Vesztergombi: Convergent Graph Sequences II: Multiway Cuts and Statistical Physics, submitted, 2009
L. Lovász, A. Schrijver: Graph parameters and semigroup functions, European J. Combin. 29, no. 4, 987-1002., 2008
L. Lovász, B. Szegedy: Szemerédi's lemma for the analyst, Geom. Funct. Anal. 17, no. 1, 252-270., 2007
L. Lovász, B. Szegedy: Testing properties of graphs and functions, Isr. J. Math. (to appear), 2009
C.Borgs, J.Chayes, L. Lovász: Moments of Two-Variable Functions and the Uniqueness of Graph Limits, arXiv:0803.1244; submitted, 2009
L. Lovász, B. Szegedy: Finitely forcible graphons, arXiv:0901.0929, 2009
R. Ördög, V. Grolmusz: Evaluating Genetic Algorithms in Protein-Ligand Docking, Lecture Notes in Computer Science, Volume 4983/2008, page 402-413, 2008
R. Ördög, Z. Szabadka, V. Grolmusz: Analyzing the Simplicial Decomposition of Spatial Protein Structures, BMC Bioinformatics, 2008, 9(Suppl 1):S11(doi:10.1186/1471-2105-9-S1-S11), http://www.biomedcentral.com/1471-2105/9/S1/S11, 2008
R. Ördög: PyDeT, a PyMOL plug-in for visualizing geometric concepts around proteins, Bioinformation. 2008; 2(8): 346-347., 2008
V. Grolmusz: Modular Representations of Polynomials: Hyperdense Coding and Fast Matrix Multiplication, IEEE Transactions on Information Theory.Volume 54, Issue 8, Aug. 2008 Pages:3687 - 3692; Digital Object Identifier 10.1109/TIT.2008.926346, 2008
K. Kátai, Cs. Szabó: The pn sequence of semigroup varieties generated by combinatorial 0-simple semigroups, Algebra Universalis, 59 (2008) 435-446, 2008, 2008
B. Bollobas, G. Kun, I. Leader: Cops and robbers in random graphs, J. of Comb. Theory, Series B, elfogadva, 2009
G. Kun, C. Tardif: Duals and homomorphisms of random paths, European Journal of Combinatorics, 2009, 2009
V. Vértesi: Transversely nonsimple knots, Algebr. Geom. Topol. 8 (2008), no. 3, 1481--1498., 2009, 2008
V. Vértesi, A. Stipsicz: On invariants for Legendrian knots, Pacific J. Math. 239 (2009), no. 1, 157--177., 2009
G. Horváth: Szóprobléma nem feloldható csoportok fölött, Matematikai Lapok, 13 (2006/07) No. 2, 20-27, 2008
G. Horváth: Véges csoportok azonosságai, Matematikai Lapok, 13 (2006/07) No. 2, 12-19, 2008
G. Pluhár: A mérgezett csokoládé rejtélye, Matematikai Lapok, 13 (2006/07) No. 2, 27-34, 2008, 2008
G. Pluhár: Szavak száma idempotens félcsoportokban, Matematikai Lapok, 13 (2006/07) No. 2, 44-53, 2008, 2008
V. Vértesi, P. Svetlana: Azonosságok 0-egyszerű félcsoportokban, Matematikai Lapok, 13 (2006/07) No. 2, 54-75, 2008, 2008
Gy. Károlyi, V. Rosta: On geometric graph Ramsey numbers, Graphs and Combinatorics, 25, 351-363, 2009
Gy. Károlyi: Forbidden order types, Oberwolfach Reports (OWR) 44/2008, pp 11-12, 2008
Gy. Kiss, S. Marcugini, F. Pambianco: Semiovals in projective planes of small order, Proceedings of Algebraic and Combinatorial Coding Theory, Eleventh International Workshop, June 16-22, 2008, Pamporovo, Bulgaria, 151-154., 2008
K. Bezdek, Gy. Kiss: On the $X$-ray number of almost smooth convex bodies and of convex bodies of constant width, Canad. Math. Bull., elfogadva., 2009
B. Csikós, Gy. Kiss, K.J. Swanepoel, P.O. de Wet: Large antipodal families, Periodica Mathematica Hungarica, 58(2), pp. 129-138, 2009
A. Gács, L. Lovász, T. Szőnyi: Directions in AG(2,p^2), Innovations in Incidence Geometry, 6/7, 189-2001., 2008
Z. Király: Better and Simpler Approximation Algorithms for the Stable Marriage Problem, Lecture Notes in Computer Science 5193, (2008), pp. 623-634, 2008
A. Bernáth, S. Iwata, T. Király, Z. Király, Z. Szigeti: Recent results on well-balanced orientations, Discrete Optimization 5, (2008), pp. 663-676, 2008
Z. Király, J. Szabó:: Induced graph packing problems, Graphs and Combinatorics, elfogadva, 2009
S. Ball, A. Gács: On the graph of a function over a prime field whose small powers have bounded degree, Europan Journal of Combinatorics, to appear, 2009
A. Gács, T. Héger: On geometric constructions of (k,g)-graphs, Contributions to Discrete Mathematics, 3 (2008) 63-80, 2008
C. Borgs, J.T. Chayes, L. Lovász, V. T. Sós, K. Vesztergombi: Limits of randomly grown graph sequences, (submitted), 2009




 

Events of the project

  
2011-02-22 14:23:37
Résztvevők változása
2010-06-17 10:23:48
Résztvevők változása
2009-07-17 14:18:18
Résztvevők változása
2009-05-12 15:06:52
Résztvevők változása



Back »