Seminars in May 2008

• Jeong-Han Kim (김정한), Optimal Query Complexity Bounds for Finding Graphs

  Optimal Query Complexity Bounds for Finding Graphs

  Jeong-Han Kim (김정한)
  Dept. of Mathematics, Yonsei University, Seoul, Korea.

  2008/05/16 Fri, 4PM-5PM

  We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask sum of weights for the weighted graphs. These types of queries were partially motivated in DNA shotgun sequencing and linkage discovery problem of artificial intelligence.

  For a given unknown weighted graph G with n vertices, m edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of G using O((m log n)/log m) queries of both types provided that m≤ n^ε for any constant ε>0. For a graph, it is shown that the same bound holds for all range of m.

  This settles a conjecture of Grebinski for finding an unweighted graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions. A similar coin weighing problem is also considered. (Joint work with S. Choi)

  Tags:

  • 김정한

• Roy Meshulam, Leray complexes – combinatorics and geometry

  Leray complexes – combinatorics and geometry

  Roy Meshulam
  Dept. of Mathematics, Technion, Haifa, Israel.

  2008/05/08 Thu, 3PM-4PM

  Helly’s theorem asserts that if a finite family of convex sets in d-space has an empty intersection, then there exists a subfamily of cardinality at most d+1 with an empty intersection. Helly’s theorem and its numerous extensions play a central role in discrete and computational geometry. It is of considerable interest to understand the role of convexity in these results, and to find suitable topological extensions. The class of d-Leray complexes (introduced by Wegner in 1975) is the natural framework for formulating topological Helly type theorems. We will survey some old and new results on Leray complexes with combinatorial and geometrical applications. In particular, we’ll describe recent work on Leray numbers of projections and a topological Helly type theorem for unions. Joint work with Gil Kalai.

  Tags:

  • RoyMeshulam

• Seog-Jin Kim (김석진), List-coloring the Square of a Subcubic Graph

  List-coloring the Square of a Subcubic Graph

  Seog-Jin Kim (김석진)
  Dept. of Mathematics Education, Konkuk University, Seoul, Korea.

  2008/05/01 Thu, 3PM-4PM

  The square G² of a graph G is the graph with the same vertex set as G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that for a planar graph G with maximum degree Δ(G)=3 we have χ(G²)≤7. Kostochka and Woodall conjectured that for every graph, the list-chromatic number of G² equals the chromatic number of G², that is χ_l(G²)=χ(G²) for all G. If true, this conjecture (together with Thomassen’s result) implies that every planar graph G with Δ(G)=3 satisfies χ_l(G²)≤7. We prove that every graph (not necessarily planar) with Δ(G)=3 other than the Petersen graph satisfies χ_l(G²)≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G)=3 and girth g(G)≥7, then χ_l(G²)≤7. Dvořák, Škrekovski, and Tancer showed that if G is a planar graph with Δ(G)=3 and girth g(G)≥10, then χ_l(G²)≤6. We improve the girth bound to show that: if G is a planar graph with Δ(G)=3 and g(G)≥9, then χ_l(G²)≤6. This is joint work with Daniel Cranston.</div>

  Tags:

  • 김석진