1st workshop of the Center of Modern Computer Science
1. seminář Centra moderní informatiky
The first workshop of the Center of Modern Computer Science will take place on Thursday April 26, 2012, in room S9 at MFF UK, Malostranské nám. 25, Praha 1.
Centrum moderní informatiky zve na první seminář ve čtvrtek 26.4.2012 od 14:00 v posluchárně S9 budovy Matematicko-fyzikální fakulty UK Malostranské nám. 25, Praha 1.
| 14:00 | Zahájení |
|---|---|
| 14:05 | Martin Tancer: Non-embeddability of buildings |
| 14:30 | Robert Šámal: Vector chromatic number - where graph theory meets semidefinite programming |
| 14:55 | Petr Gregor: Subcube isoperimetry and power of coalitions |
| 15:20 | přestávka |
| 15:40 | Milan Hladík: Basis stability in interval linear programming |
| 16:10 | Daniel Král': Flag algebra method in extremal combinatorics |
Abstracts
Martin Tancer: Non-embeddability of buildings
Buildings are highly symmetric simplicial complexes related to Coxeter groups. We may ask how hard is it to visualize them. With a visualization we mean an embedding of a (finite) building into R^n with n as small as possible.
In general, a simplicial complex of dimension d always embeds into R^{2d+1}, but there are known examples of simplicial complexes that require dimension 2d+1. Our task is to show that many buildings serve as above-mentioned examples, i.e., they are not embeddable into R^{2d}. This result can be understood in a spirit that high symmetry of the buildings implies that they are hard to visualize.
More precisely, buildings are classified and they fall into sever classes according to related Coxeter group. We show that thick type A buildings are hard to embed and also some of type B buildings (those coming from alternating bilinear forms and Hermitian forms).
We do not know the answer for remaining types of buildings; however we suspect that all thick buildings are hard to embed (thick buildings are those that are not homeomorphic to a d-dimensional sphere).
Robert Šámal: Vector chromatic number - where graph theory meets semidefinite programming
Vector coloring of a graph is a mapping of vertices of the graph to unit vectors in a vector space, so that adjacent vertices get mapped to far-away vertices. Precisely: vector k-coloring (for a real k>= 2) requires that the dot product of adjacent vertices is at most -1/(k-1).
This concept was introduces by Karger, Motwani, and Sudan as a means to approximate the usual chromatic number. As the vector chromatic number is a solution of a semidefinite program, this gives an efficient algorithm (although with a bad approximation ratio). The vector chromatic number is also closely related to the Lovasz theta function, that started the whole field of the semidefinite programming.
I will describe new progress and conjectures in this area. Considering vector chromatic number as a graph parameter that deserves its own study, I will discuss its behaviour for random graphs, and for the product of graphs (variant of the Hedetniemi conjecture).
Petr Gregor: Subcube isoperimetry and power of coalitions
We determine the minimal number of $d$-dimensional subcubes with a vertex in $A$ and simultaneously a vertex not in $A$, over all sets $A$ of $k$ vertices in the $n$-dimensional hypercube. This extends a classical result of Harper on the edge-isoperimetric problem in the hypercube. We study properties of extremal sets with means of harmonic analysis of corresponding Boolean functions. Applications range from labeling vertices of the hypercube so that total maximal deviation of labels on subcubes is minimized, to study of influence of coalitions in simple voting games via their Banzhaf power index.
Milan Hladík: Basis stability in interval linear programming
Interval linear programming considers linear programming problems with interval data. That is, coefficients vary simultaneously and independently within given intervals. An interval linear programming problem is called basis stable if there is a basis that is optimal for each possible realization of interval quantities. Basis stability is important for determining the range of optimal values and the set of all optimal solutions. In general, these problems are difficult to solve, but under basis stability they become tractable. However, checking basis stability is still NP-hard. We present a complete algorithm for checking basis stability and an efficiently computable sufficient condition.
Daniel Král': Flag algebra method in extremal combinatorics
Razborov [J. Symbolic Logic (2007), 1239-1282] developed a formal algebraic framework for deriving true relations among densities of combinatorial substructures (e.g., subgraphs of a graph). In the talk, we provide brief but self-contained introduction to this framework and we present several successful applications of it.
