Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

Hermanshu Kaul, Finding Large induced subgraphs and allocation of resources under dependeny

Tuesday, October 29th, 2013
Finding Large induced subgraphs and allocation of resources under dependeny
Hermanshu Kaul
Illinois Institute of Technology
2013/11/20 Wednesday 4PM-5PM
Room 1409

Given a graph, we are interested in studying the problem of finding an induced subgraph of a fixed order with largest number of edges. More generally, let G = (V, E) be an undirected graph, with a weight (budget) function on the vertices, w: V → ℤ+, and a benefit function on vertices and edges b: E ∪ V → ℤ. The benefit of a subgraph H =(VH,EH) is b(H) = ∑ v∈VH b(v) + ∑ e∈EH b(e) while its weight is w(H) = ∑ v∈VH w(v). What can be said about the maximum benefit of an induced subgraph with the restriction that its weight is less than W?

This problem is closely related to the Quadratic Knapsack Problem, the Densest Subgraph Problem, and classical problems in Extremal Graph Theory. We will discuss these connections, give applications in resource allocation, and present new results on approximation algorithms using methods from convex optimization and probability. This is joint work with Kapoor.

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

Suyoung Choi (최수영), The rational Betti number of small covers and its combinatorics

Tuesday, October 29th, 2013
The rational Betti number of small covers and its combinatorics
Suyoung Choi (최수영)
Department of Mathematics, Ajou University
2013/11/13 Wednesday 4PM-5PM
ROOM 1409

A small cover is a topological analogue of real toric varieties, and is an important object in toric topology. It is noted that the formula of the ℤ2-cohomology ring of small cover is well-known. However, the integral cohomology ring of small covers has not been known well.

In this talk, we discuss about the Betti numbers and its torsion of the small covers associated to some nestohedra including graph associahedra. Interestingly, the Betti numbers can be computed by purely combinatorial method (in terms of graphs and hypergraphs). To our surprise, for specific families of graphs, these numbers are deeply related to well-known combinatorial sequences such as the Catalan numbers and Euler zigzag numbers.

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

Yoshio Okamoto, Geometric weight balancing

Tuesday, October 29th, 2013
Geometric weight balancing
Yoshio Okamoto
Department of Communication Engineering and Informatics, UEC, Japan
2013/11/05 Tuesday 11AM – 12AM
Given a simple polygon P, a point t in P, and a set of positive weights, we want to place the weights on the boundary of P in such a way that their barycenter comes to t. We show that there is always such a placement if the weights are balanced, i.e., no weight is larger than half of the total weight, and the placement can be found efficiently. We also study three-dimensional versions of the problem.

Joint work with Luis Barba, Jean Lou De Carufel, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yuan Tang, Takeshi Tokuyama, Sander Verdonschot, and Tianhao Wang.

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

Meesue Yoo (유미수), Schur expansion of the integral form of Macdonald polynomials

Tuesday, October 8th, 2013
Schur expansion of the integral form of Macdonald polynomials
Meesue Yoo (유미수)
KIAS
2013/10/30 Wednesday 4PM-5PM
ROOM 1409
In this talk, we consider the combinatorial formula for the Schur coefficients of the integral form of the Macdonald polynomials. As an attempt to prove Haglund’s conjecture that ⟨Jλ[X;q,qk]/(1-q)n,sμ(X)⟩∈ℕ[q], we have found explicit combinatorial formulas for the Schur coefficients in one row case, two column case and certain hook shape cases. Egge-Loehr-Warrington constructed a combinatorial way of getting Schur expansion of symmetric functions when the expansion of the function in terms of Gessel’s fundamental quasi symmetric functions is given. We apply this method to the combinatorial formula for the integral form Macdonlad polynomials of Haglund-Haiman-Loehr in quasi symmetric functions to get the Schur coefficients and prove the Haglund’s conjecture in more general cases.

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

Boram Park (박보람), Counterexamples to the List Square Coloring Conjecture

Wednesday, September 4th, 2013
Counterexamples to the List Square Coloring Conjecture
Boram Park
Optimization and Its Application Research Team
NIMS
2013/10/16 Wednesday 4PM-5PM
ROOM 1409
The square G2 of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in G2 if the distance between u and v in G is at most 2. Let χ(H) and χl(H) be the chromatic number and the list chromatic number of H, respectively. A graph H is called chromatic-choosable if χl(H) = χ(H). It is an interesting problem to find graphs that are chromatic-choosable. Kostochka and Woodall conjectured that χl(G2) = χ(G2) for every graph G, which is called List Square Coloring Conjecture. In this paper, we give infinitely many counterexamples to the conjecture. Moreover, we show that the value χl(G2) − χ(G2) can be arbitrary large.

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

« Older Entries
Newer Entries »