Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

Dabeen Lee, Integrality of set covering polyhedra and clutter minors

Friday, June 28th, 2019

IBS/KAIST Joint Discrete Math Seminar

Integrality of set covering polyhedra and clutter minors
Dabeen Lee (이다빈)
IBS Discrete Mathematics Group
2019/07/16 Tue 4:30PM-5:30PM
Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem, also known as the hitting set problem, admits a simple integer linear programming formulation. The constraint system of the integer linear programming formulation defines a polyhedron, and we call it the set covering polyhedron of $\mathcal{C}$. We say that a set covering polyhedron is integral if every extreme point is an integer lattice point. Although the set covering problem is NP-hard in general, conditions under which the problem becomes polynomially solvable have been studied. If the set covering polyhedron is integral, then it is straightforward that the problem can be solved using a polynomial-time algorithm for linear programming.

In this talk, we will focus on the question of when the set covering polyhedron is integral. We say that the family $\mathcal{C}$ is a clutter if every subset in $\mathcal{C}$ is inclusion-wise minimal. As taking out non-minimal subsets preserves integrality, we may assume that $\mathcal{C}$ is a clutter. We call $\mathcal{C}$ ideal if the set covering polyhedron of it is integral. To understand when a clutter is ideal, the notion of clutter minors is important in that $\mathcal{C}$ is ideal if and only if so is every minor of it. We will study two fundamental classes of non-ideal clutters, namely, deltas and the blockers of extended odd holes. We will characterize when a clutter contains either a delta or the blocker of an extended odd hole as a minor.

This talk is based on joint works with Ahmad Abdi and G\’erard Cornu\’ejols.

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

Patrice Ossona de Mendez, A model theoretical approach to sparsity

Monday, May 20th, 2019

IBS/KAIST Joint Discrete Math Seminar

A model theoretical approach to sparsity
Patrice Ossona de Mendez
CNRS, France
2019/06/25 Tue 4:30PM-5:30PM
We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.

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

Suil O (오수일), An odd [1,b]-factor in regular graphs from eigenvalues

Friday, April 19th, 2019

IBS/KAIST Joint Discrete Math Seminar

An odd [1,b]-factor in regular graphs from eigenvalues
Suil O (오수일)
Department of Applied Mathematics and Statistics, SUNY-Korea
2019/06/19 Wed 4:30PM-5:30PM
An odd [1,b]-factor of a graph is a spanning subgraph H such that for every vertex v∈V(G), 1≤dH(v)≤b, and dH(v) is odd. For positive integers r≥3 and b≤r, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an r-regular graph with even number of vertices to guarantee the existence of an odd [1,b]-factor. In this talk, we improve their bound.

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

Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube

Tuesday, April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

The number of maximal independent sets in the Hamming cube
Jinyoung Park (박진영)
Department of Mathematics, Rutgers University, USA
2019/06/03 Monday 4:30PM-5:30PM (IBS, Room B232)
Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$. This is joint work with Jeff Kahn.

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

Lars Jaffke, A complexity dichotomy for critical values of the b-chromatic number of graphs

Tuesday, April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

A complexity dichotomy for critical values of the b-chromatic number of graphs
Lars Jaffke
University of Bergen
2019/05/20 Mon 4:30PM-5:30PM (IBS, B232)
A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has a b-coloring with k colors.The b-chromatic number of a graph G, denoted by χb(G), is the maximum number k such that G admits a b-coloring with k colors. We consider the complexity of the b-Coloring problem, whenever the value of k is close to one of two upper bounds on χb(G): The maximum degree Δ(G) plus one, and the m-degree, denoted by m(G), which is defined as the maximum number i such that G has i vertices of degree at least i−1. We obtain a dichotomy result stating that for fixed k∈{Δ(G)+1−p,m(G)−p}, the problem is polynomial-time solvable whenever p∈{0,1} and, even when k=3, it is NP-complete whenever p≥2.
We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree Δ(G) of the input graph G and give two FPT-algorithms. First, we show that deciding whether a graph G has a b-coloring with m(G) colors is FPT parameterized by Δ(G). Second, we show that b-Coloring is FPT parameterized by Δ(G)+ℓk(G), where ℓk(G) denotes the number of vertices of degree at least k.
This is joint work with Paloma T. Lima.

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

« Older Entries
Newer Entries »