报告人：马杰教授，中国科学技术大学

报告时间：2015年11月12日16点

报告地点：离散数学研究中心二层报告厅

报告题目：Overlaps of random hypergraphs

    报告人简介：马杰，中国科学技术大学，教授，2011年毕业于美国佐治亚理工学院，获博士学位，2011年至2013年在加州大学洛杉矶分校任Hedrick Assistant Professor，2013年至2014年在Carnegie Mellon University从事博士后研究，2014年为中国科学技术大学教授。主要从事极值组合、图论及其应用方面的研究，目前在“J. Comb. Theory, Ser. B”、“Combinatorica”、“Random Structure and Algorithms”等组合顶级杂志发表学术论文十余篇。

报告摘要：Let $G$ and $H$ be two $k$-uniform hypergraphs over the same vertex set $V$ of size $n$. Define the  discrepancy of $H$ to be $\\disc(H)=\\max_{S\\subseteq V(H)} \\left|e(S)- \ho_H \\binom{|S|}{k} \ight|$, where $\ho_H$ is the edge-density of $H$. The discrepancy can be viewed as a measure of how uniformly the edges of $H$ are distributed among the vertices. This important concept is widely adopted in many branches of combinatorics and has been the subject of extensive research, some of which will be mentioned in this talk.

The discrepancy of two hypergraphs $G$ and $H$ is defined as $\\disc(G,H) = \\max_\\pi\\left|e(G_\\pi \\cap H) - \ho_G\ho_H\\binom{n}{k}\ight|$ over all bijections $\\pi: V\o V$. This represents how far the overlap $G_{\\pi}\\cap H$ of two hypergraphs can be from its average. The definition of $\\disc(G, H)$ is in sense more general than $\\disc(H)$. Bollob\\'as and Scott asked the following question: if $G$ and $H$ are two random graphs distributed according to $G(n, p)$, then what is the expectation of $\\disc(G, H)$?

In \\cite{MNS}, we answer this problem in a stronger form, by determining the discrepancy between two random $k$-uniform hypergraphs up to a constant factor.We shall also discuss other related results and problems in this talk.

Joint work with Humberto Naves and Benny Sudakov.

欢迎老师和研究生参加！