[Turkmath:9967] Seminer Duyurusu

[Sibel ÖZKAN]

Değerli liste üyeleri,

West Virginia Üniversitesi'nden John Goldwasser, 16 Temmuz Salı günü saat 15:15'te GYTE Matematik bölümünde aşağıda özetini bulabileceğiniz Maximum density of exact copies of a graph in the n-cube and a Turán surprise başlıklı bir konuşma verecektir. İlgilenen herkesi bekleriz.

Dear all,

John Goldwasser from West Virginia University will give a talk entitled Maximum density of exact copies of a graph in the n-cube and a Turán surprise at GYTE Mathematics department on July 16th  @ 3:15 pm. You can find the abstract below and all interested are welcome.

Sibel Özkan
---

Maximum density of exact copies of a graph in the n-cube and a Turán surprise

The n-cube Qn is the graph whose vertex set is the set of all binary n-tuples, with two vertices adjacent if and only if they differ in precisely one coordinate. Let G be an induced subgraph of the d-cube Qd.  We define f(d,G), the d-cube density of G, to be the limit -as n goes to infinity- of the maximum fraction, over all subsets J of the vertex set of the n-cube Qn, of sub-d-cubes of Qn whose intersection with J induces an exact copy of G (isomorphic to G, with the same embedding in Qd).

In general, it is difficult to determine f(d,G).  We show that if C is a “perfect” 8-cycle (4 pairs of vertices at distance 4) then f(4,C) = 3/32.  Surprisingly, to establish the upper bound we needed to determine the Turán density of {P4, P5}, where P4 = {abcd, abce, abde} and P5 = {abcd, abce, adef} and where the only 4-graphs (hypergraph where all the edges have 4 elements) allowed are those where there is a bipartition of the vertex set such that each edge has two vertices in each part.  (This is the limit, as n goes to infinity, of the maximum fraction of 4-subsets one can choose from an n-set, so that there is no copy of P4 or P5.)  We note that the link graphs of the vertex a in P4 and P5 are the 3-graphs known as K4- and F5, the forbidden 3-graphs in Bollobás’ well-known theorem on the maximum number of edges in a 3-graph where no edge contains the symmetric difference of two others.
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://yunus.listweb.bilkent.edu.tr/cgi-bin/mailman/private/turkmath/attachments/20140710/21287865/attachment.html>