BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Yuri Rabinovich (University of Haifa)
DTSTART:20201201T173000Z
DTEND:20201201T180000Z
DTSTAMP:20260423T024830Z
UID:LA-CoCo/14
DESCRIPTION:Title: Large simple cycles in dense simplicial complexes\nby Yuri Rabinovich
(University of Haifa) as part of LA Combinatorics and Complexity Seminar\
n\n\nAbstract\nSimplicial complexes can be viewed as a higher dimensional
generalization of graphs\nwith a significantly richer structure than hyper
graphs. For example\, many graph theoretic\nnotions such as cycles\, cuts\
, eigenvalues\, etc.\, have natural analogues in\nsimplicial complexes\, a
s opposed to hypergraphs. Moreover\, in addition to Combinatorics\,\npower
ful methods from Linear Algebra\, Matroid Theory\, Algebraic Topology\, et
c.\,\ncan be $-$ and are $-$ employed in their study. \n\nIn the recent de
cades there has been a\nsignificant progress in the study of random simpli
cial complexes\, as well as in\nunderstanding their extremal properties. T
here are also some startling\napplications to Computer Science yet to be d
eveloped. \nThat said\, there remain many natural and seemingly simple ope
n problems in the theory of simplicial complexes. Here we focus on one suc
h problem\, which on a closer inspection turns out to be interesting and n
ontrivial.\n\nA classical theorem of Erdős and Gallai (1959)\, asserts th
at for an\nundirected graph $G=(V\,E)$\, if $|E| > 2k(|V|-1)$\, then $G$ c
ontains a cycle of length $> k$.\nIn other words\, the density of graph
is a lower bound for the size of the largest cycle in it\, up to a co
nstant factor. We show that the size of the largest simple $d$-cycle in a
simplicial $d$-complex is at least a square root of its density.\n\n Ba
sed on a joint work with Roy Meshulam and Ilan Newman.\n
LOCATION:https://researchseminars.org/talk/LA-CoCo/14/
END:VEVENT
END:VCALENDAR