Loading Events

Past Events › Discrete Math Seminar

Events Search and Views Navigation

Event Views Navigation

November 2019

:

Sun Kim (김선), Two identities in Ramanujan’s Lost Notebook with Bessel function series

Speaker

Tuesday, November 5, 2019 @ 4:30 PM - 5:30 PM
Room 1401, Bldg. E6-1, KAIST

On page 335 in his lost notebook, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities under three different interpretations for the double series, and showed that they are intimately connected with the classical circle and divisor problems in number theory. Furthermore, we established many analogues and generalizations of them. This is joint work with Bruce C. Berndt and Alexandru Zaharescu.

Find out more »
:

Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

Tuesday, November 12, 2019 @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$.  We prove that under the additional assumption that the input graph is embedded in a…

Find out more »
:

Ruth Luo, Induced Turán problems for hypergraphs

Speaker

Ruth Luo
University of California, San Diego
https://math.ucsd.edu/~ruluo/
Tuesday, November 19, 2019 @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

Let $F$ be a graph. We say that a hypergraph $\mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $\mathcal H$ such that for all $xy \in E(F)$, $f(xy) \cap V(F) = \{x,y\}$. In this talk, we show asymptotics for the maximum number of edges in $r$-uniform hypergraphs with no induced Berge $F$. In particular, this function is strongly related to the generalized Turán function $ex(n,K_r, F)$, i.e., the…

Find out more »
:

Frédéric Meunier, Topological bounds for graph representations over any field

Speaker

Frédéric Meunier
École Nationale des Ponts et Chaussées, Paris
https://cermics.enpc.fr/~meuniefr/
Thursday, November 21, 2019 @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb {R}$. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for the minrank parameter over $\mathbb {R}$ – an important graph invariant from coding theory – and show that this bound is actually valid for all…

Find out more »

December 2019

:

Jakub Gajarský, First-order interpretations of bounded expansion classes

Tuesday, December 10, 2019 @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low…

Find out more »
:

Hong Liu, A proof of Mader’s conjecture on large clique subdivisions in $C_4$-free graphs

Speaker

Hong Liu
Mathematics Institute, University of Warwick, UK
http://homepages.warwick.ac.uk/staff/H.Liu.9/
Thursday, December 12, 2019 @ 4:30 PM - 5:30 PM
Room 1401, Bldg. E6-1, KAIST

Given any integers $s,t\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of…

Find out more »
:

Attila Joó, Base partition for finitary-cofinitary matroid families

Speaker

Thursday, December 19, 2019 @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

Let ${\mathcal{M} = (M_i \colon i\in K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$. We prove the following Cantor-Bernstein-type result: if $E$ can be covered by sets ${(B_i \colon i\in K)}$ which are bases in the corresponding matroids and there are also pairwise disjoint bases of the matroids $M_i$ then $E$ can be partitioned into bases with respect to $\mathcal{M}$.

Find out more »
:

Jaiung Jun (전재웅), The Hall algebra of the category of matroids

Thursday, December 26, 2019 @ 4:30 PM - 5:30 PM
Room 1401, Bldg. E6-1, KAIST

To an abelian category A satisfying certain finiteness conditions, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a non-additive setting, Dyckerhoff and Kapranov introduced the notion of proto-exact categories, as a non-additive generalization of an exact category, which is shown to suffice for the construction of an associative Hall algebra. In this talk, I will discuss the category of matroids in this perspective.

Find out more »

January 2020

:

Sanjeeb Dash, Boolean decision rules via column generation

January 14 Tuesday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models such as random forests or support vector machines. In this talk, we consider boolean decision rule sets (equivalent to boolean functions in disjunctive normal form) as interpretable models for binary classification. We define the complexity of a rule set to be the number of rules (clauses) plus the number of…

Find out more »
:

Ben Lund, Furstenberg sets over finite fields

Speaker

Ben Lund
Princeton University
http://www.ben-lund.com
January 15 Wednesday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved by Dvir in 2008. Dvir's proof introduced the polynomial method to incidence geometry, which led to the solution to many long-standing problems in the area. I will talk about a generalization of the Kakeya conjecture posed by Ellenberg, Oberlin, and Tao. A $(k,m)$-Furstenberg set S in $\mathbb F_q^n$ has the property that,…

Find out more »
+ Export Events