当前位置:首页 > 学术报告 > 图论与网络研究中心学术报告

报告题目: Circumferences in 1-tough graphs
报 告 人: Prof. Hao Li,French National Center for Scientific Research
时间地点: 2013年8月21日(星期三)上午10:00 思源楼703
摘       要: Bauer, Morgana, Schmeichel and Veldman have conjectured that the circumference of any 1-tough graph of order with minimum degree is at least . They proved that under these conditions, . Then Bauer, Schmeichel and Veldman improved this result by getting . We show in this paper that .
报告题目: Dominating sets of triangulated discs
报 告 人: Dr.Shinichi Tokunaga,Tokyo Medical and Dental University
时间地点: 2013年3月11日(星期一)上午9:50 思源楼1013
摘       要: We show that if G is an n-vertex maximal outerplanar graph with k vertices of degree 2, then G has a dominating set of size at most by a simple coloring method. We also discuss about violating problems of triangulated discs.
报告题目: Forbidden triples generating a finite family of graphs
报 告 人: Prof. Dr. Yoshimi Egawa,Tokyo University of Science
时间地点: 2013年3月11日(星期一)上午9:00 思源楼1013
摘       要: We consider the problem of determining those triples {F1,F2,F3} of graphs for which the family of k-connected {F1,F2,F3}-free graphs is a finite family.
报告题目: Spanning trees with bound total excesses
报 告 人: Dr. Kenta Ozeki,National Institute of Informatics
时间地点: 2012年10月24日(星期三)上午9:00 思源楼709
摘       要: For an integer k with , a tree with maximum degree at most k is called a k-tree, and a tree with at most k leaves is called a k-ended tree.
As a generalization of the above two concepts, the concept of total excess is defined as follows: For a graph T and an integer k, the total excess te(T, k) from k is defined as

te(T,K)=SUM(max{0,degT(v)-k})

where degT(v) is the degree of v in T. It is easy to see that for a tree T, T is a k-tree if and only if te(T,k) = 0, and T is a (t+2) -ended tree if and only if te(T,2) t . So using the concept of total excess, we can deal with both spanning k-trees and spanning k-ended trees at the same time.
In this talk, I will give a survey on spanning trees with bounded total excesses.

报告题目: Some combinatorial problems in multiprocessor scheduling
报 告 人: Prof. D. de Werra,President of IFORS Ecole Polytechnique Fédérale de Lausanne Switzterland
时间地点: 2012年10月17日(星期三)下午3:30 思源楼703
摘       要: We shall start from the basic classical open shop model with processors and jobs to be processed on the processors according to some requirements. We shall concentrate on the case in which some processors have to be grouped (becoming so multiprocessors) in order to perform some of the tasks required by the jobs. Such a model which has been studied by some authors is motivated by applications in timetabling as well as in testing of electronic systems in particular. We shall describe these applications and review the basic results related to the simple cases of ordinary open shop. Complexity issues will be discussed for the situations in which some grouping of processors is required to cope with the needs of applications.
The presentation is based on joint work with W.Kubiak and T.Kis.
报告题目: Factors of regular graphs
报 告 人: Prof. Mikio Kano,Ibaraki University
时间地点: 2012年9月20日(星期四)上午9:00 思源楼1013
摘       要: We present some old and new results on degree factors of regular graphs, and also give some related problems.
报告题目: Matchings in balanced hypergraphs
报 告 人: Prof. Dr. Eberhard Triesch,Lehrstuhl II fuer Mathematik RWTH Aachen, Germany
时间地点: 2012年9月11日(星期二)上午10:00 思源楼712
摘       要: In 1970, C.Berge introduced the notion of a balanced hypergraph in order to generalize bipartite graphs. Balanced hypergraphs are defined as hypergraphs without a (certain type of) odd cycles and share indeed many properties of bipartite graphs, e.g. the analogues of K?nig's Theorem hold. In 1996, Conforti et al. proved an analogue of Hall's Theorem in balanced hypergraphs which can be stated as follows: We say that a hypergraph H satisfies the Hall property if the following condition holds: If a subset of the vertices of H is coloured red and blue and if there are more red than blue vertices in total, then there is a hyperedge which contains more red than blue vertices.
Theorem(Conforti et al, 1996): H satiefies the Hall property if and only if it has a perfect matching, i.e., the vertex set can be partitioned by some hyperedges.
In the talk, we discuss a recent combinatorial approach to understand the structure of matchings in balanced hypergraphs by developing an analogue of the Gallai-Edmonds decomposition for graphs. This yields a new proof of the analogue of Hall's theorem mentioned above (joint work with R.Scheidweiler).
报告题目: A new class of Ramsey-Turán problems
报 告 人: Prof. Hao Li,LRI, Université de Paris-sud and CNRS, Orsay F-91405, France
时间地点: 2012年8月31日(星期五)上午10:00 思源楼703
摘       要: We introduce and study a new class of Ramsey-Turán problems, a typical example of which is the following one:
Let ε > 0 and G be a graph of sufficiently large order n with minimum degree δ (G) >3n/4. If the edges of G are colored in blue or red, then for all k ∈ [4, ?(1/8 ? ε) n?] , there exists a monochromatic cycle of length k.
报告题目: Moneyless strategy-proof mechanism on single-sunk policy domain:characterization and applications
报 告 人: Prof. Donglei Du,Faculty of Business Administration Univ. of New Brunswick, Canada
时间地点: 2012年6月20日(星期三)上午10:00 思源楼1013
摘       要: We completely characterize deterministic strategy-proof and group strategy-proof mechanisms on single-sunk public policy domain. The single-sunk domain can be used to model any allocation problem where a single output must be chosen in an interval with the assumption that agents' preferences have a single most dislike point--the sink--in the interval, and the preferences are increasing as one moves away from that sink. Practical domains like this appear in political voting system where each voter has his most-hated candidate and alternative candidates are evaluated by their proximity to this candidate or in obnoxious location problem, where each agent prefers to have the obnoxious location to be distant from his own location, among others. As applications of our characterization, we extend existing models and results and solve some open questions fromthe literature.
报告题目: On large girth subgraphs of dense graphs
报 告 人: Prof. Vojtech Rodl,Dept of Math and Computer Science Emory University, USA
时间地点: 2012年6月18日(星期三)上午10:30 思源楼712
摘       要: We will discuss some partial results on old conjectures of Erdos and Hajnal and a more recent conjecture of C. Thomassen
报告题目: Forbidden subgraphs and 3-coloring
报 告 人: Prof. Xingxing Yu,Department of Mathematics Georgia Inst. of Technology, USA
时间地点: 6月18日(星期三)上午9:30 思源楼712
摘       要: Motivated by Vizing's theorem, Randerath considered the problem of determining pairs of graphs (A, B) such that if a graph G contains neither A nor B as an induced subgraph then (G) (G)+1. In particular, he conjectured that if G is fork-free and triangle-free then (G) 3, where a fork is isomorphic to the graph obtained from K1,4 by subdividing two edges. We prove this conjecture under the additional condition when G is also C5-free.
报告题目: Some Combinatorial Problems Motivated by their Applications
报 告 人: Prof. Gyula O.H. Katona, Rényi Institute of Mathematics Budapest, Hungary
时间地点: 2012年6月7日上午10:00 思源楼703
摘       要: 1. Search problems. There is one unknown (e.g. defective) element x of an n-element set. We have to determine it by asking questions of type \is x 2 A?" for some subsets A. Of course the mathematical question is nding the minimum number of such questions under some conditions. We will show some examples.
2. Consider the relational model of databases. It is basically a matrix where the columns are the kinds of data (attributes), the rows are the data of one individual or object. We say that a set A of columns (attributes) functionally determines the set of columns B if there are no two di erent rows equal in A and di erent in B. The set of these functional dependencies can be equivalently described by a closure operation on the set of columns.Some properties of these closure operations are investigated.
3. A practical problem of identifying objects by labels (small pictures) that cannot be copied lead to a combinatorial problem of the following type.Having a family of k-element subsets, minimize the number of k ..1-element subsets included in one of them.
4. In addition, as a former director of Renyi Institute of Math, I will also make a brief introduction on its history and presence.
报告人简介 Katona教授是国际知名组合数学专家,欧洲科学院院士和匈牙利科学院院士,曾任匈牙利科学院瑞尼数学研究所所长(1996-2006)。http://www.renyi.hu/~ohkatona/

报告题目: Forbidden Intersection Patterns in the Families of Subsets
报 告 人: Prof. Gyula O.H. Katona Rényi, Institute of Mathematics Budapest, Hungary
时间地点: 2012年6月4日上午10:00 思源楼1013
摘       要: Let [n]={1,2, … ,n} be a finite set, families F of its subsets will be investigated. Sperner' theorem says that if there is no inclusion among the members of F then the largest family under this condition is the one contaning all n/2 -element subsets of [n]. The present paper surveys certain generalizations of this theorem. The maximum size of F is to be found under the condition that a certain configuration is excluded. The configuration here is always described by inclusions. More formally, let P be a poset. The maximum size of a family F 2[n] which does not contain P as a (non-necessarily induced) subposet is denoted by La(n, P). As an example, let the poset N consist of 4 elements illustrated here with 4 distinct sets satisfying A B, C B, C D. La(n, N) has been recently determined up to the second term by J.R. Griggs and the present author
报告题目: Algebraic Cayley Graphs
报 告 人: 万大庆 教授,University of California, Irvine
时间地点: 2011年12月22日下午3:00 S703
摘       要: Cayley graphs constructed from multiplicative groups of finite commutative algebras provide an ideal source of graphs in the design of communication networks. In this self-contained talk, we explain how the fundamental properties (connectedness, diameter) of such graphs can be studied via powerful tools from number theory and arithmetic algebraic geometry. We shall focus on the important example as studied by F. Chung, constructed using a finite extension of a finite field.
报告人简介: 万大庆:1991年在美国华盛顿大学获博士学位,导师Neal Koblitz教授。随后在拉斯维加斯的内华达大学任教四年,然后转至在宾夕法尼亚州立大学任教两年。1997年到美国加州大学欧文分校担任副教授,2001年起任教授。他的研究兴趣是数论和算术代数几何,尤其是有限域上的zeta函数和L-函数。他解决了几个长期存在的猜想,其中包括单位根zeta函数的Dwork猜想。近些年,他利用数论去研究算法,编码理论和计算机科学,成效不凡。详见:http://www.math.uci.edu/~dwan/
报告题目: Towards a Complexity Theory for Randomized Search Heuristics - Black-Box Models
报 告 人: Ms. Carola Winzen, Max Planck Institute for Informatics, Saarbruecken, Germany
时间地点: 2011年4月8日,10:00-11:00 思源楼 703
摘       要: Randomized search heuristics are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. A big step forward would be a useful complexity theory for such algorithms.

In this talk, we discuss the concept of so-called black-box complexity. The black-box complexity measures a problem's difficulty to be optimized by general purpose optimization algorithms. We enrich the two existing black-box complexity notions due to Wegener and other authors by the restrictions that not actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model gives more realistic complexity estimates for some problems, while for others the low complexities of the previous models still hold.

This is joint work with Benjamin Doerr and will appear in the Proceedings of the 6th International Computer Science Symposium in Russia (CSR 2011).

Ms. Carola Winzen is a PhD student in Computer Science at the Max-Planck-Institute for Informatics, Saarbruecken, Germany. Her work is support by the Google Europe Fellowship in Randomized Algorithms. Her research interests include theory of randomized search heuristics, geometric discrepancies, randomized and quasi-randomized algorithms.
报告题目: Truthful Approximations for Maximizing the Minimum Load
报 告 人: Dr. Rob van Stee, Max Planck Institute for Informatics, Saarbruecken, Germany
时间地点: 2011年4月6日,10:00-11:00 思源楼 703
摘       要: Designing truthful mechanisms for scheduling on related machines is a very important problem in single-parameter mechanism design. We consider the covering objective, that is we are interested in maximizing the minimum completion time of a machine. This problem falls into the class of problems where the optimal allocation can be truthfully implemented. A major open issue for this class is whether truthfulness affects the polynomial-time implementation.

We provide the first constant factor approximation for deterministic truthful mechanisms. In particular we come up with an approximation guarantee of 2+epsilon, significantly improving on the previous upper bound of min(m,(2+epsilon)s_m/s_1). Here epsilon is an arbitrarily small value, m is the number of machines, and s_i is the (reported) speed of machine i.

Dr. Rob van Stee is a senior research at the Max-Planck-Institute for Computer Science in Saarbrueck. His research interests include algorithmic mechanism design, price of anarchy, price of stability, online algorithms and approximation algorithms.
报告题目: Randomized Rumor Spreading in Social Networks
报 告 人: Professor Benjamin Doerr, Max Planck Institute for Informatics, Saarbruecken, Germany
时间地点: 2011年4月1日,10:00-11:00 思源楼 1013房间
摘       要: Randomized rumor spreading is a class of simple mechanisms that disseminate a piece of information in a network by having nodes of the network exchange information with randomly chosen neighbors. Such mechanisms are used as simple distributed algorithms maintaining the consistency of distributed data bases, but also to study existing processes like the spreading of viruses in computer networks.

In this work, we analyze the performance of randomized rumor spreading on preferential attachment graphs, which are believed to be a good model for many real-world networks including social networks. We show that a natural randomized rumor spreading mechanism makes a rumor known to all nodes of the network in sublogarithmic time. This is faster than the logarithmic times needed in all previous works regarding, e.g., complete graphs, classical random graphs or hypercubes. We observe a similar behavior experimentally in real networks.

This is joint work with Mahmoud Fouz (Saarland University) and Tobias Friedrich (MPI) and will appear in the Proceedings of STOC 2011

Prof. Dr. Benjamin Doerr obtained his PhD in Mathematics from the University of Kiel (Germany) in 2000. Since 2005, he is a senior research (tenured) at the Max-Planck-Institute for Computer Science in Saarbruecken. His research interests include probabilistic methods in discrete mathematics and computer science, algorithm engineering, quasirandomness, evolutionary algorithms and random structures like random graphs.
报告题目: Decomposition of graphs into forests
报 告 人: 朱绪鼎 浙江师范大学
时间地点: 2010年12月20日(星期一)下午15:30 思源楼709
摘       要:  
朱绪鼎教授现为浙江师范大学教授,曾担任台湾中山大学西湾讲座教授,第三批国家"千人计划"入选者。作为图论与组合优化研究领域的著名专家,朱绪鼎在图的染色理论、结构分析、演算法等领域做出了杰出的贡献,取得一系列重大研究成果,特别是创新发展了图的圆染色理论,使得该方向已成为当前国内外研究的热点之一。朱绪鼎曾先后在国际重要学术刊物上发表SCI研究论文130余篇,论文被同行引用1000余次。2007年,在ISI公布的、有全球900多位数学家入选的世界数学家被引用次数排名中,位列第67名。
   
报告题目: Some results and problems on spanning trees and factors of graphs
报 告 人: Prof. Mikio Kano,Ibaraki University, Department of Computer & Information Sciences
时间地点: 8月19日(星期三)上午10:00 思源楼705室
摘       要: 日本茨城大学Mikio Kano教授是著名的数学家,1984年获得日本大阪大学博士学位,在图论、离散几何等研究领域做出了多项重要工作,是国际公认的图论研究权威学者。已发 表论文60余篇,现担任国际权威组合数学杂志《图与组合》(Graphs and Combinatorics)的执行主编。在图的因子理论方面,Kano教授做出了一系列有影响的结果。Jin Akiyama教授的一个重大猜想"任何3n阶3-连通3-正则图都有一个P2 -因子"引起了国内外图论界的广泛关注,很多图论界的权威人物都致力于解决此猜想,但至今仍悬而未决。而Kano教授围绕此猜想做了大量的工作并取得了重 大的进展。他与合作者给出了一类具有[a,b]-因子的特殊的图,给出了图具有(1,f)-奇因子的充要条件,这个结论在很大程度上推广了图论领域领袖人 物Tutte教授关于图G具有完美匹配的经典结论。在path-因子理论方面,Kano教授与合作者给出了一系列关于(P2, P3) -因子、P3 -因子、P4 -因子的结论,并把它们应用到triominos覆盖问题的一些特殊情况。在离散几何领域,Kano教授在着色问题方面得到了一系列重要结果.
报告题目: Turan type results for sparse bipartite graphs
报 告 人: Dr. Tao Jiang,Dept of Math and Statistics Miami University
时间地点: 2009年3月3日10:00 思源楼1013
摘       要:

One of the fundamental problems in extremal graph theory is the Turan problem which asks for the largest number of edges in a simple $n$-vertex graph $G$ not containing a given graph $H$ as a subgraph. This largest number is called the Turan number of $H$ and is denoted by $ex(n,H)$. The Turan number is well understood for nonbipartite graphs. For general bipartite graphs, however, the problem remains very difficult.
After a brief introduction to the current status of the Turan problem for bipartite graphs, we discuss some Turan type results for bipartite graphs obtained through edge subdivision. One of these is a so-called topological clique: a graph obtained from subdividing edges of a complete graph. For each $t$ and sufficiently large $n$, we show that every $n$-vertex graph with at least $a(t) n^{1+\epsilon}$ edges, where $a(t)$ is a constant depending on $t$, contains a subdivision of $K_t$ in which each edge of $K_t$ is subdivided at most $c\log (1/\epsilon)/\epsilon$ times, where $c$ is an absolute constant. This improves an earlier result of Kostochka and Pyber. We also show that if H is obtained from iteratively adding a path of odd length at least $2k-1$ between a pair of adjacent vertices then $ex(n,H)=O(n^{1+1/k})$, which substantially generalizes the known result on the Turan numbers of even cycles..

(http://www.users.muohio.edu/jiangt/)

报告题目: When Biology meets Mathematics at synergy screening
报 告 人: Prof. Lixin Zhang (Institute of Microbiology, Chinese Academy of Sciences )
时间地点: 2008年6月26日9:00 究生院中关村教学楼N306
摘       要: The high mortality of fungal infections in immunocompromised patients and the limited availability of highly efficacious and safe agents demands the development of new antifungal therapeutics. However, infectious pathogens are composed of complex networking systems with redundant, convergent and divergent signaling pathways. To control fungal infection, multicomponent therapies along the disease pathway may need to be manipulated simultaneously for an effective treatment. In order to rapidly discover such agents, we developed a high throughput synergy screening (HTSS) strategy for novel microbial natural products.
报告题目: When Biology meets Mathematics at synergy screening
报 告 人: Prof. Lixin Zhang (Institute of Microbiology, Chinese Academy of Sciences )
时间地点: 2008年6月26日9:00 究生院中关村教学楼N306
摘       要: The high mortality of fungal infections in immunocompromised patients and the limited availability of highly efficacious and safe agents demands the development of new antifungal therapeutics. However, infectious pathogens are composed of complex networking systems with redundant, convergent and divergent signaling pathways. To control fungal infection, multicomponent therapies along the disease pathway may need to be manipulated simultaneously for an effective treatment. In order to rapidly discover such agents, we developed a high throughput synergy screening (HTSS) strategy for novel microbial natural products.
报告题目: Global inference of disease genes on the basis of biological networks
报 告 人: Prof. Rui Jiang (Department of Automation Tsinghua University )
时间地点: 2008年6月24日9:00 究生院中关村教学楼N306
摘       要: Deciphering the genetic basis of human diseases is an important goal of biomedical research. On the basis of the assumption that phenotypically similar diseases are caused by functionally related genes, we propose a computational framework that integrates human protein-protein interactions, disease phenotype similarities, and known gene-phenotype associations to capture the complex relationships between phenotypes and genotypes. We develop a tool named CIPHER to predict and prioritize disease genes, and we show that the global concordance between the human protein network and the phenotype network reliably predicts disease genes.
2008年
报告题目: Erdos-Ko-Rado with conditions on the minimum complementary degree
报 告 人: Prof. John Goldwasser (Dept of Mathematics, West Virginia University, USA )
时间地点: 2008年4月18日10:00 思源楼1013
摘       要: Let X={1,2,…,n}, 2k<n, and let X(k) denote the set of all subsets of X of size k. A subset F of X(k) is intersecting if no two of its elements are disjoint. The minimum complementary degree c(F) of F is the minimum over all i in X of the number of sets in F not containing i. We say F is complementary degree condition maximal (CDCM) if whenever a subset H of X(k) is intersecting with c(H)at least as large as c(F), then #H is at least as large as #F . Our result generalizes the Erdos-Ko-Rado and Hilton-Milner theorems and a theorem of Frankl's with conditions on the maximum degree.
当前位置:首页 > 学术报告 > 图论与网络研究中心学术报告