报告题目： 
Circumferences in 1tough 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 1tough 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 nvertex
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 kconnected
{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 ktree, and a tree with
at most k leaves is called a kended 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 ktree 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 ktrees and spanning kended 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 GallaiEdmonds 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 RamseyTurán problems 
报
告 人： 
Prof. Hao Li,LRI, Université de Parissud
and CNRS, Orsay F91405, France 
时间地点： 
2012年8月31日（星期五）上午10:00 思源楼703 
摘 要： 
We introduce and study a new class
of RamseyTurá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 strategyproof mechanism
on singlesunk 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
strategyproof and group strategyproof mechanisms on singlesunk
public policy domain. The singlesunk 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 pointthe sinkin 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 mosthated 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 3coloring 
报
告 人： 
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 forkfree and trianglefree 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 C5free. 

报告题目： 
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 nelement 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 dierent rows equal in
A and dierent 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 kelement subsets,
minimize the number of k ..1element 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教授是国际知名组合数学专家，欧洲科学院院士和匈牙利科学院院士，曾任匈牙利科学院瑞尼数学研究所所长（19962006）。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 (nonnecessarily 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 selfcontained
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  BlackBox 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 generalpurpose 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 socalled blackbox
complexity. The blackbox complexity measures a problem's
difficulty to be optimized by general purpose optimization
algorithms. We enrich the two existing blackbox 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 rankingbased
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 MaxPlanckInstitute 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 quasirandomized 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
singleparameter 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 polynomialtime 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 MaxPlanckInstitute 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 realworld 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
MaxPlanckInstitute 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 socalled 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 $2k1$ 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 proteinprotein
interactions, disease phenotype similarities, and known genephenotype
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年

报告题目： 
ErdosKoRado
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 ErdosKoRado and HiltonMilner
theorems and a theorem of Frankl's with conditions on the maximum
degree. 
