Weekly Seminar of Combinatorics
Shahid Beheshti University

Talks:
Place:  The Seminar Room of Department of Mathematics 304/1,
Shahid Beheshti University

Seminars, Workshops , Conferences:

 Old Events: Workshop On Topological Combinatorics Wednesday, October 21, 2009 SBU Combinatorics Day Wednesday, March 4, 2009

Title: Generalized Fisher inequality

Speaker: Dr Elaheh Khamseh

Time and Date: 10:00-11:30, Saturday, 26 November, 2011

زمان: شنبه 5 آذر 1390 ساعت 11:30-10:00

Abstract: In this talk, we present miniatures 3 and 4 of the book thirty three miniatures. In fact, we present the proof of following theorems:

Theorem 1. If we have n citizens and m clubs such that each club has
to have an odd number of members and every two clubs must have an even
number of members in common, then m
n.

Theorem 2. If C_1,...,C_m are distinct and nonempty subsets of an
n-element set  such that all the intersections C_i ∩ C_j have the
same size, them m
n.

Title: Hypercubes: Problems and applications

Time and Date: 10:30-12:00, Saturday, 19 November, 2011

زمان: شنبه 28 آبان 1390 ساعت 12:00-10:30

Abstract: Hypercubes are very interesting objects which arise in many different
areas of mathematics. As a graph, a hypergraph Q_n is a graph in which the
vertices are all binary vectors of length n, and two vertices are adjacent if
and only if the Hamming distance between them is 1, i.e. their components
differ in one place. Hypercubes have many applications and there are many
challenging conjectures about them. In this talk we discuss some of these
conjectures and the applications. Our emphasis will be on square coloring,
galactic number and forced matchings.

Title: s Theory

Speaker: Bahman Ghandchi

Time and Date: 10:00-11:30, Saturday, 5 November, 2011

زمان: شنبه 14 آبان 1390 ساعت 11:30-10:00

Abstract: For a given graph $G$ we say graph $H$ is a minor of $G$ if it can be obtained from $G$ by a sequence of vertex deletions, edge deletions and edge contractions. Many Graph theorists admit that the most important unsolved problem in Graph theory is a conjecture by Hadwiger which states for every graph $G$ the graph $k_{\chi(G)}$ is a minor of $G$. This conjecture has led to a great interest among graph theorist and combinatorists to study Graph Minors Theory.

In this short talk we will cover basic definitions of Graph Minors Theory along with some interesting results in the field including but not limited to:

2- Extremal problems in Graph Minors Theory
3- Well quasi ordering and Wagner's conjecture
4- Graph Minors project by Seymour and Robertson

Title: Fractional Covering and Packing

Speaker: Farokhlagha Moazami

Time and Date: 10:00-11:30, Saturday, 29 October, 2011

زمان: شنبه 7 آبان 1390 ساعت 11:30-10:00

Abstract:  Our purpose in this talk is to reveal the rational side of graph theory. We seek to convert integer-based definitions and invariants into their fractional analogues. When we do this, we want to be sure that we have formulated the "right" definitions— conversions from integer to real that are, in some sense, natural. Here are two  ways we might judge if an integer-to-real conversion process is natural: First, when two seemingly disparate conversions yield the same concept, then we feel confident that the fractionalized concept is important (and not tied to how we made the conversion). Second, when the same conversion process works for a variety of concepts, then we feel we have arrived at a reasonable way to do the integer-to-real transformation. If a variety of attractive theorems arise from the new definition, then we can be certain that we are on the right track.

Title: Again Erdos's High Girth-High Chromatic Number Theorem
Speaker: Saeed Shaebani
Time and Date: 10:00-11:30, Saturday, 8 October, 2011

زمان: شنبه 16 مهر 1390 ساعت 11:30-10:00

Abstract: Erdos's celebrated theorem on High Girth-High Chromatic Number, states that for each naturak number k, there exists a graph G that min{χ(G) , g(G)} > k , where  χ(G) and g(G) stand for the chromatic number of G and the girth of G, respectively. This theorem maybe the beginning of using Probabilistic Methods in Combinatorics. In this talk, first we describe a new simple and nice proof of this theorem that uses only counting arguments. Then we talk about famous Shift Graphs that provide graphs with High Odd-Girth and High Chromatic Number. Finally, we decribe an application of Shift Graphs in a short proof of Welzl's Homomorphism Density Theorem.

Title: A sharp bound for the number of sets that pairwise intersect at k positive values
Speaker: Farokhlagha Moazami
Time and Date: 10:00-11:30, Saturday, 1 October, 2011

Abstract:
In this talk we prove that if L is a set of k positive integers and
{A1,. . .,Am} is a family of subsets of an n-element set satisfying |Ai ∩Aj| belongs to L, for all 1 ≤ i < j ≤m, then m≤ \sum_{i=0}^k {n-1 \choose i}.  The case k=1 was proven 50 years ago by Majumdar.

Title: On conflict-free coloring
Speaker: Erfan Rostami
Time and Date: 12:45-14:00, Sunday, 10 July, 2011

Abstract: A conflict-free coloring of a hypergraph H = (V,E) is an assignment of colors to V  such that in each hyperedge e there is at least one uniquely-colored vertex. This notion is an extension of the classical graph coloring. In this talk we are interested in study of this notion and its applications in the context of frequency assignment to cellular antennae, in battery consumption aspects of sensor networks, in RFID protocols and several other fields, and also we survey combinatorial and algorithmic aspects of this notion.