Archive for the ‘2017’ Category

« Older Entries
Newer Entries »

Xavier Goaoc, Shatter functions of (geometric) hypergraphs

Thursday, September 7th, 2017
Shatter functions of (geometric) hypergraphs
Xavier Goaoc
Université Paris-Est, Marne-la-Vallée, France
2017/09/25 Mon 4PM-5PM (Room 3433, Bldg. E6-1)
In combinatorial and computational geometry, the complexity of a system of sets is often studied via its shatter function. I will introduce these functions, and discuss how their asymptotic growth rate is governed from a single of its values, in the spirit of the classical notion of “Vapnik-Chernonenkis dimension” of hypergraphs. In particular, I will describe a probabilistic construction that refutes a conjecture of Bondy and Hajnal. This is joint work with Boris Bukh (https://arxiv.org/abs/1701.06632). The talk will start from first principles.

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

Jaehoon Kim (김재훈), Property testing for hypergraphs

Saturday, July 15th, 2017
Property testing for hypergraphs
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, UK
2017/7/27 Thu 4PM-5PM
We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs).
Here, a k-graph property ? is testable if there is a randomized algorithm which quickly distinguishes with high probability between k-graphs that satisfy ? and those that are far from satisfying ?. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. This is joint work with Felix Joos, Deryk Osthus and Daniela Kühn.

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

Edgardo Roldán-Pensado, On the colourful Helly theorem

Monday, June 26th, 2017
On the colourful Helly theorem
Edgardo Roldán-Pensado
Instituto de Matemáticas, UNAM, Mexico
2017/07/07 Fri 4PM-5PM
Let F be a family of convex sets in R^d coloured using d+1 colours. Lovasz’s Colourful Helly Theorem states that if any colourful subfamily of convex sets is intersecting, then one of the monochromatic families is intersecting. We study what happens with the rest of the families.

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

Johann A. Makowsky, The Complexity of Counting Generalized Colorings: New Results and Challenges

Monday, June 26th, 2017
The Complexity of Counting Generalized Colorings: New Results and Challenges
Johann A. Makowsky
Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
2017/07/14 Fri 4PM-5PM
Let P be a graph property. We look at graph colorings with k colors where each color class induces a graph satisfying P. By a result of Makowsky and Zilber (2005) the number of such colorings ?P(G;k) is a polynomial in k. We present recent results and open problems on the complexity of evaluating ?P(G;λ) for various properties P and (not only integer) values of λ.
This is joint work with A. Goodall, M. Hermann, T. Kotek and S. Noble which was initiated during last year’s program “Counting Complexity and Phase Transitions”. See also arXiv:1701.06639v1.

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

June Huh (허준이), Negative correlation and Hodge-Riemann relations

Saturday, June 17th, 2017

Discrete Math Seminar Joint with Algebraic Geometry Seminar

Negative correlation and Hodge-Riemann relations
June Huh (허준이)
Institute for Advanced Study, Princeton, NJ, USA
2017/07/12 Wednesday 4PM (Room 3435)
All finite graphs satisfy the two properties mentioned in the title. I will explain what I mean by this, and speculate on generalizations and interconnections. This talk will be non-technical: Nothing will be assumed beyond basic linear algebra.

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

« Older Entries
Newer Entries »