BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Bhargav Narayanan (Rutgers University)
DTSTART:20200430T160000Z
DTEND:20200430T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/1
DESCRIPTION:Title: Finding homeomorphs\nby Bhargav Narayanan (Rutgers Universit
y) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nA number o
f interesting problems at the interface of topology and combinatorics aris
e when we view $r$-uniform hypergraphs as $(r-1)$-dimensional simplicial c
omplexes. I’ll talk about some recent developments around the Dirac and
Turan problems for 3-graphs or equivalently\, 2-complexes.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oleg Musin (University of Texas Rio Grande Valley)
DTSTART:20200507T160000Z
DTEND:20200507T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/2
DESCRIPTION:Title: Sphere Packings in Four Dimensions\nby Oleg Musin (Universit
y of Texas Rio Grande Valley) as part of Moscow Big Seminar of CombiGeo La
b\n\n\nAbstract\nIn this talk I'm going discuss reasonable approaches for
solutions to problems related to densest sphere packings in 4-dimensional
Euclidean space. I consider two long-standing open problems: the uniquenes
s of maximum kissing arrangements in 4 dimensions and the 24--cell conject
ure. Note that a proof of the 24-cell conjecture also proves that $D_4$ is
the densest sphere packing in 4 dimensions.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Will Perkins (UIC Chicago)
DTSTART:20200514T160000Z
DTEND:20200514T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/3
DESCRIPTION:Title: Counting independent sets with the cluster expansion\nby Wil
l Perkins (UIC Chicago) as part of Moscow Big Seminar of CombiGeo Lab\n\n\
nAbstract\nI'll present two tools from statistical physics\, abstract poly
mer models and the cluster expansion\, and show how they can be used in ex
tremal and enumerative combinatorics to give very good approximations to t
he number of (weighted) independent sets in certain graphs. In one applica
tion we use the cluster expansion in concert with Sapozhenko's container l
emma (and Galvin's generalization) to obtain new results on the weighted n
umber of independent sets in the hypercube and their typical structure. Jo
int work with Matthew Jenssen.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dor Minzer (IAS\, Prinston)
DTSTART:20200521T160000Z
DTEND:20200521T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/4
DESCRIPTION:Title: New sharp thresholds results and applications in extremal combin
atorics\nby Dor Minzer (IAS\, Prinston) as part of Moscow Big Seminar
of CombiGeo Lab\n\n\nAbstract\nThe classical hypercontractive inequality f
or the Boolean hypercube lies at the \ncore of many results in analysis of
Boolean functions. Though extensions of \nthe inequality to different dom
ains (e.g. the biased hypercube) are known\,\nthey are often times quantit
atively weak\, making them harder to apply.\nWe will discuss new forms of
this inequality and some of their consequences\,\nsuch as qualitatively ti
ght version of Bourgain's sharp threshold theorem\, as \nwell as a variant
that applies for sparse families. Time permitting\, we will also \ndiscus
s applications to two problems in extremal combinatorics: the (cross versi
on)\nof the Erdos matching conjecture\, and determining the extremal size
of families of\nvectors in $\\{0\,1\,\\dots\,m-1\\}^n$ avoiding a fixed in
tersection size\, for $m\\geq 3$.\n\n\nBased on joint works with Peter Kee
vash\, Noam Lifshitz and Eoin Long.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Razborov (University of Chicago\, Steklov Mathematical I
nstitute)
DTSTART:20200625T160000Z
DTEND:20200625T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/5
DESCRIPTION:Title: Limits of Dense Combinatorial Objects\nby Alexander Razborov
(University of Chicago\, Steklov Mathematical Institute) as part of Mosco
w Big Seminar of CombiGeo Lab\n\n\nAbstract\nThe theory of limits of discr
ete combinatorial objects has been thriving for\nover a decade. There are
two known approaches to it\, one is geometric and\nsemantic (``graph limit
s'') and another is algebraic and syntactic (``flag\nalgebras''). The lang
uage of graph limits is more intuitive and expressive\nwhile flag algebras
are more helpful when it comes to generalizations to\ncombinatorial objec
ts other than graphs\, as well as to concrete \ncalculations.\nIn this tal
k I will try to give a gentle introduction to the subject. Time\npermittin
g\, I will talk about general ideas behind our joint research with\nLeonar
do Coregliano attempting to build a unified theory using\nmodel-theoretica
l language and apply it to the study of quasi-randomness.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Conlon (Caltech)
DTSTART:20200528T160000Z
DTEND:20200528T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/6
DESCRIPTION:Title: Recent progress in extremal graph theory\nby David Conlon (C
altech) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nThe e
xtremal number $\\mathrm{ex}(n\, H)$ of a graph $H$ is the largest number
of edges in an $n$-vertex graph containing no copy of $H$. In this talk\,
we will describe some of the recent progress that has been made on underst
anding this question in the difficult case when $H$ is bipartite.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Korandi (University of Oxford)
DTSTART:20200604T160000Z
DTEND:20200604T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/7
DESCRIPTION:Title: Exact stability for Turán's theorem\nby Daniel Korandi (Uni
versity of Oxford) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbst
ract\nTurán's theorem says that an extremal $K_{r+1}$-free graph is $r$-p
artite. The Stability Theorem of Erdős and Simonovits shows that if a $K_
{r+1}$-free graph with n vertices has close to the maximal $t_r(n)$ edges\
, then it is close to being $r$-partite. In this talk we determine exactly
the $K_{r+1}$-free graphs with at least $m$ edges that are farthest from
being $r$-partite\, for any $m > t_r(n) - δn^2$. This extends work by Erd
ős\, Győri and Simonovits\, and proves a conjecture of Balogh\, Clemen\,
Lavrov\, Lidický and Pfender. Joint work with Alexander Roberts and Alex
Scott.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Grigory Kabatiansky (Skoltech)
DTSTART:20200611T160000Z
DTEND:20200611T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/8
DESCRIPTION:Title: Cover-free families of sets\, their generalizations and applicat
ions\nby Grigory Kabatiansky (Skoltech) as part of Moscow Big Seminar
of CombiGeo Lab\n\n\nAbstract\nWe start from the following question:\n\nWh
at is the maximal number of subsets of a given finite set such that no one
subset is covered by $t$ others?\n\nWe present the history of this proble
m which was discovered under different names in group testing\, coding the
ory and combinatorics. We consider variations of the problem\, in particul
ar\, Renyi-Ulam search with a lie. Then we embed the problem into more gen
eral question:\nHow to find unknown subset of a finite set?\n
LOCATION:https://researchseminars.org/talk/combgeostructures/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jacob Fox (Stanford Unversity)
DTSTART:20200618T160000Z
DTEND:20200618T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/9
DESCRIPTION:Title: Subset sums\, completeness and colorings\nby Jacob Fox (Stan
ford Unversity) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstrac
t\nWe develop novel techniques which allow us to prove a diverse range of
results relating to subset sums and complete sequences of positive integer
s\, including solutions to several long standing open problems. These incl
ude: solutions to the three problems of Burr and Erdös on Ramsey complete
sequences\, for which Erdös later offered a combined total of 350 analog
ous results for the new notion of density complete sequences\; the answer
to a question of Alon and Erdös on the minimum number of colors needed to
color the positive integers less than $n$ so that $n$ cannot be written a
s a monochromatic sum\; the exact determination of an extremal function in
troduced by Erdös and Graham and first studied by Alon on sets of integer
s avoiding a given subset sum\; and\, answering a question of Tran\, Vu an
d Wood\, a common strengthening of seminal results of Szemerédi-Vu and S
árközy on long arithmetic progressions in subset sums.\n\nBased on joint
work with David Conlon and Huy Tuan Pham.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:József Balogh (University of Illinois)
DTSTART:20200702T160000Z
DTEND:20200702T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/10
DESCRIPTION:Title: Independent sets in regular graphs\nby József Balogh (Univ
ersity of Illinois) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbs
tract\nEstimating the number of independent sets of regular graphs is in t
he center of attention recently.\n The classical result of Korshunov and S
apozhenko in 1983 counts the number of independent sets in the hypercube\,
and then shows that typical independent sets are not far from the trivial
construction. The main focus of the talk to prove similar results for the
middle two layers of the hypercube.\n\nThis is partly joint work with Bel
a Bollobas\, Ramon I. Garcia\, Lina Li\, Bhargav Narayanan\, Andrew Treglo
wn\, Adam Zs. Wagner.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fedor Petrov (St. Petersburg State University)
DTSTART:20200709T160000Z
DTEND:20200709T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/11
DESCRIPTION:Title: List colorings of direct products\nby Fedor Petrov (St. Pet
ersburg State University) as part of Moscow Big Seminar of CombiGeo Lab\n\
n\nAbstract\nLet $G=C_n\\times C_m$ be a toroidal grid (that is\, 4-regula
r graph)\, where $nm$ is even. We prove that this graph $G$ is 3-choosable
. We also prove some more general results about list colorings of direct p
roducts. The proofs are algebraic\, the starting point is Alon — Tarsi a
pplication of Combinatorial Nullstellensatz\, and the main difficulty is t
o prove that the corresponding coefficient of the graph polynomial is non-
zero.\n\nThe talk is based on joint results with Alexey Gordeev\, Zhiguo
Li and Zeling Shao. \n\nNo preliminary knowledge is required.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:József Solymosi (University of British Columbia)
DTSTART:20200716T160000Z
DTEND:20200716T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/12
DESCRIPTION:Title: Directions in an affine Galois plane and the clique number of t
he Paley graph\nby József Solymosi (University of British Columbia) a
s part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nWe prove that
the number of directions determined by a set of the form A×B⊂AG(2\,p)\,
where p is prime\, is at least $|A||B|−\\min\\{|A|\,|B|\\}+2$. We are u
sing the polynomial method: the Rédei polynomial with Szőnyi's extension
+ a simple variant of Stepanov's method. As an application of the result\
, we obtain an upper bound on the clique number of the Paley graph.\n\nBas
ed on joint work with Daniel Di Benedetto and Ethan White.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pavel Valtr (Charles University)
DTSTART:20200730T160000Z
DTEND:20200730T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/13
DESCRIPTION:Title: Holes and islands in random point sets\nby Pavel Valtr (Cha
rles University) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstra
ct\nFor $d\\ge 2$\, let $S$ be a finite set of points in $\\mathbb R^d$ in
general\nposition. A set $H$ of $k$ points from $S$ is a $k$-hole in $S$
if\nall points from $H$ lie on the boundary of the convex hull $conv(H)$ o
f\n$H$ and the interior of $conv(H)$ does not contain any point from $S$.
A\nset $I$ of $k$ points from $S$ is a $k$-island in $S$ if\n$conv(I)\\cap
S=I$. Note that each $k$-hole in $S$ is a $k$-island in $S$.\n\nFor fixed
positive integers $d\, k$ and a convex body $K$ in $\\mathbb R^d$ with\n$
d$-dimensional Lebesgue measure 1\, let $S$ be a set of $n$ points chosen\
nuniformly and independently at random from $K$. We show that the expected
\nnumber of $k$-islands in $S$ is in $O(n^d)$. In the case $k=d+1$\, we pr
ove\nthat the expected number of empty simplices (that is\, $(d+1)$-holes)
in\n$S$ is at most $2^{d-1}d!{n\\choose d}$. Our results improve and gene
ralize\nprevious bounds by Bárány and Füredi (1987)\, Valtr (1995)\,\nF
abila-Monroy and Huemer (2012)\, and Fabila-Monroy\, Huemer\, and Mitsche\
n(2015). Joint work with Martin Balko and Manfred Scheucher.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yufei Zhao (MIT)
DTSTART:20200813T160000Z
DTEND:20200813T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/14
DESCRIPTION:Title: The joints problem for varieties\nby Yufei Zhao (MIT) as pa
rt of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nWe generalize the
Guth-Katz joints theorem from lines to varieties. A special case of our re
sult says that N planes (2-flats) in 6 dimensions (over any field) have $O
(N^{3/2})$ joints\, where a joint is a point contained in a triple of thes
e planes not all lying in some hyperplane. Our most general result gives u
pper bounds\, tight up to constant factors\, for joints with multiplicitie
s for several sets of varieties of arbitrary dimensions (known as Carbery'
s conjecture). Our main innovation is a new way to extend the polynomial m
ethod to higher dimensional objects.\nJoint work with Jonathan Tidor and H
ung-Hsun Hans Yu\n
LOCATION:https://researchseminars.org/talk/combgeostructures/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zoltán Füredi (Rényi Institute Budapest and University of Illin
ois\, Urbana-Champaign)
DTSTART:20200903T160000Z
DTEND:20200903T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/15
DESCRIPTION:Title: A useful tool in combinatorics: Intersecting set-pair systems\nby Zoltán Füredi (Rényi Institute Budapest and University of Illino
is\, Urbana-Champaign) as part of Moscow Big Seminar of CombiGeo Lab\n\n\n
Abstract\nThe notion of cross intersecting set pair system (SPS) of size $
m$\, $\\Big(\\{A_i\\}_{i=1}^m\, \\{B_i\\}_{i=1}^m\\Big)$ with\n$A_i\\cap B
_i=\\emptyset$ and $A_i\\cap B_j\\ne\\emptyset$\, was introduced by\nBollo
bás and it became an important tool of extremal combinatorics.\nHis class
ical result states that $m\\le {a+b\\choose a}$ if $|A_i|\\le a$ and $|B_i
|\\le b$ for each $i$.\n\nAfter reviewing classical proofs\, applications
and generalizations\,\nour central problem is to see how this bound change
s\n with additional conditions.\n\nIn particular we consider {$1$-cross in
tersecting} set pair systems\, where\n $|A_i\\cap B_j|=1$ for all $i\\ne
j$.\nWe show connections to perfect graphs\, clique partitions of graphs\,
and finite geometries. \nMany problems are proposed. \n\nMost new resul
ts is a joint work with A. Gyárfás and Z. Király.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lutz Warnke (Georgia Institute of Technology)
DTSTART:20200910T160000Z
DTEND:20200910T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/16
DESCRIPTION:Title: Counting extensions in random graphs\nby Lutz Warnke (Georg
ia Institute of Technology) as part of Moscow Big Seminar of CombiGeo Lab\
n\n\nAbstract\nWe consider rooted subgraphs in random graphs\, i.e.\, exte
nsion counts such as (a) the number of triangles containing a given `root'
vertex\, or (b) the number of paths of length three connecting two given
`root' vertices.\n\nIn 1989 Spencer gave sufficient conditions for the eve
nt that\, whp\, all roots of the binomial random graph G(n\,p) have the sa
me asymptotic number of extensions\, i.e.\, $(1 \\pm \\varepsilon)$ times
their expected number. For the important strictly balanced case\, Spencer
also raised the fundamental question whether these conditions are necessar
y.\nWe answer this question by a careful second moment argument\, and disc
uss some open problems and cautionary examples for the general case.\n\nBa
sed on joint work with Matas Sileikis.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noga Alon (Prinston\, Tel-Aviv University)
DTSTART:20201119T160000Z
DTEND:20201119T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/17
DESCRIPTION:Title: Fair partitions: questions\, results and algorithms\nby Nog
a Alon (Prinston\, Tel-Aviv University) as part of Moscow Big Seminar of C
ombiGeo Lab\n\n\nAbstract\nA substantial number of results and conjectures
deal with the existence of\na set of prescribed type which contains a fai
r share from each member\nof a finite collection of objects in a space\, o
r the existence of\npartitions in which this is the case for every part. E
xamples include the\nHam-Sandwich Theorem in Measure Theory\, the Hobby-Ri
ce Theorem in\nApproximation Theory\, the Necklace Theorem and\nthe Ryser
Conjecture in Discrete Mathematics\, and more. The techniques\nin the stud
y of these results combine combinatorial\, topological\,\ngeometric and al
gebraic tools.\nI will describe the topic\, focusing on several recent\nex
istence results and their algorithmic aspects.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rob Morris (IMPA)
DTSTART:20201001T160000Z
DTEND:20201001T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/18
DESCRIPTION:Title: Erdos covering systems\nby Rob Morris (IMPA) as part of Mos
cow Big Seminar of CombiGeo Lab\n\n\nAbstract\nA covering system of the in
tegers is a finite collection of arithmetic progressions whose union is th
e set $\\mathbb{Z}$. The study of these objects was initiated by Erdos in
1950\, and over the following decades he asked a number of beautiful quest
ions about them. Most famously\, his so-called ``minimum modulus problem"
was resolved in 2015 by Hough\, who proved that in every covering system w
ith distinct moduli\, the minimum modulus is at most $10^{16}$.\n\nIn this
talk I will present a variant of Hough's method\, which turns out to be b
oth simpler and more powerful. In particular\, I will sketch a short proof
of Hough's theorem\, and discuss several further applications. I will als
o discuss a related result\, proved using a different method\, about the n
umber of minimal covering systems.\n\nJoint work with Paul Balister\, Bela
Bollobas\, Julian Sahasrabudhe and Marius Tiba.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Márton Naszódi (Loránd Eötvös University)
DTSTART:20201008T160000Z
DTEND:20201008T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/19
DESCRIPTION:Title: John ellipsoid for log-concave functions\nby Márton Naszó
di (Loránd Eötvös University) as part of Moscow Big Seminar of CombiGeo
Lab\n\n\nAbstract\nWe extend the notion of the largest volume ellipsoid c
ontained in a convex body to the setting of log-concave functions. As an a
pplication\, we prove a quantitative Helly-type result about the integral
of the pointwise minimum of a family of log-concave functions. \n\nJoint w
ork with Grigory Ivanov.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexey Garber (The University of Texas Rio Grande Valley)
DTSTART:20201015T160000Z
DTEND:20201015T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/20
DESCRIPTION:Title: Voronoi conjecture for five-dimensional parallelohedra\nby
Alexey Garber (The University of Texas Rio Grande Valley) as part of Mosco
w Big Seminar of CombiGeo Lab\n\n\nAbstract\nIn this talk I am going to di
scuss a well-known connection\nbetween lattices in $\\mathbb{R}^d$ and con
vex polytopes that tile\n$\\mathbb{R}^d$ with translations only.\n\nMy mai
n topic will be the Voronoi conjecture\, a century old conjecture\nwhich i
s\, while stated in very simple terms\, is still open in general.\nThe con
jecture states that every convex polytope that tiles\n$\\mathbb{R}^d$ with
translations can be obtained as an affine image of\nthe Voronoi domain fo
r some lattice.\n\nI plan to survey several known results on the Voronoi c
onjecture and\ngive an insight on a recent proof of the Voronoi conjecture
in the\nfive-dimensional case. The talk is based on a joint work with\nAl
exander Magazinov.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robert Robere (McGill University)
DTSTART:20201022T160000Z
DTEND:20201022T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/21
DESCRIPTION:Title: Nullstellensatz Size-Degree Trade-offs from the Reversible Pebb
ling Game\nby Robert Robere (McGill University) as part of Moscow Big
Seminar of CombiGeo Lab\n\n\nAbstract\nWe discuss recent work in which we
establish a tight relationship between Nullstellensatz certificates of the
so-called "pebbling" formulas --- which play an important role in a varie
ty of results in proof complexity\, circuit complexity\, and logic --- and
the "reversible pebbling game"\, a well-studied combinatorial pebbling ga
me on directed graphs. To be precise: we show that a graph $G$ can be reve
rsibly pebbled in time $t$ and space $s$ if and only if there is a Nullste
llensatz certificate of the pebbling formula over $G$ in length $t+1$ and
degree $s$. This result is independent of the underlying field of the Null
stellensatz certificate\, and implies sharp bounds for other proof systems
in the literature\; furthermore\, we can apply known reversible pebbling
time-space tradeoffs to obtain strong length-degree trade-offs for Nullste
llensatz certificates. To our knowledge these are the first strong tradeof
fs known for this propositional proof system.\n \n\nThis is joint work wit
h Susanna de Rezende\, Or Meir and Jakob Nordstrom.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julian Sahasrabudhe (University of Cambridge)
DTSTART:20201029T160000Z
DTEND:20201029T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/22
DESCRIPTION:Title: Combinatorial discrepancy in harmonic analysis\nby Julian S
ahasrabudhe (University of Cambridge) as part of Moscow Big Seminar of Com
biGeo Lab\n\n\nAbstract\nGiven a collection of finite sets $A_1\,\\dots\,
A_n$ in $\\{1\,\\dots\,n\\}$\, a basic problem in combinatorial discrepanc
y theory is to find a colouring $f:\\{1\,\\dots\, n\\}\\to \\{\\pm1\\}$ so
that each sum\n\\[\n\\left|\\sum_{x\\in A_i} f(x) \\right|\n\\]\nis as sm
all as possible. I will discuss how the sort of combinatorial and probabil
istic reasoning used to think about problems in combinatorial discrepancy
can used to solve an old conjecture of J.E.Littlewood in the area of harmo
nic analysis.\n\nThis talk is based on joint work with Balister\, Bollobá
s\, Morris and Tiba.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Wojciech Samotij (Tel Aviv University)
DTSTART:20201105T160000Z
DTEND:20201105T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/23
DESCRIPTION:Title: A sharp threshold for Ramsey’s theorem\nby Wojciech Samot
ij (Tel Aviv University) as part of Moscow Big Seminar of CombiGeo Lab\n\n
\nAbstract\nGiven graphs $G$ and $H$ and an integer $r \\ge 2$\, we write
$G \\to (H)_r$ if every $r$-colouring of the edges of $G$ contains contain
s a monochromatic copy of $H$. It follows from Ramsey's theorem that\, whe
n $n$ is sufficiently large\, $G \\to (H)_r$ is a nontrivial\, monotone pr
operty of subgraphs $G$ of $K_n$. The celebrated work of Rödl and Rucińs
ki from the 1990s located the threshold for this property in the binomial
random graph $G_{n\,p}$ for all $H$ and $r.$ We prove that this threshold
is sharp when $H$ is a clique or a cycle\, for every number of colours $r$
\; this extends earlier results of Friedgut\, Rödl\, Ruciński\, and Teta
li and of Schacht and Schulenburg.\n\n\nThis is joint work with Ehud Fried
gut\, Eden Kuperwasser\, and Mathias Schacht.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrei Vesnin (Tomsk State University)
DTSTART:20201112T160000Z
DTEND:20201112T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/24
DESCRIPTION:Title: Around right-angled hyperbolic polytopes\nby Andrei Vesnin
(Tomsk State University) as part of Moscow Big Seminar of CombiGeo Lab\n\n
\nAbstract\nWe will consider a class of polytopes which can be realized in
a hyperbolic space with all dihedral angled equal to $\\pi/2$. Since this
class contains fullerene polytopes\, we will describe fullerene graphs wi
th maximal Wiener index. We will discuss combinatorics and volumes of righ
t-angles polytopes\, construction of 3-manifolds from right-angled blocks\
, and knots and links related to such manifolds.\n\n\nTalk is based on joi
nt works with A. Dobrynin [1] and A. Egorov [2\,3].\n\n\n[1] A. Dobrynin\,
A. Vesnin\, On the Wiener Complexity and the Wiener Index of Fullerene Gr
aphs\, Mathematics\, 2019\, 7(11)\, 1071\, 16 pp. \n\n[2] A. Egorov\, A.
Vesnin\, Volume estimates for right-angled hyperbolic polyhedra\, preprint
arXiv:2010.11147\, 12pp. \n\n[3] A. Egorov\, A. Vesnin\, On correlation o
f hyperbolic volumes of fullerenes with their properties\, submitted\, 24
pp.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xavier Pérez Giménez (University of Nebraska-Lincoln)
DTSTART:20201210T160000Z
DTEND:20201210T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/25
DESCRIPTION:Title: The chromatic number of a random lift of $K_d$\nby Xavier P
érez Giménez (University of Nebraska-Lincoln) as part of Moscow Big Semi
nar of CombiGeo Lab\n\n\nAbstract\nAn $n$-lift of a graph $G$ is a graph f
rom which there is an $n$-to-$1$ covering map onto $G$. Amit\, Linial\, an
d Matou\\v sek (2002) raised the question of whether the chromatic number
of a random $n$-lift of $K_5$ is concentrated on a single value. We consid
er a more general problem\, and show that for fixed $d\\ge 3$ the chromati
c number of a random lift of $K_d$ is (asymptotically almost surely) eithe
r $k$ or $k+1$\, where $k$ is the smallest integer satisfying $d < 2k \\lo
g k$. Moreover\, we show that\, for roughly half of the values of $d$\, th
e chromatic number is concentrated on $k$. The argument for the upper-boun
d on the chromatic number uses the small subgraph conditioning method\, an
d it can be extended to random $n$-lifts of $G$\, for any fixed $d$-regula
r graph $G$. \n\n\n(This is joint work with JD Nir.)\n
LOCATION:https://researchseminars.org/talk/combgeostructures/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sergey Avvakumov (University of Copenhagen\, Denmark)
DTSTART:20201217T160000Z
DTEND:20201217T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/26
DESCRIPTION:Title: A subexponential size ${\\mathbb R}P^n$\nby Sergey Avvakumo
v (University of Copenhagen\, Denmark) as part of Moscow Big Seminar of Co
mbiGeo Lab\n\n\nAbstract\nA practical way to encode a manifold is to trian
gulate it.\nAmong all possible triangulations it makes sense to look for t
he minimal one\, which for the purpose of this talk means using the least
number of vertices.Consider now a family of manifolds such as $S^n$\, ${\\
mathbb R}P^n$\, $SO_n$\, etc. A natural question is how the size of the mi
nimal triangulation depends on $n$?\nSurprisingly\, except for the trivial
case of $S^n$\, our best lower and upper bounds are very far apart.For ${
\\mathbb R}P^n$ the current best lower and upper bounds are around $n^2$ a
nd $\\phi^n$\, respectively\, where $\\phi$ is the golden ratio.\nIn this
talk I will present the first triangulation of ${\\mathbb R}P^n$ with a su
bexponential\, $e^{(\\frac{1}{2}+o(1))\\sqrt{n}{\\log n}}$\, number of ver
tices.\nI will also state several open problems related to the topic.\n\nT
his is a joint work with Karim Adiprasito and Roman Karasev.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mikhail Rudnev
DTSTART:20210211T160000Z
DTEND:20210211T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/27
DESCRIPTION:Title: Erdös distance problem in positive characteristics\nby Mik
hail Rudnev as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nW
e'll review the state of the art of the finite field version of the Erdös
distinct distance problem and its variations. Recently there has been som
e interesting work in two and three dimensions. In particular\, it was sho
wn that in order that a point set in $F_p^2$ define a positive proportion
of the feasible p distances\, its cardinality needs to be bigger than $p^{
5/4}$. This improved the earlier lower bound $q^{4/3}$\, which holds over
$F_q$\, and for q non-prime cannot be improved. Coincidentally\, the same
quantitative improvement was recently made as to the Falconer problem in $
R^2$\, using decoupling\, which seems to be very far from the incidence ge
ometric approach over $F_p$ to be outlined.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Kolpakov (University of Neuchâtel\, Switzerland)
DTSTART:20210225T160000Z
DTEND:20210225T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/28
DESCRIPTION:Title: Space vectors forming rational angles\nby Alexander Kolpako
v (University of Neuchâtel\, Switzerland) as part of Moscow Big Seminar o
f CombiGeo Lab\n\n\nAbstract\nWe classify all sets of nonzero vectors in $
\\mathbb{R}^3$ such that the angle formed by each pair is a rational multi
ple of $\\pi$. The special case of four-element subsets lets us classify a
ll tetrahedra whose dihedral angles are multiples of $\\pi$\, solving a 19
76 problem of Conway and Jones: there are $2$ one-parameter families and $
59$ sporadic tetrahedra\, all but three of which are related to either the
icosidodecahedron or the $B_3$ root lattice. The proof requires the solut
ion in roots of unity of a $W(D_6)$-symmetric polynomial equation with $10
5$ monomials (the previous record was only $12$ monomials). \n\nThis is a
joint work with Kiran S. Kedlaya\, Bjorn Poonen\, and Michael Rubinstein.\
n
LOCATION:https://researchseminars.org/talk/combgeostructures/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dömötör Pálvölgyi (Eötvös Loránd University\, Hungary)
DTSTART:20210304T160000Z
DTEND:20210304T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/29
DESCRIPTION:Title: At most $4.47^n$ stable matchings\nby Dömötör Pálvölgy
i (Eötvös Loránd University\, Hungary) as part of Moscow Big Seminar of
CombiGeo Lab\n\n\nAbstract\nWe improve the upper bound for the maximum po
ssible number of stable matchings among $n$ men and $n$ women from $O(1310
72^n)$ to $4.47^n$. To establish this bound\, we develop a novel formulati
on of a probabilistic technique that is easy to apply and may be of indepe
ndent interest in counting other combinatorial objects. \n\nJoint work wit
h Cory Palmer.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrei Bulatov (Simon Fraser University)
DTSTART:20210318T160000Z
DTEND:20210318T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/30
DESCRIPTION:Title: On the Complexity of CSP-based Ideal Membership Problems\nb
y Andrei Bulatov (Simon Fraser University) as part of Moscow Big Seminar o
f CombiGeo Lab\n\n\nAbstract\nWe consider the Ideal Membership Problem (IM
P for short)\, in which we are given real polynomials $f_0\,f_1\,...\, f_k
$ and the question is to decide whether $f_0$ belongs to the ideal generat
ed by $f_1\,...\,f_k$. In the more stringent version the task is also to f
ind a proof of this fact. The IMP underlies many proof systems based on po
lynomials such as Nullstellensatz\, Polynomial Calculus\, and Sum-of-Squar
es. In the majority of such applications the IMP involves so called combin
atorial ideals that arise from a variety of discrete combinatorial problem
s. This restriction makes the IMP significantly easier and in some cases a
llows for an efficient algorithm to solve it.\n\n\nIn 2019 Mastrolilli ini
tiated a systematic study of IMPs arising from Constraint Satisfaction Pro
blems (CSP) of the form CSP(G)\, that is\, CSPs in which the type of const
raints is limited to relations from a set G. He described sets G on a 2-el
ement set that give rise to polynomial time solvable IMPs and showed that
for the remaining ones the problem is hard. We continue this line of resea
rch.\n\n\nFirst\, we show that many CSP techniques can be translated to IM
Ps thus allowing us to significantly improve the methods of studying the c
omplexity of the IMP. We also develop universal algebraic techniques for t
he IMP that have been so useful in the study of the CSP. This allows us to
prove a general necessary condition for the tractability of the IMP\, and
three sufficient ones. The sufficient conditions include IMPs arising fro
m systems of linear equations over GF(p)\, p prime\, and also some conditi
ons defined through special kinds of polymorphisms.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Igor Pak (UCLA)
DTSTART:20210325T160000Z
DTEND:20210325T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/31
DESCRIPTION:Title: Counting integer points in polytopes\nby Igor Pak (UCLA) as
part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nI will give a b
road survey of the recent progress on counting integer points in polytopes
of bounded dimension. I will emphasize both computational complexity asp
ects and applications which range from graph enumeration to Kronecker coef
ficients. The talk is aimed at a general audience.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yuval Wigderson (Stanford University)
DTSTART:20210401T160000Z
DTEND:20210401T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/32
DESCRIPTION:Title: Covering the hypercube with geometry and algebra\nby Yuval
Wigderson (Stanford University) as part of Moscow Big Seminar of CombiGeo
Lab\n\n\nAbstract\nWhat is the smallest number of hyperplanes needed to co
ver the vertices of the hypercube $\\{0\, 1\\}^n$? At least two hyperplane
s are needed\, and since we may take the parallel hyperplanes $x_1=0$ and
$x_1=1$\, we see that two hyperplanes suffice.\n \nAlthough the question a
bove is not particularly interesting\, there are many interesting variants
of it\, with connections to discrete geometry\, infinite Ramsey theory\,
theoretical computer science\, extremal combinatorics\, and beyond. One su
ch question is the following: how many hyperplanes are needed to cover all
vertices of the hypercube except the origin\, while not covering the orig
in? Here\, Alon and Füredi proved that at least $n$ hyperplanes are neede
d\, and it is easy to see that $n$ hyperplanes also suffice.\n \nAlthough
these problems are geometric in nature\, all known proofs of the Alon–F
üredi theorem use algebraic techniques\, relating the hyperplane covering
problem to a polynomial covering problem and then resolving this latter p
roblem. Miraculously\, the geometric problem and its algebraic relaxation
turn out to have the same answer. In this talk\, I will survey some result
s and questions about covers of the hypercube\, and then discuss a recent
result showing that for a natural higher-multiplicity version of the Alon
–Füredi theorem proposed by Clifton and Huang\, the geometric and algeb
raic problems (probably) have very different answers.\n\nJoint work with L
isa Sauermann.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anuj Dawar (University of Cambridge)
DTSTART:20210408T160000Z
DTEND:20210408T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/33
DESCRIPTION:Title: Circuit Lower Bounds Assuming Symmetry\nby Anuj Dawar (Univ
ersity of Cambridge) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAb
stract\nIt is a long-standing open question in complexity theory to show t
hat the permanent of a matrix cannot be computed by a polynomial-size arit
hmetic circuit. We proved an exponential lower bound on the size of any fa
mily of symmetric arithmetic circuits for computing the permanent. Here\,
symmetric means that the circuit is invariant under simultaneous row and c
olumn permutations of the matrix. In this talk\, I will explain the game-b
ased lower-bound methods and show how they can be used for deriving furthe
r lower bounds\, varying symmetry groups and other matrix polynomials\, su
ch as the determinant.\n\n\nJoint work with Gregory Wilsenach.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alex Scott (University of Oxford)
DTSTART:20210415T160000Z
DTEND:20210415T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/34
DESCRIPTION:Title: Combinatorics in the exterior algebra and the Two Families Theo
rem\nby Alex Scott (University of Oxford) as part of Moscow Big Semina
r of CombiGeo Lab\n\n\nAbstract\nThe Two Families Theorem of Bollobas says
the following: Let $(A_i\,B_i)$ be a sequence of pairs of sets such that
the $A_i$ have size $a$\, the $B_i$ have size $b$\, and $A_i$ and $B_j$ in
tersect if and only if $i$ and $j$ are distinct. Then the sequence has len
gth at most $(a+b\\choose a)$.\n\nThis beautiful result has many applicati
ons and has been generalized in two distinct ways. The first (which follow
s from the original result of Bollobas) allows the sets to have different
sizes\, and replaces the cardinality constraint with a weighted sum. The s
econd uses an elegant exterior algebra argument due to Lovasz and allows t
he intersection condition to be replaced by a skew intersection condition.
However\, there are no previous results that have versions of both condit
ions.\n\nIn this talk\, we will explain and extend the exterior algebra ap
proach. We investigate the combinatorial structure of subspaces of the ext
erior algebra of a finite-dimensional real vector space\, working in paral
lel with the extremal combinatorics of hypergraphs. As an application\, we
prove a new extension of the Two Families Theorem that allows both (some)
variation in set sizes and a skew intersection condition.\n\n\nThis is jo
int work with Elizabeth Wilmer (Oberlin).\n
LOCATION:https://researchseminars.org/talk/combgeostructures/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Liana Yepremyan (University of Oxford)
DTSTART:20210422T160000Z
DTEND:20210422T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/35
DESCRIPTION:Title: Size-Ramsey numbers of powers of hypergraph trees and long subd
ivisions\nby Liana Yepremyan (University of Oxford) as part of Moscow
Big Seminar of CombiGeo Lab\n\n\nAbstract\nThe $s$-colour size-Ramsey numb
er of a hypergraph $H$ is the minimum number of edges in a hypergraph $G$
whose every $s$-edge-colouring contains a monochromatic copy of $H$. \nWe
show that the $s$-colour size-Ramsey number of the $t$-power of the $r$-un
iform tight path on $n$ vertices is linear in $n$\, for every fixed $r\, s
\, t$\, thus answering a question of Dudek\, La Fleur\, Mubayi\, and R\\"o
dl (2017).\nIn fact\, we prove a stronger result that allows us to deduce
that powers of bounded degree hypergraph trees and of `long subdivisions'
of bounded degree hypergraphs have size-Ramsey numbers that are linear in
the number of vertices. This extends recent results about the linearity of
size-Ramsey numbers of powers of bounded degree trees and of long subdivi
sions of bounded degree graphs.\n \n\nThis is joint work with Shoham Letzt
er and Alexey Pokrovskiy.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Avi Wigderson (IAS\, Princeton)
DTSTART:20210429T160000Z
DTEND:20210429T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/36
DESCRIPTION:Title: Optimization\, Complexity and Math (or\, can we prove P ≠ NP
using gradient descent)\nby Avi Wigderson (IAS\, Princeton) as part of
Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nThis talk aims to summa
rize the status and goals of a broad research project. The main messages o
f this project are summarized below\; I plan to describe\, through example
s\, many of the concepts they refer to\, and the evolution of ideas leadin
g to them. No special background is assumed. \n\n\n(1) (1) We extend some
basic algorithms of convex optimization from Euclidean space to the far m
ore general setting of Riemannian manifolds\, capturing the symmetries of
non-commutative group actions. The main tools for analyzing these algorith
ms combine central results from invariant and representation theory.\n\n\n
\n(2) One main motivation for studying these problems and algorithms come
s from algebraic complexity theory\, especially attempts to separate Valia
nt’s algebraic analogs of the P and NP. Symmetries and group actions pla
y a key role in these attempts. \n\n\n(3) The new algorithms give exponen
tial (or better) improvements in run-time for solving algorithmic many spe
cific problems across CS\, Math and Physics. In particular\, in algebra (t
esting rational identities in non-commutative variables)\, in analysis (te
sting the feasibility and tightness of Brascamp-Lieb inequalities)\, in qu
antum information theory (to the quantum marginals problem)\, optimization
(testing membership in “moment polytopes”)\, and others. This work ex
poses old and new connections between these diverse areas.\n\n\nBased on m
any joint works in the past 5 years\, with Zeyuan Allen-Zhu\, Peter Burgis
ser\, Cole Franks\, Ankit Garg\, Leonid Gurvits\, Pavel Hrubes\, Yuanzhi L
i\, Visu Makam\, Rafael Oliveira and Michael Walter.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alex Cohen (Yale University)
DTSTART:20210506T160000Z
DTEND:20210506T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/37
DESCRIPTION:Title: Equivalence of 3-tensor ranks\nby Alex Cohen (Yale Universi
ty) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nWe prove
that the slice rank of a 3-tensor (a combinatorial notion introduced by Ta
o in the context of the cap-set problem)\, the analytic rank (a Fourier-th
eoretic notion introduced by Gowers and Wolf)\, and the geometric rank (a
recently introduced algebro-geometric notion) are all equivalent up to an
absolute constant. The proof uses tools from algebraic geometry to argue a
bout tangent spaces to certain determinantal varieties corresponding to th
e tensor. Our result settles open questions of Haramaty and Shpilka [STOC
2010]\, and of Lovett [Discrete Anal.\, 2019] for 3-tensors.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Gaifullin (Skoltech\, Steklov Mathematical Institute of
RAS)
DTSTART:20210520T160000Z
DTEND:20210520T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/38
DESCRIPTION:Title: Flexible polyhedra: Constructions\, Volume\, Scissors Congruenc
e\nby Alexander Gaifullin (Skoltech\, Steklov Mathematical Institute o
f RAS) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nFlexib
le polyhedra are polyhedral surfaces with rigid faces and hinges at edges
that admit non-trivial deformations\, that is\, deformations not induced b
y ambient isometries of the space. Main steps in theory of flexible polyhe
dra are: Bricard’s construction of self-intersecting flexible octahedra
(1897)\, Connelly’s construction of flexors\, i.e.\, non-self-intersecti
ng flexible polyhedra (1977)\, and Sabitov’s proof of the Bellows conjec
ture claiming that the volume of any flexible polyhedron remains constant
during the flexion (1996). In my talk I will give a survey of these classi
cal results and ideas behind them\, as well as of several more recent resu
lts by the speaker\, including the proof of Strong Bellows conjecture clai
ming that any flexible polyhedron in Euclidean three-space remains scissor
s congruent to itself during the flexion.\n\n\nJoint work with Leonid Igna
shchenko\, 2017.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexey Pokrovskiy (University College London)
DTSTART:20211028T160000Z
DTEND:20211028T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/39
DESCRIPTION:Title: Rainbow matchings in coloured multigraphs\nby Alexey Pokrov
skiy (University College London) as part of Moscow Big Seminar of CombiGeo
Lab\n\n\nAbstract\nThis talk will be about taking a coloured multigraph a
nd finding a rainbow matching using every colour. There's a variety of con
jectures that guarantee a matching like this in various classes of multigr
aphs (eg the Aharoni-Berger Conjecture). In the talk\, I'll discuss an eas
y technique to prove asymptotic versions of conjectures in this area. \n\n
\nThis is joint work with David Munhá Correia and Benny Sudakov.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Kwan (IST Austria)
DTSTART:20211104T160000Z
DTEND:20211104T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/40
DESCRIPTION:Title: Friendly bisections of random graphs\nby Matthew Kwan (IST
Austria) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nReso
lving a conjecture of Füredi\, we prove that almost every n-vertex graph
admits a partition of its vertex set into two parts of equal size in which
almost all vertices have more neighbours on their own side than across. O
ur proof involves some new techniques for \nstudying processes driven by d
egree information in random graphs\, which may be of general interest.\n\n
\nThis is joint work with Asaf Ferber\, Bhargav Narayanan\, Ashwin Sah and
\nMehtaab Sawhney\n
LOCATION:https://researchseminars.org/talk/combgeostructures/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pablo Soberón (Baruch College\, CUNY)
DTSTART:20211111T160000Z
DTEND:20211111T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/41
DESCRIPTION:Title: Mass partitions\, transversals\, and Stiefel manifolds\nby
Pablo Soberón (Baruch College\, CUNY) as part of Moscow Big Seminar of Co
mbiGeo Lab\n\n\nAbstract\nWe study mass partition problems related to geom
etric transversals. In this talk\, we focus on two problems. In the firs
t\, given a measure in R^d\, we seek to split R^d into few convex sets of
equal measure so that every hyperplane misses the interior of many regions
. In the second\, we extend recent ham sandwich results on Grassmannians
to impose geometric constraints on the dividing subspaces. The topologica
l backbone of both problems is the same\, and relies on extensions of the
Borsuk—Ulam theorem to Stiefel manifolds.\n\nThe contents of this talk a
re joint work with Ilani Axelrod-Freed and Michael Manta.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrey Kupavskii (CNRS\, France\; MIPT\, Russia)
DTSTART:20211125T160000Z
DTEND:20211125T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/42
DESCRIPTION:Title: Random restrictions and forbidden intersections\nby Andrey
Kupavskii (CNRS\, France\; MIPT\, Russia) as part of Moscow Big Seminar of
CombiGeo Lab\n\n\nAbstract\nRandom restrictions is a powerful tool that p
layed a central role in the breakthrough result by Alweiss et al. on the f
amous Erdos-Rado sunflower conjecture. In this talk\, I will describe a ne
w approach to getting a junta-type approximation for families of sets base
d on random restrictions. Such approximations have several exciting conseq
uences\, and I will present a couple of them. The first one is an upper bo
und on the size of regular k-uniform intersecting families similar to the
one obtained by Ellis\, Kalai and Narayanan for intersecting families unde
r a much stronger restriction of being transitive. The second one is signi
ficant progress on the t-intersection (and the Erdos-Sos forbidden one int
ersection) problem for permutations. Improving and simplifying previous re
sults\, we show that the largest family of permutations [n] -> [n] avoidin
g pairs of permutations with intersection exactly t-1\, has size at most
(n-t)!\, for t polynomial in n. Previously\, this was only known for fixed
t.\n \n\nJoint work with Dmitriy Zakharov.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pawel Pralat (Ryerson University)
DTSTART:20211202T160000Z
DTEND:20211202T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/43
DESCRIPTION:Title: Semi-random process\nby Pawel Pralat (Ryerson University) a
s part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nThe semi-rando
m graph process is a single-player game that begins with an empty graph on
n vertices. In each round\, a vertex u is presented to the player indepen
dently and uniformly at random. The player then adaptively selects a verte
x v and adds the edge uv to the graph. For a fixed monotone graph property
\, the objective of the player is to force the graph to satisfy this prope
rty with high probability in as few rounds as possible.\n\nDuring the talk
\, we will focus on the following problems: a) perfect matchings\, b) Hami
lton cycles\, c) constructing a subgraph isomorphic to an arbitrary fixed
graph G. We will also consider a natural generalization of the process to
s-uniform hypergraphs.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vishesh Jain (Stanford University)
DTSTART:20211209T160000Z
DTEND:20211209T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/44
DESCRIPTION:Title: Singularity of discrete random matrices\nby Vishesh Jain (S
tanford University) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbs
tract\nLet $M_n$ be an $n\\times n$ random matrix whose entries are i.i.d
copies of a discrete random variable $\\xi$. It has been conjectured that
the dominant reason for the singularity of $M_n$ is the event that a row o
r column of $M_n$ is zero\, or that two rows or columns of $M_n$ coincide
(up to a sign).\n\n I will discuss joint work with Ashwin Sah (MIT) and Me
htaab Sawhney (MIT)\, towards the resolution of this conjecture.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dmitrii Zhelezov (RICAM\, Linz\, Austria)
DTSTART:20211216T160000Z
DTEND:20211216T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/45
DESCRIPTION:Title: Sets inducing large additive doubling\nby Dmitrii Zhelezov
(RICAM\, Linz\, Austria) as part of Moscow Big Seminar of CombiGeo Lab\n\n
\nAbstract\nRephrasing the celebrated Freiman lemma in additive combinator
ics\, one can show that a finite set in Z^d containing a K-dimensional sim
plex has additive doubling at least ~K. We will discuss a novel framework
for studying how such induced doubling can be inherited from a more genera
l class of multi-dimensional subsets. It turns out that subsets of so-call
ed quasi-cubes induce large doubling no matter the dimension of the ambien
t set. Time permitting\, we will discuss how it allows to deduce a structu
ral theorem for sets with polynomially large additive doubling and an appl
ication to the ”few products\, many sums” problem of Bourgain and Chan
g.\n\nThis is joint work with I.Ruzsa\, D. Matlosci\, G. Shakan and D. Pal
völgyi\n
LOCATION:https://researchseminars.org/talk/combgeostructures/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrew Suk (University of California\, San Diego)
DTSTART:20220210T160000Z
DTEND:20220210T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/46
DESCRIPTION:Title: Hypergraph Ramsey numbers and an old problem of Erdos and Hajna
l\nby Andrew Suk (University of California\, San Diego) as part of Mos
cow Big Seminar of CombiGeo Lab\n\n\nAbstract\nThe Ramsey number r_k(s\,n)
is the minimum integer N\, such that for any red/blue coloring of the k-t
uples of {1\,2\,...\,N}\, there are s integers such that every k-tuple amo
ng them is red\, or there are n integers such that every k-tuple among the
m is blue. In this talk\, I will discuss known upper and lower bounds for
r_k(s\,n). I will also discuss another closely related function that was
introduced by Erdos and Hajnal in 1972.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Irit Dinur (Weizmann institute of science)
DTSTART:20220217T160000Z
DTEND:20220217T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/47
DESCRIPTION:Title: Locally testable codes via expanders\nby Irit Dinur (Weizma
nn institute of science) as part of Moscow Big Seminar of CombiGeo Lab\n\n
\nAbstract\nA locally testable code (LTC) is an error-correcting code that
admits a very efficient membership test. The tester reads a constant numb
er of (randomly - but not necessarily uniformly - chosen) bits from a give
n word and rejects words with probability proportional to their distance f
rom the code.\nLTCs were initially studied as important components of PCPs
\, and since then the topic has evolved on its own. High rate LTCs could b
e useful in practice: before attempting to decode a received word\, one ca
n save time by first quickly testing if it is close to the code. \n\nAn ou
tstanding open question has been whether there exist LTCs that are "good"
in the coding theory sense of having both constant relative distance and r
ate\, and at the same time testable with a constant number of queries.\n\n
In this talk\, I will describe a construction of such codes based on a new
object called a left-right Cayley complex\, which is a graph with squares
. We will see how the expansion of this graph plays a key role.\n \n\nJoin
t work with Shai Evra\, Ron Livne\, Alex Lubotzky\, and Shahar Mozes.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Géza Tóth (Alfréd Rényi Institute of Mathematics)
DTSTART:20220224T160000Z
DTEND:20220224T173000Z
DTSTAMP:20260422T212827Z
UID:combgeostructures/48
DESCRIPTION:Title: Disjointness graphs of short polygonal chains\nby Géza Tó
th (Alfréd Rényi Institute of Mathematics) as part of Moscow Big Seminar
of CombiGeo Lab\n\n\nAbstract\nThe disjointness graph of a set system is
a graph whose vertices\nare the sets\, two being connected by an edge if a
nd only if they are disjoint.\nIt is known that the disjointness graph $G$
of any system of segments in\nthe plane is $\\chi$-bounded\, that is\, it
s chromatic number $\\chi(G)$\nis upper bounded by a function of its cliqu
e number $\\omega(G)$.\n\nWe show that this statement does not remain true
for systems of polygonal\nchains of length $2$. Moreover\, for polygonal
chains of length\n$3$ the disjointness graph have arbitrarily large girth
and chromatic number.\nWe discuss some other\, related results.\n\n\nJoint
work with János Pach and Gábor Tardos.\n
LOCATION:https://researchseminars.org/talk/combgeostructures/48/
END:VEVENT
END:VCALENDAR