Seminar on Combinatorics

主講者: 1. 陸臨淵 教授(南卡羅來納大學) 2. 黃喻培 博士(義守大學)
講題: 1. Forbidden configurations and Repeated columns 2. On the Minimum Rank Problems of Graphs
時間: 2013-11-29 (Fri.)  14:00 - 17:00
地點: 數學所 617 研討室 (台大院區)
Abstract: 1. How many edges can a simple hypergraph on $m$ vertices have when there is a forbidden configuration? A fundamental result is due to Sauer, Perles and Shelah, Vapnik and Chervonenkis. Let $K_k$ denote the complete hypergraph on $k$ vertices (with $2^k$ edges). Then any simple hypergraph on $m$ vertices forbidding $K_k$ can have at most $\sum_{i=0}^{k-1}{m\choose i}$ edges. In this talk, we will consider the following forbidden configuration problem. Let $t\ge 1$ be a given integer. Let ${\cal F}$ be a family of subsets of $[m]=\{1,2,\ldots ,m\}$. Assume that for every pair of disjoint sets $S,T\subset [m]$ with $|S|=|T|=k$, there do not exist $2t$ sets in ${\cal F}$ where $t$ subsets of ${\cal F}$ contain $S$ and are disjoint from $T$ and $t$ subsets of ${\cal F}$ contain $T$ and are disjoint from $S$. We show that $|{\cal F}|$ is $O(m^{k})$. This is joint work with Richard P. Anstee. 2. Let $G$ be a simple undirected graph on $n$ vertices. The matrices having $G$ as a described graph are the symmetric matrices indexed by the vertices of $G$, whose off-diagonal entries are nonzero if the corresponding vertices are adjacent, and zero otherwise. The minimum rank $m(G)$ of $G$ is defined as the minimum rank among these matrices. In this talk we will briefly introduce some current progress about the minimum rank problems. This is a joint work with Liang-Yu Hsieh.
  || Close window ||