6th HLF – Laureate Lectures: On the early history of Expanders
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 37 | |
| Autor | ||
| Lizenz | Keine Open-Access-Lizenz: Es gilt deutsches Urheberrecht. Der Film darf zum eigenen Gebrauch kostenfrei genutzt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden. | |
| Identifikatoren | 10.5446/40173 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
00:00
Elektronisches ForumExpandierender GraphGrundsätze ordnungsmäßiger DatenverarbeitungFormation <Mathematik>Fields-MedaillePhysikalische TheorieErgodentheorieTaylor-ReiheDatenstrukturZweiMathematikBeobachtungsstudieGruppenoperationElementare ZahlentheorieTheoretische InformatikAnalysisComputeranimation
01:20
Web-SeiteUnternehmensarchitekturSoftwareTheoretische InformatikElektronisches ForumTaylor-ReiheKalkülMathematikMultiplikationsoperatorInformatikMathematikerinPhysikalische TheorieKomplex <Algebra>KonzentrizitätComputeranimation
02:55
Hill-DifferentialgleichungMicrosoft dot netCAN-BusParametersystemFunktion <Mathematik>Ein-AusgabeGebäude <Mathematik>MereologieKonzentrizitätp-BlockKategorie <Mathematik>Taylor-ReiheGraphComputeranimation
04:28
PrimzahlzwillingeE-LearningMathematikSoftwareEin-AusgabeFunktion <Mathematik>GraphKonzentrizitätPhysikalische TheorieZahlenbereichStrömungsrichtungSchnittmengeComputeranimation
07:27
InformationQuantisierung <Physik>Uniformer RaumEinfach zusammenhängender RaumKategorie <Mathematik>Ein-AusgabeSchnittmengeFunktion <Mathematik>MehrrechnersystemTeilmengeVererbungshierarchieKonzentrizitätCASE <Informatik>Computeranimation
10:04
FarbverwaltungssystemKonzentrizitätSymmetrische MatrixTopologieKategorie <Mathematik>Konstruktor <Informatik>Physikalische TheorieVorlesung/Konferenz
11:09
BORIS <Programm>RechenwerkSpieltheorieMaß <Mathematik>TorusNebenbedingungKonzentrizitätAbgeschlossene MengeDatentransferZahlenbereichVererbungshierarchiePhysikalische TheorieKollaboration <Informatik>Lokales MinimumGebundener Zustandt-TestSchätzfunktionInformationComputeranimation
13:56
Lokales MinimumPrimzahlzwillingeWeb-SeiteNP-hartes ProblemRechenwerkResultanteMIDI <Musikelektronik>SchätzfunktionFehlermeldungComputeranimation
14:39
RechenwerkMachsches PrinzipTeilbarkeitGraphBipartiter Graphp-BlockKategorie <Mathematik>Konstruktor <Informatik>Funktion <Mathematik>Coxeter-GruppeEin-AusgabeTaylor-ReiheGebäude <Mathematik>KonstanteSchätzfunktionComputeranimation
17:04
Funktion <Mathematik>Ein-AusgabeRelativitätstheorieZahlenbereichKreisbogenTaylor-ReiheComputeranimation
18:05
Innerer PunktPrimzahlzwillingeRelativitätstheorieFunktion <Mathematik>Ein-AusgabeJensen-MaßBetafunktionKonstruktor <Informatik>Bipartiter GraphKonzentrizitätUnendlichkeitCASE <Informatik>Taylor-ReihePRINCE2NummernsystemComputeranimationVorlesung/Konferenz
20:59
Disk-ArraySichtenkonzeptRechenwerkQuilt <Mathematik>Uniformer RaumTaylor-ReiheJensen-MaßZahlenbereichPhysikalische TheorieFunktion <Mathematik>SchnittmengeBetafunktionRandwertGrenzwertberechnungEin-AusgabeKategorie <Mathematik>Element <Gruppentheorie>TeilmengeKnotenmengeIdentifizierbarkeitFinitismusTVD-VerfahrenGraphCASE <Informatik>Dienst <Informatik>Zellularer AutomatZeichenvorratAnalysisSystemidentifikationComputeranimationVorlesung/Konferenz
25:33
RechenwerkPhysikalische TheorieBefehl <Informatik>ParametersystemTypentheorieExistenzsatzZahlenbereichJensen-MaßTaylor-ReiheSchätzfunktionZeichenvorratKonstruktor <Informatik>UnendlichkeitFunktion <Mathematik>Ein-AusgabeBetafunktionStandardabweichungComputeranimation
28:18
Kartesische KoordinatenVorzeichen <Mathematik>ViereckSummierbarkeitE-MailExistenzsatzPhysikalische Theoriep-adische ZahlBefehl <Informatik>Kategorie <Mathematik>BildschirmmaskeKonstruktor <Informatik>MultiplikationTopologieQuaternionGalois-FeldZahlenbereichMathematikRelativitätstheorieVarietät <Mathematik>GruppenoperationDigitalisierungPrimzahlMultiplikationsoperatorReelle ZahlTaylor-ReiheDezimalzahlKreisflächeRechter WinkelPunktspektrumNichtlinearer OperatorAutomorphismusVererbungshierarchieTheoremFinitismusEndliche GruppeComputeranimation
34:06
FarbverwaltungssystemMenütechnikHIP <Kommunikationsprotokoll>DatentransferAnalogieschlussSichtenkonzeptMathematikDruckverlaufPhysikalische TheorieMultiplikationsoperatorTaylor-ReiheGüte der AnpassungSondierungKonstruktor <Informatik>MathematikerinPunktKategorie <Mathematik>ZahlenbereichExistenzsatzDatenfeldBeweistheorieInformationSchätzfunktionComputeranimation
39:46
Elektronisches ForumSchätzfunktionTaylor-ReiheKartesische KoordinatenLogistische VerteilungKonstruktor <Informatik>MinimalgradVersionsverwaltungHilfesystemKategorie <Mathematik>MAPMultiplikationsoperatorQuaternionKnotenmengeGrenzschichtablösungEndliche ModelltheorieMultigraphRegulärer GraphGüte der AnpassungBeweistheoriePrimzahlPortscannerTypentheorieParametersystemExistenzsatzZentrische StreckungBinärdatenInformatikTeilbarkeitBipartiter GraphRandomisierungGraphDimensionsanalyseUmsetzung <Informatik>Formation <Mathematik>ZahlenbereichStichprobenumfangMixed RealityTheoretische InformatikTrigonometrische FunktionLoginPunktspektrumMathematikNeuroinformatikAnalytische FortsetzungGroße VereinheitlichungDreiecksfreier GraphExpertensystemRelativitätstheorieComputeranimation
Transkript: Englisch(automatisch erzeugt)
00:23
Pleasure to welcome you for the second session this morning. My name is Anna Wienhard. I'm a professor of mathematics here at the University of Heidelberg and at the Heidelberg Institute for Theoretical Studies and a member of the Scientific Committee of the HLF. And it's my great pleasure to introduce to you the first speaker of the second session,
00:41
Gregory Margulis, who got his Fields Medal in 1978 for his work on the innovative analysis of the structure of league groups. He has actually influenced mathematics in many other ways, introducing ergodic theory in the study of number theory and also in constructing one of the first known expanders,
01:01
a theory which became quite popular in mathematics and theoretical computer science. And in his talk, he will tell us about the early history of expanders. Yeah, thank you very much for the introduction.
01:22
So it's my first time when I participate in Heidelberg forum. So now theory of expanders is quite is very popular. And so I have a colleague at Yale, Dan Spearman, who is one of the winners of the prize.
01:53
And he's a computer science department. And he once gave a colloquium talk at in the mathematics department.
02:01
And if I remember correctly, he said that after calculus, the theory of expanders is the most important contribution by mathematicians to theoretical computer science.
02:21
So it's, yeah, probably it's an exaggeration, but just I want to mention that. So from, so it's initially the theory of expanders was motivated by certain problems
02:45
in telephone network theory. And so there was a paper by Mark Pinsker, which is on the complexity of concentrator
03:01
from 1973, which he constructed concentrators with certain properties. And one of the main building blocks was where expanders. So maybe let me start with the definition of a concentrator.
03:26
So there's some parameters attached to this notion. So an M concentrator is a graph with, there's N inputs and M outputs, and such that, so
03:48
M is less than N, such that if we choose any M inputs, then they can be connected by non-intersecting paths to the outputs, or in other ways, we choose M inputs, then
04:12
there is a paths which, okay, so each input is connected to some output, and thereby
04:24
some path, and these paths are the joint. Okay, so it follows from the definition of the, this N M concentrator, if we choose any
04:44
K inputs, where K is not greater than M, then there are K paths which start at this K inputs, and they will be non-intersecting and which end at outputs.
05:02
But it's not, so it's not claimed that this K output somehow will be something which we can prescribe before. Okay, so now there is a, so the notion of concentrator somehow was motivated by
05:28
some problems in telephone network theory. Now, there's a somewhat related notion which is called super concentrator, and it was
05:47
introduced by Pippinger in 1977, so super concentrator is a graph where we have the
06:08
same number inputs and outputs, so N inputs and N outputs, such that you would take any K, you would fix some K which is less than, not greater than N, and take K inputs
06:32
and K outputs that they can be connected by non-intersecting paths.
06:44
So it means that we start with each of these K inputs, then draw some, can draw
07:01
some inputs and outputs, and this path should be the joint. So it's, the notion of the super concentrator in some sense is more elegant and more symmetric, so it's somehow there's a, you can interchange inputs and outputs.
07:37
Yes, so it's, you know, now some remarks about these connections between super concentrators
07:49
and concentrators. So you will have a super concentrator with, okay, N inputs and N outputs, and if we
08:01
choose some, any N which is not greater than N, and then fix some, and then choose some subset of outputs, choose some N outputs, and just forget about other outputs, then
08:27
we, it's clear that we get N M concentrator. But yeah, so actually this N M concentrator, which we obtain, has some additional property,
08:46
which is if we fix some K, which is K is, K is not greater than M, and choose some
09:01
K inputs, and then choose another K outputs from this N M concentrator, then we can connect this chosen K inputs with chosen K outputs by non-intersecting paths.
09:25
So this is somehow additional property which we didn't have in the definition of N M concentrator. N M concentrator we chose a set of K inputs, somehow they can be connected to outputs
09:42
by the joined paths, but what we get at the end somehow is not fixed. So it's, so now somehow it's, because we have this additional property, which we
10:10
usually don't have in N M concentrators, it's kind, it's not likely that super concentrator
10:22
can be obtained by some, by some obvious construction from concentrator. So it's, you know, so as I said super concentrators is kind of maybe more symmetric, more elegant,
10:45
and somehow it's, and it's, so it's really kind of generalize or relate the notion
11:01
to the concentrator with some additional properties. Okay, so now it's, now it's somehow one of the problems in theory of concentrators
11:46
and super concentrators is to find some good upper bounds for the number of edges in this concentrators and super concentrators.
12:03
And so this is, was the problem which Pinsker considered in the paper, which was mentioned
12:21
at the beginning. So it's, yeah actually quite, most of this historic information which I now describe was provided to me by Leonid Busaliga, who was my colleague at the Institute of Problems
12:42
Information Transmission, and he's maybe four years older than me, and he sent me some historical notes. And he was a close collaborator of Mark Pinsker and also he was one of the last students
13:03
of Kolmogorov. And so apparently the, Busaliga told Pinsker about this problem of finding concentrators
13:22
with smallest, okay, to get some upper bounds on the number of edges which should be in the concentrator, in a concentrator. So at that time, so it's probably it's about 1971, it was known that, say we denote this
13:49
minimum number by c of n, then this, okay, there is a low estimate which is kind
14:04
of obvious, but there's an upper estimate that c of n is not greater than 4n log n. So this upper bound probably, as Busaliga wrote to me, is follows from some earlier
14:30
results which were obtained independently in mid-60s by Offman and Banish.
14:47
Okay, so now, so there's this factor, okay, log n, and somehow Pinsker was able
15:01
to eliminate this factor, and he showed that this c of n is actually is not greater than cn, where c is not greater than 29.
15:22
Maybe by now it's known, there's some better estimates for this constant. Okay, now I'll just, now we can go to expanders.
15:43
So the Pinsker construction actually quite ingenious, and so it presents some kind of multi-level scheme, multi-level graph, but kind of build and block is what Pinsker
16:04
called NRM expanders. So it's NRM expander is a bipartite graph with n inputs and r outputs.
16:22
So it's, okay, so r is between m and n, so m is less than r and r is less than n with the following property. So for every k which is not greater than m, we, so r, so we can connect the connected
17:15
paths with at least k, so they can connect it with k outputs, no, r connected with
17:31
at least k outputs, so it's, you know, so actually, so why it's called an expander,
17:43
because it's, so how we have the same k inputs and the same arc number of outputs, so it's, in some sense there is no expansion, but one has to notice that this r is less
18:02
than n, so the relative size of this, of outputs actually will be bigger than the relative size of inputs.
18:25
So it's, so Pinsker used this definition for this notion of m, r, n expander to construct
18:45
large concentrators. Now for some other problems in, like super concentrators and also construction of a non-bewalking
19:16
schemes, so Basilega, Pinsker, and Pinsker used more elaborate definition of an expander,
19:31
and so this is the following. So it's, it's, so we consider bipartite graph with n inputs and mu and outputs where mu
19:56
is between zero and infinity, and so this bipartite graph is called alpha beta expander,
20:14
so it's alpha is less than one, so it's mu is between alpha and beta.
20:27
If any k inputs, where k is not greater than alpha n, so we choose some portion of the inputs, are connected with at least beta k outputs, so we have, so here we really
20:54
have, it's clear that here, here we have expansion.
21:15
Now it's, so this was initially there was alpha beta expenders and there was this mu.
21:29
Now it's usually assumed that mu is one, that in the theory of expenders, so we have the same number of inputs and outputs, and in this case, so it's, we can actually,
22:00
so we have the same number of inputs and outputs, we can identify inputs and outputs,
22:06
and then it's, we can somehow reformulate the notion of expander, and so in, so under
22:23
the assumption that number of inputs and number of outputs is the same, so it can be, and we have this identification, then we can say that alpha beta expander is, so alpha
22:41
is between zero and one, and beta is greater than one, is a finite non-oriented graph with n vertices, and with the following property, that every set of k vertices, so k is again
23:09
is not greater than alpha n, it's connected with at least beta minus one multiplied by
23:28
k of vertices outside of this set k, so maybe some explanation, so we have this non-oriented
23:43
graph, so then for every set, subset of vertices, we can define some kind of a notion of a boundary, so boundary will be actually is not in the set, but it will be all vertices
24:08
outside of the set, which are connected by an edge with some element from the set, and so then there is this property that every, you would take this, so every set of k vertices,
24:33
the k is less than alpha n, so the number of vertices in the boundary will be at least
24:44
beta minus one multiplied by k. Okay, so it's now actually by expanders, okay so there's many variations in the definition
25:09
of an expander, and actually for example, Lubotsky in his book uses the, on expanders
25:21
use the definition where alpha is one half, and okay then beta is kind of one plus some epsilon and use this definition of the boundary.
25:46
Now one of the main problems in the theory of expanders is to give an estimate of the number of edges, an upper estimate of the number of edges in this alpha beta expanders.
26:17
So it turns out that for every alpha beta and mu which we defined before, one can
26:31
find the constant c which is, okay, depends on alpha beta and mu, and such that for
26:42
there is an infinite set, there are infinitely many n's such that we can construct alpha beta expander with n inputs and mu n outputs, and with such that the number of edges is
27:11
not greater than cn. So it's, and actually this was essentially was maybe, no, which was noticed by Pinsker,
27:33
so it's the kind to prove the existence of such c.
27:44
So it's relatively easy, and it follows by some kind of standard probabilistic argument. So there was in combinatorics, so probably it's maybe the first, this probabilistic
28:00
type arguments were introduced by Erdos many decades ago, and so here it can be applied and to get this statement.
28:22
So it's, this is about the existence. Now to get explicit, it turns out that to get explicit construction, so some, actually it's involves some sophisticated mathematics, and so first construction, so this parent
28:56
I was the first who gave the first explicit construction of the expander, of this statement,
29:06
and then there's Gaber and Galiw and some others, and it was about 1973-75, and
29:22
it was, so some of the subjects which were involved, so there was, okay, unitary representations, and in particular there was a property T of Kajdan.
29:46
Now there's calligraphs, there's a finite groups of finite fields, so certainly I don't have time to, so actually each of these topics deserves a separate lecture, and so
30:12
I will not do that, so it's, now there's a decade later, so there was some other construction
30:32
with some properties which are better than, some spectral properties which are better than in the original explicit construction, so it's, again, so these constructions were
30:50
obtained independently by myself and by Lubotsky-Phillips-Cernak, so it was approximately 1984-1988,
31:07
and actually it uses probably more complicated subjects than in this first construction.
31:22
Yeah, so there was a quaternion of the periodic numbers, so it's, Michael and I describe what quaternions are, they were introduced by Hamilton, but they were of the real numbers, so it's, we have A plus B I plus C J plus D K with usual relations, I J is minus J
31:48
I equal to K, and then we, by circle we rotate this relation, and then there's usual multiplications, A, B, C, and D are real numbers, so, but then one can consider also
32:08
all the periodic numbers, so it's maybe just probably not, everybody here knows what periodic numbers are, so it's, so P is a prime, so it's, so usually real numbers written in
32:30
decimal expansions, so from left to the right, now is P, prime number P stands at 10, of course it's not
32:40
a prime, but you were right, some, this decimal expansion from right to the left, then we get periodic numbers, so it's, of course we should replace 10 by digits between, so 0, 1, 2, P minus 1,
33:04
okay, and then there's a theory of arithmetic groups, so then there's, okay I didn't try it, so there's a Briati, it's trees, and actually, and then something very advanced, so there's a
33:26
Jacqueline Glenn's theorem from the theory of automorphic forms, then there was a, there was a famous conjecture by Patterson and Ramanujan, again it's about
33:43
some spectrum of certain operators in the theory of automorphic forms, which was proved by Delin, so it's actually very advanced mathematics, so it's some of, for example, when
34:10
I proved that there's a, this expand is with this properties, I referred to this Ramanujan-Patterson conjecture, so it's Loboski-Phillips-Sarnak initially also did that,
34:26
but later they were able to somewhat simplify the proof and use only kind of less complicated mathematics, so it's, yeah, probably there's about 10 minutes left, so it's just,
34:57
and I maybe want to make some maybe personal remarks, so it's,
35:10
so after I got my PhD or even slightly before that, I started to work in the
35:23
Institute for the problems information transmission of the Soviet Academy of Sciences, and so then it's there where these people, so Pinsker and Vasilega, and when Pinsker
35:45
did his construction, and then there was some existence of expanders with certain, some estimates or a number of edges, so he didn't have this explicit construction, so and
36:04
I was able to do that, in some sense it was kind of, okay, in many surveys of this,
36:21
my contributions is considered as a breakthrough, but in some sense it was a luck, so it was in the right place, in the right time, and also had certain background.
36:41
Actually I was in the right place for a wrong reason, but I don't want to elaborate on that, so it's that it was, I was quite, so from this point of view, I was quite lucky, so it's,
37:01
and so actually I also wanted to do pure mathematics, so Institute for problems information transmission, so they had quite many mathematicians, but it was not exactly
37:21
mathematical institute, and there was some kind of pressure to do something more applied, and then in some sense, because of this pressure, I made this contribution, so it's,
37:40
yeah, probably it's not the most, not what I consider my most important contribution to mathematics, but probably it's the best known. Now it's let me, so probably I am
38:02
old enough to give some advice to young mathematicians, and okay, you can consider this as a joke, but so it's, once I watched TV, there was an interview with some former member of the
38:24
British government, he was also a member of the House of Lords, and he gave an advice to young people who wanted to become politicians, and he said that before
38:46
going to politics, you should make some money, so it's kind of an analog of this,
39:04
so maybe some advice before starting to develop some grand theories, you should solve some hard problems, okay. Thank you very much for your nice talk, and also for
39:37
somehow giving an example that sometimes being in the wrong place can turn out right for
39:43
something, so I think it's a very good advice for young people. So we have a short time for a question, so is there someone, yeah, there's a question there, and there's... Hello, so I'm the computer scientist, so I don't know math, but I'm working with,
40:03
I don't know like pure math in high level, I'm working with a lot of data, graph data, I can't have a thinking that's related to computer science, so could you give some hints that any application to the computer science to this? Yeah, so there was
40:27
one of the properties of this, expand the graphs that you can reach quite fast from
40:41
one vertex to another, there's a quite, okay, so there's some of it very well connected,
41:01
so probably that's the reason why it's related to many problems in theoretical computer science.
41:29
Hi, so you mentioned Dan Spielman at the beginning of your talk, and in Markus Spielman's proof of the Katzen-Singer conjecture, they give a probabilistic proof of the
41:42
existence of these bipartite Ramanujan graphs, so no explicit construction is known as of now, so I was just wondering whether you could comment on the pitfalls between going from a probabilistic proof to an explicit construction of these expander type graphs?
42:01
No, but no, that was a probabilistic, no, no probabilistic is not a construction, so it's, you know, okay, you can, if you start to construct kind randomly, then with very high probability you get an expander, but you are, but explicit construction, so give,
42:31
yeah, so what, what makes it difficult to go from the probabilistic version to the expander, to the explicit construction? I'm just wondering if there is, like, an intuitive reason why. No, no, no, it's, yeah, okay, so there was, what is called,
42:48
now, yeah, so there was a construction which are based on the use of quaternions, and they have Ramanujan properties, and so it's, but then it's the regular graphs where you have p plus one,
43:17
degree p plus one, where p is a prime number, and there is some kind of best possible estimate
43:23
for the spectrum. Yeah, so relatively recently, so it's Dan Spearman proved that it's possible to do this for, I think, for every degree, but his construction is kind of mixed, it's,
43:45
so he chooses some ensemble of graphs, and then shows that with high probability it will be this graph which, graphs which has this spectral estimate, so that's what.
44:05
I think his question was more in general, why sometimes you have a probabilistic argument that something exists, but it's very hard to find an explicit construction. Yeah, it's actually usually appropriate to show the existence using probabilistic methods.
44:24
Somehow it's kind of much easier than to give an explicit construction. Actually, I want to mention the following, you know, actually I forgot to say that rather recently it was discovered by Gut and Gromov that several years before
44:50
paper of Pinsky, there was a paper by Kolmogorov and Barzin about some brain models, and there actually they used some constructions which
45:04
have certain expanded, similar expanding properties, but somehow this paper by Kolmogorov and Barzin was not actually expert in this. Pinsky and Basaliga,
45:21
they didn't know when I told Basaliga several years ago about this paper by Kolmogorov and Barzin, he said he was not aware of that, but then he looked at the paper and he said there's something like expanders, but Pinsky certainly didn't know about
45:44
the paper and Basaliga didn't know. Now it's, yeah, so also this construction of continuous of those kind of related problems of finding graphs of our short cycles
46:09
and for example take a regular graph with degree p plus one and vertices that
46:20
is shown by the ballistic method that there is a lower estimate for possible graphs, it's less than log p log n log p n, but for this explicit construction there is this
46:41
better estimate, there's the factor four of the three log p n, and actually this number four of the three, I don't know, it's probably some neurology, but also occurs in there, there was an Mandelbrot conjecture about Hausdorff dimensions of random non-self-intersecting paths
47:08
and there is which was proved by Schramm and actually there's also this factor one of four of the three. So thank you very much.
Empfehlungen
Serie mit 37 Medien