Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, February 8, 2016

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041



Lecture - 14:15

Jan Draisma - TU Eindhoven

Noetherianity up to symmetry

Abstract:
One of my favourite open questions is the following:

"Is Sato's Grassmannian Noetherian up to symmetry?"

At first sight, this question seems quite remote from discrete mathematics, but I hope to convince you otherwise. Along the way, I will review recent developments in infinite-dimensional commutative algebra, in which combinatorial notions such as well-partial-orders play a fundamental role.




Colloquium - 16:00

Jan Hackfeld - TU Berlin

Undirected Graph Exploration with Θ(log log n) Pebbles

Abstract:
We consider the fundamental problem of exploring an undirected and initially unknown graph by an agent with little memory. The vertices of the graph are unlabeled, and the edges incident to a vertex have locally distinct labels. In this setting, it is known that Θ(log n) bits of memory are necessary and sufficient to explore any graph with at most n vertices. We show that this memory requirement can be decreased significantly by making a part of the memory distributable in the form of pebbles. A pebble is a device that can be dropped to mark a vertex and can be collected when the agent returns to the vertex. We show that for an agent O(log log n) distinguishable pebbles and bits of memory are sufficient to explore any bounded-degree graph with at most n vertices. We match this result with a lower bound exhibiting that for any agent with sub-logarithmic memory, Ω(log log n) distinguishable pebbles are necessary for exploration.



Letzte Aktualisierung: 26.01.2016