Decomposition of graphs is an important tool for the design ofalgorithms as well as for understanding their structure.Hyperfiniteness means that the graph can be decomposed into pieces ofbounded size by removing an arbitrarily small fraction of the edges.This property, which can be defined for a family of finite graphs,but also for graph-limits with bounded degree called "graphings", isvery useful in designing local algorithms for such graphs. But theoptimal decomposition is difficult to compute. We show how methodsfrom combinatorial optimization, namely linear relaxation, can beused to prove basic properties of hyperfiniteness, and also to obtaina decomposition that is almost optimal.
About the speaker
About the speaker
László Lovász was born on March 9, 1948 in Budapest, Hungary. He is
married, has 4 children. He obtained his doctoral degree in
mathematics from the Eötvös Loránd University, in Budapest, Hungary
in 1971. He is a member of the Hungarian Academy of Sciences, the US
National Academy of Sciences and several other Academies. He held the Chair of Geometry at the University of Szeged (1975-1982)
and the Chair of Computer Science at the Eötvös Loránd University
(Budapest, 1983-1993). He was A.D. White Professor-at-Large at Cornell
University (1982-1987), Professor of Mathematics and Computer Science
at Yale University (1993-1999), Senior/Principal Researcher at
Microsoft Research (1999-2006), Director of the Mathematical
Institute of the Eötvös Loránd University (2006-2011), and since 2014, he is the President of the Hungarian Academy of Sciences. His awards include the George Polya Prize (1979), the Ray D.Fulkerson
Prize (1982), the Brouwer Medal of the Dutch Mathematical Society
(1993), the Wolf Prize (1999), the Knuth Prize (1999), the Gödel
Prize (2001), and the Kyoto Prize (2010). He is editor-in-chief of
Combinatorica and editor of 12 other Journals. His field of research is discrete mathematics, in particular its
applications to the theory of algorithms and the theory of computing,
discrete probability, and its interactions with classical mathematics. He wrote 5 research monographs and 4 textbooks, and over 250 research papers.
László Lovász was born on March 9, 1948 in Budapest, Hungary. He is
married, has 4 children. He obtained his doctoral degree in
mathematics from the Eötvös Loránd University, in Budapest, Hungary
in 1971. He is a member of the Hungarian Academy of Sciences, the US
National Academy of Sciences and several other Academies. He held the Chair of Geometry at the University of Szeged (1975-1982)
and the Chair of Computer Science at the Eötvös Loránd University
(Budapest, 1983-1993). He was A.D. White Professor-at-Large at Cornell
University (1982-1987), Professor of Mathematics and Computer Science
at Yale University (1993-1999), Senior/Principal Researcher at
Microsoft Research (1999-2006), Director of the Mathematical
Institute of the Eötvös Loránd University (2006-2011), and since 2014, he is the President of the Hungarian Academy of Sciences. His awards include the George Polya Prize (1979), the Ray D.Fulkerson
Prize (1982), the Brouwer Medal of the Dutch Mathematical Society
(1993), the Wolf Prize (1999), the Knuth Prize (1999), the Gödel
Prize (2001), and the Kyoto Prize (2010). He is editor-in-chief of
Combinatorica and editor of 12 other Journals. His field of research is discrete mathematics, in particular its
applications to the theory of algorithms and the theory of computing,
discrete probability, and its interactions with classical mathematics. He wrote 5 research monographs and 4 textbooks, and over 250 research papers.
