主讲人：毋述斐，河南理工大学
报告时间：2019年8月9日10点，8月10日10点，8月11日10点，8月12日10点
报告地点：数计学院4号楼A407
报告题目1：On judicious bipartitions of directed graphs
报告摘要：Let $d\ge 4$ be an integer. Lee, Loh and Sudakov [{Random Struct. Algorithms}, 2016, 48: 147--170] conjectured that every directed graph $D$ with $m$ arcs and minimum outdegree at least $d$ admits a bipartition $V(D)=V_1\cup V_2$ such that \[\min\{e(V_1,V_2),e(V_2,V_1)\}\geq \Big(\frac{d-1}{2(2d-1)}+ o(1)\Big)m,\] where $e(V_i,V_j)$ denote the number of arcs in $D$ from $V_i$ to $V_j$ for $\{i,j\}=\{1,2\}$. Let $\overrightarrow{{K_{d,2}}}$ denote the directed graph obtained by orienting each edge of a bipartite graph $K_{2,d}$ from the part of size $d$ to the other part. In this paper, we show that the conjecture holds for $\overrightarrow{{K_{d,2}}}$-free directed graphs. Then, we prove that the conjecture holds under the additional condition that the minimum indegree is also at least $d-1$, which improve a result given by Hou, Ma, Yu and Zhang.
报告题目2：On bipartitions of directed graphs with small semidegree
报告摘要：Let $D$ be a directed graph. The minimum semidegree of $D$ is defined to be the minimum value of the minimum outdegree and the minimum indegree of $D$. For nonempty sets $S, T\subseteq V(D)$, we use $e(S, T)$ to denote the number of arcs in $D$ from $S$ to $T$. If $D$ has $m$ arcs and the positive minimum semidegree, then we show that $D$ admits a bipartition $V(D)=V_1 \cup V_2$ such that $\min\{e(V_1,V_2),e(V_2,V_1)\}\geq (1/6+o(1))m$. We also prove that if the minimum semidegree is at least two (or three, respectively), then the constant can be increased to $1/5$ (or $3/14$, respectively). These partly answers a question of Hou and Wu (2018).
报告题目3：Judicious bisections of $H$-free graphs
报告摘要：Judicious bisections usually ask for a bisection of a graph in which both vertex classes span few edges. For a random bisection of a graph with $m$ edges, we expected $m/4$ edges in each class. Bollob\'as and Scott (Random Struct. Alg. 21 (2002) 414--430) asked for conditions that guarantee a judicious bisection in which each class spans at most $(1/4 + o(1))m$ edges.
Let $\ell \ge 2$ be a fixed integer, we prove that if $G$ contains neither triangle nor $K_{2,\ell}$ then $G$ admits a bisection in which each class spans at most $(1/4+o(1))m$ edges.
报告题目4：Judicious bisections of directed graphs
报告摘要：For a digraph $D$, the directed cut $e(X,Y)$ spans by the bisection $V(D)=X\cup Y$ is the set of all directed arcs from $X$ to $Y$ in $D$. It is easy to show that every $m$-arcs-digraph has a bisection spans a directed cut of size at least $m/4$. For judicious bisections, we ask for bisections in which spans many arcs in each direction. For some fixed integer $s\ge3$, let $D$ be a directed graph with $m$ arcs and minimum degree 2, if the underlying graph of $D$ does no contain triangles and $K_{2,s}$, then $D$ admits a bisection in which at least $(1/4+o(1))m$ arcs spans in each direction.
