Events

A Counterexample to Beck's Three Permutations Conjecture

Abstract:

Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. In 1982, Jozsef Beck conjectured that the discrepancy of this set system is O(1).

Cops and robber on a random graph

Abstract:

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G.

Augmenting undirected node-connectivity by one

Abstract:

Orientation of Graphs

Abstract:

In this survey talk I will present results on orientations of graphs satisfying connectivity constraints.

Quantum Problems in Algebraic Graph Theory

Abstract:

Quantum computing is an exciting topic for many reasons. What might be less well known is that many problems in quantum computing have lead to interesting questions in algebraic graph theory.

Convex Relaxation for Sensor Network Localization

Abstract:

In this talk, we consider the problem of sensor network localization, where one locates unknown sensor positions from some known sensor positions (called anchors) and (noisy) distance measurements between neighboring sensors.

The 012-Puzzle Conjecture

Abstract:

The 012-Puzzle conjecture in algebraic combinatorics was formulated by A. Knutson about 10 years ago. The statement is quite elementary and easy to understand. It is also a bit surprising and hard to believe.

Log concavity of characteristic polynomials and tropical intersection theory

Abstract:

In a recent joint work with June Huh, we proved the log concavity of the characteristic polynomial of a realizable matroid by relating its coefficients to intersection numbers on an algebraic variety and applying an a

Forcing large transitive subtournaments

Abstract:

The Erdos Hajnal Conjecture states roughly that a graph with some induced subgraph excluded has a large clique or a large stable set.

Multiple Traveling Salesmen in Asymmetric Metrics