当前位置:首页 |  学术交流学术交流

河南理工大学毋述斐博士报告

信息来源: 暂无 发布日期: 2019-08-06 浏览次数:

主讲人:毋述斐,河南理工大学  

报告时间: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.