Archive for the ‘2011’ Category

« Older Entries
Newer Entries »

Hans L. Bodlaender, Algorithms on Tree Decompositions and Time Improvements

Thursday, September 15th, 2011
Algorithms on Tree Decompositions and Time Improvements
Hans L. Bodlaender
Institute of Information and Computing Sciences, Utrecht University, The Netherlands
2011/10/31 Mon 4PM-5PM
Many problems that are intractable on general graphs become linear time solvable on graphs of bounded treewidth. The constant factor however of such algorithms is exponential or worse in the treewidth of the tree decomposition that is used. In this talk, a number of known and some new results are surveyed. In particular, it is shown how speed improvements can be obtained using convolutions, and how a recent technique called “cut-and-count” can be used to obtain fast probabilistic algorithms for problems like Hamiltonian Circuit.

Tags:
Posted in 2011, KAIST Discrete Math Seminar | Comments Closed

Jiang Zeng, Permutation Statistics on Signed Permutation Groups

Thursday, September 15th, 2011
Permutation Statistics on Signed Permutation Groups
Jiang Zeng
Institut Camille Jordan, Université Claude Bernard Lyon-I, France
2011/10/19 Wed 4PM-5PM (Room 3433)
We generalize two bijections due to Garsia and Gessel to compute the generating functions of the two vector statistics (desG, maj, ℓG, col) and (desG, idesG, maj, imaj, col, icol) over the wreath product of a symmetric group by a cyclic group. Here desG, ℓG, maj, col, idesG, imajG, and icol denote the number of descents, length, major index, color weight, inverse descents, inverse major index, and inverse color weight, respectively. Our main formulas generalize and unify several known identities due to Brenti, Carlitz, Chow-Gessel, Garsia-Gessel, and Reiner on various distributions of statistics over Coxeter groups of type A and B.

Tags:
Posted in 2011, KAIST Discrete Math Seminar | Comments Closed

Edward D. Kim, On Diameters of Transportation and Network Flow Polytopes

Thursday, September 15th, 2011
On Diameters of Transportation and Network Flow Polytopes
Edward D. Kim
Department of Mathematics, POSTECH, Pohang
2011/10/14 Fri 4PM-5PM
Transportation and network polytopes are classical objects in operations research. In this talk, we focus on recent advances on the diameters of several classes of transportation polytopes, motivated by the efficiency of the simplex algorithm. In particular, we discuss results on 2-way transportation polytopes, including a recent result of Stougie and report on joint work with Bruhn-Fujimoto and Pilaud, concerning 2-way transportation polytopes with a certain support structure. We also present a bound on 3-way transportation polytopes in joint work with De Loera, Onn, and Santos. To conclude, we discuss avenues for future work on transportation polytopes and their diameters.

Tags:
Posted in 2011, KAIST Discrete Math Seminar | Comments Closed

Michael Dobbins, Realizability of Antiprisms

Thursday, September 15th, 2011
Realizability of Antiprisms
Michael Dobbins
Department of Mathematical Sciences, KAIST
2011/10/7 Fri 4PM-5PM
If one draws the Hasse diagram for the face lattice of a polytope, this may appear to be the 1-skeleton of some other polytope. In 1971 Lindström asked whether the intervals of a polytope’s face lattice ordered by containment can be realized as the face lattice of another polytope. If so, this would be the polytope appearing the Hasse diagram. In this talk, I will give necessary and sufficient conditions for the intervals of a polytope’s face lattice to be realizable, and I will provide a counter example showing that not every polytope satisfies these conditions.

Tags:
Posted in 2011, KAIST Discrete Math Seminar | Comments Closed

Mihyun Kang (강미현), Phase transitions in random graphs

Thursday, September 15th, 2011
Phase transitions in random graphs
Mihyun Kang (강미현)
Institut für Mathematik, Freie Universität Berlin, Germany
2011/09/30 Fri 4PM-5PM
The phase transition deals with sudden global changes and is observed in many fundamental problems from statistical physics, mathematics and theoretical computer science, for example, Potts models, graph colourings and random k-SAT. The phase transition in random graphs refers to a phenomenon that there is a critical edge density, to which adding a small amount a drastic change in the size of the largest component occurs. In Erdös-Renyi random graph, which begins with an empty graph on n vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches n/2 and a giant component emerges. Since this seminal work of Erdös and Renyi, various random graph models have been introduced and studied. In this talk we discuss phase transitions in several random graph models, including Erdös-Renyi random graph, random graphs with a given degree sequence, random graph processes and random planar graphs.

Tags:
Posted in 2011, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »