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:20260404T094428Z
UID:combgeostructures/1
DESCRIPTION:Title: Finding homeomorphs\nby Bhargav Narayanan (Rutgers Un
iversity) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nA n
umber of interesting problems at the interface of topology and combinatori
cs arise when we view $r$-uniform hypergraphs as $(r-1)$-dimensional simpl
icial complexes. I’ll talk about some recent developments around the Dir
ac and Turan problems for 3-graphs or equivalently\, 2-complexes.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oleg Musin (University of Texas Rio Grande Valley)
DTSTART:20200507T160000Z
DTEND:20200507T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/2
DESCRIPTION:Title: Sphere Packings in Four Dimensions\nby Oleg Musin (Un
iversity of Texas Rio Grande Valley) as part of Moscow Big Seminar of Comb
iGeo Lab\n\n\nAbstract\nIn this talk I'm going discuss reasonable approach
es for solutions to problems related to densest sphere packings in 4-dimen
sional Euclidean space. I consider two long-standing open problems: the un
iqueness of maximum kissing arrangements in 4 dimensions and the 24--cell
conjecture. 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://stable.researchseminars.org/talk/combgeostructures/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Will Perkins (UIC Chicago)
DTSTART:20200514T160000Z
DTEND:20200514T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/3
DESCRIPTION:Title: Counting independent sets with the cluster expansion\
nby Will Perkins (UIC Chicago) as part of Moscow Big Seminar of CombiGeo L
ab\n\n\nAbstract\nI'll present two tools from statistical physics\, abstra
ct polymer models and the cluster expansion\, and show how they can be use
d in extremal and enumerative combinatorics to give very good approximatio
ns to the number of (weighted) independent sets in certain graphs. In one
application we use the cluster expansion in concert with Sapozhenko's cont
ainer lemma (and Galvin's generalization) to obtain new results on the wei
ghted number of independent sets in the hypercube and their typical struct
ure. Joint work with Matthew Jenssen.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dor Minzer (IAS\, Prinston)
DTSTART:20200521T160000Z
DTEND:20200521T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/4
DESCRIPTION:Title: New sharp thresholds results and applications in extremal
combinatorics\nby Dor Minzer (IAS\, Prinston) as part of Moscow Big S
eminar of CombiGeo Lab\n\n\nAbstract\nThe classical hypercontractive inequ
ality for the Boolean hypercube lies at the \ncore of many results in anal
ysis of Boolean functions. Though extensions of \nthe inequality to differ
ent domains (e.g. the biased hypercube) are known\,\nthey are often times
quantitatively weak\, making them harder to apply.\nWe will discuss new fo
rms of this inequality and some of their consequences\,\nsuch as qualitati
vely tight version of Bourgain's sharp threshold theorem\, as \nwell as a
variant that applies for sparse families. Time permitting\, we will also \
ndiscuss applications to two problems in extremal combinatorics: the (cros
s version)\nof the Erdos matching conjecture\, and determining the extrema
l size of families of\nvectors in $\\{0\,1\,\\dots\,m-1\\}^n$ avoiding a f
ixed intersection size\, for $m\\geq 3$.\n\n\nBased on joint works with Pe
ter Keevash\, Noam Lifshitz and Eoin Long.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Razborov (University of Chicago\, Steklov Mathematical I
nstitute)
DTSTART:20200625T160000Z
DTEND:20200625T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/5
DESCRIPTION:Title: Limits of Dense Combinatorial Objects\nby Alexander R
azborov (University of Chicago\, Steklov Mathematical Institute) as part o
f Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nThe theory of limits o
f discrete combinatorial objects has been thriving for\nover a decade. The
re are two known approaches to it\, one is geometric and\nsemantic (``grap
h limits'') and another is algebraic and syntactic (``flag\nalgebras''). T
he language of graph limits is more intuitive and expressive\nwhile flag a
lgebras are more helpful when it comes to generalizations to\ncombinatoria
l objects other than graphs\, as well as to concrete \ncalculations.\nIn t
his talk I will try to give a gentle introduction to the subject. Time\npe
rmitting\, I will talk about general ideas behind our joint research with\
nLeonardo Coregliano attempting to build a unified theory using\nmodel-the
oretical language and apply it to the study of quasi-randomness.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Conlon (Caltech)
DTSTART:20200528T160000Z
DTEND:20200528T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/6
DESCRIPTION:Title: Recent progress in extremal graph theory\nby David Co
nlon (Caltech) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract
\nThe extremal 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
understanding this question in the difficult case when $H$ is bipartite.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Korandi (University of Oxford)
DTSTART:20200604T160000Z
DTEND:20200604T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/7
DESCRIPTION:Title: Exact stability for Turán's theorem\nby Daniel Koran
di (University of Oxford) as part of Moscow Big Seminar of CombiGeo Lab\n\
n\nAbstract\nTurán's theorem says that an extremal $K_{r+1}$-free graph i
s $r$-partite. The Stability Theorem of Erdős and Simonovits shows that i
f 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 farthes
t 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\, C
lemen\, Lavrov\, Lidický and Pfender. Joint work with Alexander Roberts a
nd Alex Scott.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Grigory Kabatiansky (Skoltech)
DTSTART:20200611T160000Z
DTEND:20200611T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/8
DESCRIPTION:Title: Cover-free families of sets\, their generalizations and a
pplications\nby Grigory Kabatiansky (Skoltech) as part of Moscow Big S
eminar of CombiGeo Lab\n\n\nAbstract\nWe start from the following question
:\n\nWhat 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
problem which was discovered under different names in group testing\, cod
ing theory and combinatorics. We consider variations of the problem\, in p
articular\, Renyi-Ulam search with a lie. Then we embed the problem into m
ore general question:\nHow to find unknown subset of a finite set?\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jacob Fox (Stanford Unversity)
DTSTART:20200618T160000Z
DTEND:20200618T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/9
DESCRIPTION:Title: Subset sums\, completeness and colorings\nby Jacob Fo
x (Stanford Unversity) as part of Moscow Big Seminar of CombiGeo Lab\n\n\n
Abstract\nWe develop novel techniques which allow us to prove a diverse ra
nge of results relating to subset sums and complete sequences of positive
integers\, including solutions to several long standing open problems. The
se include: solutions to the three problems of Burr and Erdös on Ramsey c
omplete sequences\, for which Erdös later offered a combined total of 350
analogous 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 ne
eded to color the positive integers less than $n$ so that $n$ cannot be wr
itten as a monochromatic sum\; the exact determination of an extremal func
tion introduced by Erdös and Graham and first studied by Alon on sets of
integers avoiding a given subset sum\; and\, answering a question of Tran\
, Vu and 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://stable.researchseminars.org/talk/combgeostructures/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:József Balogh (University of Illinois)
DTSTART:20200702T160000Z
DTEND:20200702T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/10
DESCRIPTION:Title: Independent sets in regular graphs\nby József Balog
h (University of Illinois) as part of Moscow Big Seminar of CombiGeo Lab\n
\n\nAbstract\nEstimating the number of independent sets of regular graphs
is in the center of attention recently.\n The classical result of Korshuno
v and Sapozhenko in 1983 counts the number of independent sets in the hype
rcube\, 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 w
ith Bela Bollobas\, Ramon I. Garcia\, Lina Li\, Bhargav Narayanan\, Andrew
Treglown\, Adam Zs. Wagner.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fedor Petrov (St. Petersburg State University)
DTSTART:20200709T160000Z
DTEND:20200709T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/11
DESCRIPTION:Title: List colorings of direct products\nby Fedor Petrov (
St. Petersburg 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
-regular graph)\, where $nm$ is even. We prove that this graph $G$ is 3-ch
oosable. We also prove some more general results about list colorings of d
irect products. The proofs are algebraic\, the starting point is Alon —
Tarsi application of Combinatorial Nullstellensatz\, and the main difficul
ty is to 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://stable.researchseminars.org/talk/combgeostructures/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:József Solymosi (University of British Columbia)
DTSTART:20200716T160000Z
DTEND:20200716T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/12
DESCRIPTION:Title: Directions in an affine Galois plane and the clique numb
er of the Paley graph\nby József Solymosi (University of British Colu
mbia) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nWe prov
e 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$. W
e are using the polynomial method: the Rédei polynomial with Szőnyi's ex
tension + 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\nBased on joint work with Daniel Di Benedetto and Ethan White.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pavel Valtr (Charles University)
DTSTART:20200730T160000Z
DTEND:20200730T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/13
DESCRIPTION:Title: Holes and islands in random point sets\nby Pavel Val
tr (Charles University) as part of Moscow Big Seminar of CombiGeo Lab\n\n\
nAbstract\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 $con
v(H)$ of\n$H$ and the interior of $conv(H)$ does not contain any point fro
m $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\nFo
r 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 e
xpected\nnumber of $k$-islands in $S$ is in $O(n^d)$. In the case $k=d+1$\
, we prove\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 a
nd generalize\nprevious bounds by Bárány and Füredi (1987)\, Valtr (199
5)\,\nFabila-Monroy and Huemer (2012)\, and Fabila-Monroy\, Huemer\, and M
itsche\n(2015). Joint work with Martin Balko and Manfred Scheucher.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yufei Zhao (MIT)
DTSTART:20200813T160000Z
DTEND:20200813T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/14
DESCRIPTION:Title: The joints problem for varieties\nby Yufei Zhao (MIT
) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nWe generali
ze the Guth-Katz joints theorem from lines to varieties. A special case of
our result 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 these planes not all lying in some hyperplane. Our most general result
gives upper bounds\, tight up to constant factors\, for joints with multip
licities for several sets of varieties of arbitrary dimensions (known as C
arbery's conjecture). Our main innovation is a new way to extend the polyn
omial method to higher dimensional objects.\nJoint work with Jonathan Tido
r and Hung-Hsun Hans Yu\n
LOCATION:https://stable.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:20260404T094428Z
UID:combgeostructures/15
DESCRIPTION:Title: A useful tool in combinatorics: Intersecting set-pair sy
stems\nby Zoltán Füredi (Rényi Institute Budapest and University of
Illinois\, Urbana-Champaign) as part of Moscow Big Seminar of CombiGeo La
b\n\n\nAbstract\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
\nBollobás and it became an important tool of extremal combinatorics.\nHi
s classical result states that $m\\le {a+b\\choose a}$ if $|A_i|\\le a$ an
d $|B_i|\\le b$ for each $i$.\n\nAfter reviewing classical proofs\, applic
ations and generalizations\,\nour central problem is to see how this bound
changes\n with additional conditions.\n\nIn particular we consider {$1$-c
ross intersecting} 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 g
raphs\, and finite geometries. \nMany problems are proposed. \n\nMost ne
w results is a joint work with A. Gyárfás and Z. Király.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lutz Warnke (Georgia Institute of Technology)
DTSTART:20200910T160000Z
DTEND:20200910T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/16
DESCRIPTION:Title: Counting extensions in random graphs\nby Lutz Warnke
(Georgia Institute of Technology) as part of Moscow Big Seminar of CombiG
eo Lab\n\n\nAbstract\nWe consider rooted subgraphs in random graphs\, i.e.
\, extension 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 event that\, whp\, all roots of the binomial random graph G(n\,p) have
the same asymptotic number of extensions\, i.e.\, $(1 \\pm \\varepsilon)$
times their expected number. For the important strictly balanced case\, S
pencer also raised the fundamental question whether these conditions are n
ecessary.\nWe answer this question by a careful second moment argument\, a
nd discuss some open problems and cautionary examples for the general case
.\n\nBased on joint work with Matas Sileikis.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noga Alon (Prinston\, Tel-Aviv University)
DTSTART:20201119T160000Z
DTEND:20201119T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/17
DESCRIPTION:Title: Fair partitions: questions\, results and algorithms\
nby Noga Alon (Prinston\, Tel-Aviv University) as part of Moscow Big Semin
ar of CombiGeo Lab\n\n\nAbstract\nA substantial number of results and conj
ectures deal with the existence of\na set of prescribed type which contain
s a fair share from each member\nof a finite collection of objects in a sp
ace\, or the existence of\npartitions in which this is the case for every
part. Examples include the\nHam-Sandwich Theorem in Measure Theory\, the H
obby-Rice Theorem in\nApproximation Theory\, the Necklace Theorem and\nthe
Ryser Conjecture in Discrete Mathematics\, and more. The techniques\nin t
he study of these results combine combinatorial\, topological\,\ngeometric
and algebraic tools.\nI will describe the topic\, focusing on several rec
ent\nexistence results and their algorithmic aspects.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rob Morris (IMPA)
DTSTART:20201001T160000Z
DTEND:20201001T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/18
DESCRIPTION:Title: Erdos covering systems\nby Rob Morris (IMPA) as part
of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nA covering system of
the integers is a finite collection of arithmetic progressions whose unio
n is the set $\\mathbb{Z}$. The study of these objects was initiated by Er
dos in 1950\, and over the following decades he asked a number of beautifu
l questions about them. Most famously\, his so-called ``minimum modulus pr
oblem" was resolved in 2015 by Hough\, who proved that in every covering s
ystem with distinct moduli\, the minimum modulus is at most $10^{16}$.\n\n
In this talk I will present a variant of Hough's method\, which turns out
to be both simpler and more powerful. In particular\, I will sketch a shor
t proof of Hough's theorem\, and discuss several further applications. I w
ill also discuss a related result\, proved using a different method\, abou
t the number of minimal covering systems.\n\nJoint work with Paul Balister
\, Bela Bollobas\, Julian Sahasrabudhe and Marius Tiba.\n
LOCATION:https://stable.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:20260404T094428Z
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 C
ombiGeo Lab\n\n\nAbstract\nWe extend the notion of the largest volume elli
psoid contained in a convex body to the setting of log-concave functions.
As an application\, we prove a quantitative Helly-type result about the in
tegral of the pointwise minimum of a family of log-concave functions. \n\n
Joint work with Grigory Ivanov.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexey Garber (The University of Texas Rio Grande Valley)
DTSTART:20201015T160000Z
DTEND:20201015T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/20
DESCRIPTION:Title: Voronoi conjecture for five-dimensional parallelohedra\nby Alexey Garber (The University of Texas Rio Grande Valley) as part o
f Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nIn this talk I am goin
g to discuss a well-known connection\nbetween lattices in $\\mathbb{R}^d$
and convex polytopes that tile\n$\\mathbb{R}^d$ with translations only.\n\
nMy main topic will be the Voronoi conjecture\, a century old conjecture\n
which is\, while stated in very simple terms\, is still open in general.\n
The conjecture states that every convex polytope that tiles\n$\\mathbb{R}^
d$ with translations can be obtained as an affine image of\nthe Voronoi do
main for some lattice.\n\nI plan to survey several known results on the Vo
ronoi conjecture and\ngive an insight on a recent proof of the Voronoi con
jecture in the\nfive-dimensional case. The talk is based on a joint work w
ith\nAlexander Magazinov.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robert Robere (McGill University)
DTSTART:20201022T160000Z
DTEND:20201022T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/21
DESCRIPTION:Title: Nullstellensatz Size-Degree Trade-offs from the Reversib
le Pebbling Game\nby Robert Robere (McGill University) as part of Mosc
ow Big Seminar of CombiGeo Lab\n\n\nAbstract\nWe discuss recent work in wh
ich we establish a tight relationship between Nullstellensatz certificates
of the so-called "pebbling" formulas --- which play an important role in
a variety of results in proof complexity\, circuit complexity\, and logic
--- and the "reversible pebbling game"\, a well-studied combinatorial pebb
ling game on directed graphs. To be precise: we show that a graph $G$ can
be reversibly pebbled in time $t$ and space $s$ if and only if there is a
Nullstellensatz certificate of the pebbling formula over $G$ in length $t+
1$ and degree $s$. This result is independent of the underlying field of t
he Nullstellensatz certificate\, and implies sharp bounds for other proof
systems in the literature\; furthermore\, we can apply known reversible pe
bbling time-space tradeoffs to obtain strong length-degree trade-offs for
Nullstellensatz certificates. To our knowledge these are the first strong
tradeoffs known for this propositional proof system.\n \n\nThis is joint w
ork with Susanna de Rezende\, Or Meir and Jakob Nordstrom.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julian Sahasrabudhe (University of Cambridge)
DTSTART:20201029T160000Z
DTEND:20201029T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/22
DESCRIPTION:Title: Combinatorial discrepancy in harmonic analysis\nby J
ulian Sahasrabudhe (University of Cambridge) as part of Moscow Big Seminar
of CombiGeo Lab\n\n\nAbstract\nGiven a collection of finite sets $A_1\,\\
dots\, A_n$ in $\\{1\,\\dots\,n\\}$\, a basic problem in combinatorial dis
crepancy 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\\]\ni
s as small as possible. I will discuss how the sort of combinatorial and p
robabilistic reasoning used to think about problems in combinatorial discr
epancy can used to solve an old conjecture of J.E.Littlewood in the area o
f harmonic analysis.\n\nThis talk is based on joint work with Balister\, B
ollobás\, Morris and Tiba.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Wojciech Samotij (Tel Aviv University)
DTSTART:20201105T160000Z
DTEND:20201105T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/23
DESCRIPTION:Title: A sharp threshold for Ramsey’s theorem\nby Wojciec
h Samotij (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
contains a monochromatic copy of $H$. It follows from Ramsey's theorem tha
t\, when $n$ is sufficiently large\, $G \\to (H)_r$ is a nontrivial\, mono
tone property of subgraphs $G$ of $K_n$. The celebrated work of Rödl and
Ruciński from the 1990s located the threshold for this property in the bi
nomial random graph $G_{n\,p}$ for all $H$ and $r.$ We prove that this thr
eshold is sharp when $H$ is a clique or a cycle\, for every number of colo
urs $r$\; this extends earlier results of Friedgut\, Rödl\, Ruciński\, a
nd Tetali and of Schacht and Schulenburg.\n\n\nThis is joint work with Ehu
d Friedgut\, Eden Kuperwasser\, and Mathias Schacht.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrei Vesnin (Tomsk State University)
DTSTART:20201112T160000Z
DTEND:20201112T173000Z
DTSTAMP:20260404T094428Z
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 real
ized in a hyperbolic space with all dihedral angled equal to $\\pi/2$. Sin
ce this class contains fullerene polytopes\, we will describe fullerene gr
aphs with maximal Wiener index. We will discuss combinatorics and volumes
of right-angles polytopes\, construction of 3-manifolds from right-angled
blocks\, and knots and links related to such manifolds.\n\n\nTalk is based
on joint works with A. Dobrynin [1] and A. Egorov [2\,3].\n\n\n[1] A. Dob
rynin\, A. Vesnin\, On the Wiener Complexity and the Wiener Index of Fulle
rene Graphs\, Mathematics\, 2019\, 7(11)\, 1071\, 16 pp. \n\n[2] A. Egoro
v\, A. Vesnin\, Volume estimates for right-angled hyperbolic polyhedra\, p
reprint arXiv:2010.11147\, 12pp. \n\n[3] A. Egorov\, A. Vesnin\, On correl
ation of hyperbolic volumes of fullerenes with their properties\, submitte
d\, 24 pp.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xavier Pérez Giménez (University of Nebraska-Lincoln)
DTSTART:20201210T160000Z
DTEND:20201210T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/25
DESCRIPTION:Title: The chromatic number of a random lift of $K_d$\nby X
avier Pérez Giménez (University of Nebraska-Lincoln) as part of Moscow B
ig Seminar of CombiGeo Lab\n\n\nAbstract\nAn $n$-lift of a graph $G$ is a
graph from which there is an $n$-to-$1$ covering map onto $G$. Amit\, Lini
al\, and 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
consider a more general problem\, and show that for fixed $d\\ge 3$ the c
hromatic number of a random lift of $K_d$ is (asymptotically almost surely
) either $k$ or $k+1$\, where $k$ is the smallest integer satisfying $d <
2k \\log k$. Moreover\, we show that\, for roughly half of the values of $
d$\, the chromatic number is concentrated on $k$. The argument for the upp
er-bound on the chromatic number uses the small subgraph conditioning meth
od\, and it can be extended to random $n$-lifts of $G$\, for any fixed $d$
-regular graph $G$. \n\n\n(This is joint work with JD Nir.)\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sergey Avvakumov (University of Copenhagen\, Denmark)
DTSTART:20201217T160000Z
DTEND:20201217T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/26
DESCRIPTION:Title: A subexponential size ${\\mathbb R}P^n$\nby Sergey A
vvakumov (University of Copenhagen\, Denmark) as part of Moscow Big Semina
r of CombiGeo Lab\n\n\nAbstract\nA practical way to encode a manifold is t
o triangulate it.\nAmong all possible triangulations it makes sense to loo
k for the 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 minimal 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$ and $\\phi^n$\, respectively\, where $\\phi$ is the golden ratio.\nI
n this talk I will present the first triangulation of ${\\mathbb R}P^n$ wi
th a subexponential\, $e^{(\\frac{1}{2}+o(1))\\sqrt{n}{\\log n}}$\, number
of vertices.\nI will also state several open problems related to the topi
c.\n\nThis is a joint work with Karim Adiprasito and Roman Karasev.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mikhail Rudnev
DTSTART:20210211T160000Z
DTEND:20210211T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/27
DESCRIPTION:Title: Erdös distance problem in positive characteristics\
nby Mikhail Rudnev as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbst
ract\nWe'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 b
een some interesting work in two and three dimensions. In particular\, it
was shown that in order that a point set in $F_p^2$ define a positive prop
ortion of the feasible p distances\, its cardinality needs to be bigger th
an $p^{5/4}$. This improved the earlier lower bound $q^{4/3}$\, which hold
s over $F_q$\, and for q non-prime cannot be improved. Coincidentally\, th
e same quantitative improvement was recently made as to the Falconer probl
em in $R^2$\, using decoupling\, which seems to be very far from the incid
ence geometric approach over $F_p$ to be outlined.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Kolpakov (University of Neuchâtel\, Switzerland)
DTSTART:20210225T160000Z
DTEND:20210225T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/28
DESCRIPTION:Title: Space vectors forming rational angles\nby Alexander
Kolpakov (University of Neuchâtel\, Switzerland) as part of Moscow Big Se
minar of CombiGeo Lab\n\n\nAbstract\nWe classify all sets of nonzero vecto
rs in $\\mathbb{R}^3$ such that the angle formed by each pair is a rationa
l multiple of $\\pi$. The special case of four-element subsets lets us cla
ssify all tetrahedra whose dihedral angles are multiples of $\\pi$\, solvi
ng a 1976 problem of Conway and Jones: there are $2$ one-parameter familie
s and $59$ sporadic tetrahedra\, all but three of which are related to eit
her the icosidodecahedron or the $B_3$ root lattice. The proof requires th
e solution in roots of unity of a $W(D_6)$-symmetric polynomial equation w
ith $105$ monomials (the previous record was only $12$ monomials). \n\nThi
s is a joint work with Kiran S. Kedlaya\, Bjorn Poonen\, and Michael Rubin
stein.\n
LOCATION:https://stable.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:20260404T094428Z
UID:combgeostructures/29
DESCRIPTION:Title: At most $4.47^n$ stable matchings\nby Dömötör Pá
lvölgyi (Eötvös Loránd University\, Hungary) as part of Moscow Big Sem
inar of CombiGeo Lab\n\n\nAbstract\nWe improve the upper bound for the max
imum possible number of stable matchings among $n$ men and $n$ women from
$O(131072^n)$ to $4.47^n$. To establish this bound\, we develop a novel fo
rmulation of a probabilistic technique that is easy to apply and may be of
independent interest in counting other combinatorial objects. \n\nJoint w
ork with Cory Palmer.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrei Bulatov (Simon Fraser University)
DTSTART:20210318T160000Z
DTEND:20210318T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/30
DESCRIPTION:Title: On the Complexity of CSP-based Ideal Membership Problems
\nby Andrei Bulatov (Simon Fraser University) as part of Moscow Big Se
minar of CombiGeo Lab\n\n\nAbstract\nWe consider the Ideal Membership Prob
lem (IMP 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
generated by $f_1\,...\,f_k$. In the more stringent version the task is al
so to find a proof of this fact. The IMP underlies many proof systems base
d on polynomials such as Nullstellensatz\, Polynomial Calculus\, and Sum-o
f-Squares. In the majority of such applications the IMP involves so called
combinatorial ideals that arise from a variety of discrete combinatorial
problems. This restriction makes the IMP significantly easier and in some
cases allows for an efficient algorithm to solve it.\n\n\nIn 2019 Mastroli
lli initiated a systematic study of IMPs arising from Constraint Satisfact
ion Problems (CSP) of the form CSP(G)\, that is\, CSPs in which the type o
f constraints is limited to relations from a set G. He described sets G on
a 2-element set that give rise to polynomial time solvable IMPs and showe
d that for the remaining ones the problem is hard. We continue this line o
f research.\n\n\nFirst\, we show that many CSP techniques can be translate
d to IMPs thus allowing us to significantly improve the methods of studyin
g the complexity of the IMP. We also develop universal algebraic technique
s for the IMP that have been so useful in the study of the CSP. This allow
s us to prove a general necessary condition for the tractability of the IM
P\, and three sufficient ones. The sufficient conditions include IMPs aris
ing from systems of linear equations over GF(p)\, p prime\, and also some
conditions defined through special kinds of polymorphisms.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Igor Pak (UCLA)
DTSTART:20210325T160000Z
DTEND:20210325T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/31
DESCRIPTION:Title: Counting integer points in polytopes\nby Igor Pak (U
CLA) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nI will g
ive a broad survey of the recent progress on counting integer points in po
lytopes of bounded dimension. I will emphasize both computational complex
ity aspects and applications which range from graph enumeration to Kroneck
er coefficients. The talk is aimed at a general audience.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yuval Wigderson (Stanford University)
DTSTART:20210401T160000Z
DTEND:20210401T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/32
DESCRIPTION:Title: Covering the hypercube with geometry and algebra\nby
Yuval Wigderson (Stanford University) as part of Moscow Big Seminar of Co
mbiGeo Lab\n\n\nAbstract\nWhat is the smallest number of hyperplanes neede
d to cover the vertices of the hypercube $\\{0\, 1\\}^n$? At least two hyp
erplanes 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 que
stion above is not particularly interesting\, there are many interesting v
ariants of it\, with connections to discrete geometry\, infinite Ramsey th
eory\, theoretical computer science\, extremal combinatorics\, and beyond.
One such question is the following: how many hyperplanes are needed to co
ver all vertices of the hypercube except the origin\, while not covering t
he origin? Here\, Alon and Füredi proved that at least $n$ hyperplanes ar
e needed\, and it is easy to see that $n$ hyperplanes also suffice.\n \nAl
though these problems are geometric in nature\, all known proofs of the Al
on–Füredi theorem use algebraic techniques\, relating the hyperplane co
vering problem to a polynomial covering problem and then resolving this la
tter problem. Miraculously\, the geometric problem and its algebraic relax
ation turn out to have the same answer. In this talk\, I will survey some
results and questions about covers of the hypercube\, and then discuss a r
ecent result showing that for a natural higher-multiplicity version of the
Alon–Füredi theorem proposed by Clifton and Huang\, the geometric and
algebraic problems (probably) have very different answers.\n\nJoint work w
ith Lisa Sauermann.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anuj Dawar (University of Cambridge)
DTSTART:20210408T160000Z
DTEND:20210408T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/33
DESCRIPTION:Title: Circuit Lower Bounds Assuming Symmetry\nby Anuj Dawa
r (University of Cambridge) as part of Moscow Big Seminar of CombiGeo Lab\
n\n\nAbstract\nIt is a long-standing open question in complexity theory to
show that the permanent of a matrix cannot be computed by a polynomial-si
ze arithmetic circuit. We proved an exponential lower bound on the size of
any family of symmetric arithmetic circuits for computing the permanent.
Here\, symmetric means that the circuit is invariant under simultaneous ro
w and column permutations of the matrix. In this talk\, I will explain the
game-based lower-bound methods and show how they can be used for deriving
further lower bounds\, varying symmetry groups and other matrix polynomia
ls\, such as the determinant.\n\n\nJoint work with Gregory Wilsenach.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alex Scott (University of Oxford)
DTSTART:20210415T160000Z
DTEND:20210415T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/34
DESCRIPTION:Title: Combinatorics in the exterior algebra and the Two Famili
es Theorem\nby Alex Scott (University of Oxford) as part of Moscow Big
Seminar of CombiGeo Lab\n\n\nAbstract\nThe Two Families Theorem of Bollob
as says the following: Let $(A_i\,B_i)$ be a sequence of pairs of sets suc
h that the $A_i$ have size $a$\, the $B_i$ have size $b$\, and $A_i$ and $
B_j$ intersect if and only if $i$ and $j$ are distinct. Then the sequence
has length at most $(a+b\\choose a)$.\n\nThis beautiful result has many ap
plications and has been generalized in two distinct ways. The first (which
follows from the original result of Bollobas) allows the sets to have dif
ferent sizes\, and replaces the cardinality constraint with a weighted sum
. The second uses an elegant exterior algebra argument due to Lovasz and a
llows the intersection condition to be replaced by a skew intersection con
dition. However\, there are no previous results that have versions of both
conditions.\n\nIn this talk\, we will explain and extend the exterior alg
ebra approach. We investigate the combinatorial structure of subspaces of
the exterior algebra of a finite-dimensional real vector space\, working i
n parallel with the extremal combinatorics of hypergraphs. As an applicati
on\, 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\nThi
s is joint work with Elizabeth Wilmer (Oberlin).\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Liana Yepremyan (University of Oxford)
DTSTART:20210422T160000Z
DTEND:20210422T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/35
DESCRIPTION:Title: Size-Ramsey numbers of powers of hypergraph trees and lo
ng subdivisions\nby Liana Yepremyan (University of Oxford) as part of
Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nThe $s$-colour size-Rams
ey number of a hypergraph $H$ is the minimum number of edges in a hypergra
ph $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$-uniform tight path on $n$ vertices is linear in $n$\, for every fixed
$r\, s\, t$\, thus answering a question of Dudek\, La Fleur\, Mubayi\, an
d R\\"odl (2017).\nIn fact\, we prove a stronger result that allows us to
deduce that powers of bounded degree hypergraph trees and of `long subdivi
sions' of bounded degree hypergraphs have size-Ramsey numbers that are lin
ear in the number of vertices. This extends recent results about the linea
rity of size-Ramsey numbers of powers of bounded degree trees and of long
subdivisions of bounded degree graphs.\n \n\nThis is joint work with Shoha
m Letzter and Alexey Pokrovskiy.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Avi Wigderson (IAS\, Princeton)
DTSTART:20210429T160000Z
DTEND:20210429T173000Z
DTSTAMP:20260404T094428Z
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 t
o summarize the status and goals of a broad research project. The main mes
sages of this project are summarized below\; I plan to describe\, through
examples\, many of the concepts they refer to\, and the evolution of ideas
leading to them. No special background is assumed. \n\n\n(1) (1) We exte
nd some basic algorithms of convex optimization from Euclidean space to th
e far more general setting of Riemannian manifolds\, capturing the symmetr
ies of non-commutative group actions. The main tools for analyzing these a
lgorithms combine central results from invariant and representation theory
.\n\n\n\n(2) One main motivation for studying these problems and algorith
ms comes from algebraic complexity theory\, especially attempts to separat
e Valiant’s algebraic analogs of the P and NP. Symmetries and group acti
ons play a key role in these attempts. \n\n\n(3) The new algorithms give
exponential (or better) improvements in run-time for solving algorithmic m
any specific problems across CS\, Math and Physics. In particular\, in alg
ebra (testing rational identities in non-commutative variables)\, in analy
sis (testing the feasibility and tightness of Brascamp-Lieb inequalities)\
, in quantum information theory (to the quantum marginals problem)\, optim
ization (testing membership in “moment polytopes”)\, and others. This
work exposes old and new connections between these diverse areas.\n\n\nBas
ed on many joint works in the past 5 years\, with Zeyuan Allen-Zhu\, Peter
Burgisser\, Cole Franks\, Ankit Garg\, Leonid Gurvits\, Pavel Hrubes\, Yu
anzhi Li\, Visu Makam\, Rafael Oliveira and Michael Walter.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alex Cohen (Yale University)
DTSTART:20210506T160000Z
DTEND:20210506T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/37
DESCRIPTION:Title: Equivalence of 3-tensor ranks\nby Alex Cohen (Yale U
niversity) 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 introduce
d by Tao in the context of the cap-set problem)\, the analytic rank (a Fou
rier-theoretic notion introduced by Gowers and Wolf)\, and the geometric r
ank (a recently introduced algebro-geometric notion) are all equivalent up
to an absolute constant. The proof uses tools from algebraic geometry to
argue about tangent spaces to certain determinantal varieties correspondin
g to the tensor. Our result settles open questions of Haramaty and Shpilka
[STOC 2010]\, and of Lovett [Discrete Anal.\, 2019] for 3-tensors.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Gaifullin (Skoltech\, Steklov Mathematical Institute of
RAS)
DTSTART:20210520T160000Z
DTEND:20210520T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/38
DESCRIPTION:Title: Flexible polyhedra: Constructions\, Volume\, Scissors Co
ngruence\nby Alexander Gaifullin (Skoltech\, Steklov Mathematical Inst
itute of RAS) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\
nFlexible polyhedra are polyhedral surfaces with rigid faces and hinges at
edges that admit non-trivial deformations\, that is\, deformations not in
duced by ambient isometries of the space. Main steps in theory of flexible
polyhedra are: Bricard’s construction of self-intersecting flexible oct
ahedra (1897)\, Connelly’s construction of flexors\, i.e.\, non-self-int
ersecting flexible polyhedra (1977)\, and Sabitov’s proof of the Bellows
conjecture claiming that the volume of any flexible polyhedron remains co
nstant during the flexion (1996). In my talk I will give a survey of these
classical results and ideas behind them\, as well as of several more rece
nt results by the speaker\, including the proof of Strong Bellows conjectu
re claiming that any flexible polyhedron in Euclidean three-space remains
scissors congruent to itself during the flexion.\n\n\nJoint work with Leon
id Ignashchenko\, 2017.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexey Pokrovskiy (University College London)
DTSTART:20211028T160000Z
DTEND:20211028T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/39
DESCRIPTION:Title: Rainbow matchings in coloured multigraphs\nby Alexey
Pokrovskiy (University College London) as part of Moscow Big Seminar of C
ombiGeo Lab\n\n\nAbstract\nThis talk will be about taking a coloured multi
graph and finding a rainbow matching using every colour. There's a variety
of conjectures that guarantee a matching like this in various classes of
multigraphs (eg the Aharoni-Berger Conjecture). In the talk\, I'll discuss
an easy technique to prove asymptotic versions of conjectures in this are
a. \n\n\nThis is joint work with David Munhá Correia and Benny Sudakov.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Kwan (IST Austria)
DTSTART:20211104T160000Z
DTEND:20211104T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/40
DESCRIPTION:Title: Friendly bisections of random graphs\nby Matthew Kwa
n (IST Austria) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstrac
t\nResolving 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 i
n which almost all vertices have more neighbours on their own side than ac
ross. Our proof involves some new techniques for \nstudying processes driv
en by degree information in random graphs\, which may be of general intere
st.\n\n\nThis is joint work with Asaf Ferber\, Bhargav Narayanan\, Ashwin
Sah and \nMehtaab Sawhney\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pablo Soberón (Baruch College\, CUNY)
DTSTART:20211111T160000Z
DTEND:20211111T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/41
DESCRIPTION:Title: Mass partitions\, transversals\, and Stiefel manifolds\nby Pablo Soberón (Baruch College\, CUNY) as part of Moscow Big Semina
r of CombiGeo Lab\n\n\nAbstract\nWe study mass partition problems related
to geometric transversals. In this talk\, we focus on two problems. In t
he first\, given a measure in R^d\, we seek to split R^d into few convex s
ets of equal measure so that every hyperplane misses the interior of many
regions. In the second\, we extend recent ham sandwich results on Grassma
nnians to impose geometric constraints on the dividing subspaces. The top
ological 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 are joint work with Ilani Axelrod-Freed and Michael Manta.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrey Kupavskii (CNRS\, France\; MIPT\, Russia)
DTSTART:20211125T160000Z
DTEND:20211125T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/42
DESCRIPTION:Title: Random restrictions and forbidden intersections\nby
Andrey Kupavskii (CNRS\, France\; MIPT\, Russia) as part of Moscow Big Sem
inar of CombiGeo Lab\n\n\nAbstract\nRandom restrictions is a powerful tool
that played a central role in the breakthrough result by Alweiss et al. o
n the famous Erdos-Rado sunflower conjecture. In this talk\, I will descri
be a new approach to getting a junta-type approximation for families of se
ts based on random restrictions. Such approximations have several exciting
consequences\, and I will present a couple of them. The first one is an u
pper bound on the size of regular k-uniform intersecting families similar
to the one obtained by Ellis\, Kalai and Narayanan for intersecting famili
es under a much stronger restriction of being transitive. The second one i
s significant progress on the t-intersection (and the Erdos-Sos forbidden
one intersection) problem for permutations. Improving and simplifying prev
ious results\, we show that the largest family of permutations [n] -> [n]
avoiding pairs of permutations with intersection exactly t-1\, has size at
most (n-t)!\, for t polynomial in n. Previously\, this was only known fo
r fixed t.\n \n\nJoint work with Dmitriy Zakharov.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pawel Pralat (Ryerson University)
DTSTART:20211202T160000Z
DTEND:20211202T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/43
DESCRIPTION:Title: Semi-random process\nby Pawel Pralat (Ryerson Univer
sity) as part of Moscow Big Seminar of CombiGeo Lab\n\n\nAbstract\nThe sem
i-random graph process is a single-player game that begins with an empty g
raph on n vertices. In each round\, a vertex u is presented to the player
independently and uniformly at random. The player then adaptively selects
a vertex v and adds the edge uv to the graph. For a fixed monotone graph p
roperty\, the objective of the player is to force the graph to satisfy thi
s property with high probability in as few rounds as possible.\n\nDuring t
he talk\, we will focus on the following problems: a) perfect matchings\,
b) Hamilton cycles\, c) constructing a subgraph isomorphic to an arbitrary
fixed graph G. We will also consider a natural generalization of the proc
ess to s-uniform hypergraphs.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vishesh Jain (Stanford University)
DTSTART:20211209T160000Z
DTEND:20211209T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/44
DESCRIPTION:Title: Singularity of discrete random matrices\nby Vishesh
Jain (Stanford University) as part of Moscow Big Seminar of CombiGeo Lab\n
\n\nAbstract\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 conjecture
d that the dominant reason for the singularity of $M_n$ is the event that
a row or column of $M_n$ is zero\, or that two rows or columns of $M_n$ co
incide (up to a sign).\n\n I will discuss joint work with Ashwin Sah (MIT)
and Mehtaab Sawhney (MIT)\, towards the resolution of this conjecture.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dmitrii Zhelezov (RICAM\, Linz\, Austria)
DTSTART:20211216T160000Z
DTEND:20211216T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/45
DESCRIPTION:Title: Sets inducing large additive doubling\nby Dmitrii Zh
elezov (RICAM\, Linz\, Austria) as part of Moscow Big Seminar of CombiGeo
Lab\n\n\nAbstract\nRephrasing the celebrated Freiman lemma in additive com
binatorics\, one can show that a finite set in Z^d containing a K-dimensio
nal simplex has additive doubling at least ~K. We will discuss a novel fra
mework for studying how such induced doubling can be inherited from a more
general class of multi-dimensional subsets. It turns out that subsets of
so-called quasi-cubes induce large doubling no matter the dimension of the
ambient set. Time permitting\, we will discuss how it allows to deduce a
structural theorem for sets with polynomially large additive doubling and
an application to the ”few products\, many sums” problem of Bourgain a
nd Chang.\n\nThis is joint work with I.Ruzsa\, D. Matlosci\, G. Shakan and
D. Palvölgyi\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrew Suk (University of California\, San Diego)
DTSTART:20220210T160000Z
DTEND:20220210T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/46
DESCRIPTION:Title: Hypergraph Ramsey numbers and an old problem of Erdos an
d Hajnal\nby Andrew Suk (University of California\, San Diego) as part
of Moscow 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-tuples of {1\,2\,...\,N}\, there are s integers such that every k-tu
ple among them is red\, or there are n integers such that every k-tuple am
ong them is blue. In this talk\, I will discuss known upper and lower boun
ds for r_k(s\,n). I will also discuss another closely related function th
at was introduced by Erdos and Hajnal in 1972.\n
LOCATION:https://stable.researchseminars.org/talk/combgeostructures/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Irit Dinur (Weizmann institute of science)
DTSTART:20220217T160000Z
DTEND:20220217T173000Z
DTSTAMP:20260404T094428Z
UID:combgeostructures/47
DESCRIPTION:Title: Locally testable codes via expanders\nby Irit Dinur
(Weizmann institute of science) as part of Moscow Big Seminar of CombiGeo
Lab\n\n\nAbstract\nA locally testable code (LTC) is an error-correcting co
de that admits a very efficient membership test. The tester reads a consta
nt number of (randomly - but not necessarily uniformly - chosen) bits from
a given word and rejects words with probability proportional to their dis
tance from 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 be useful in practice: before attempting to decode a received word\,
one can save time by first quickly testing if it is close to the code. \n
\nAn outstanding open question has been whether there exist LTCs that are
"good" in the coding theory sense of having both constant relative distanc
e and rate\, and at the same time testable with a constant number of queri
es.\n\nIn this talk\, I will describe a construction of such codes based o
n 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\nJoint work with Shai Evra\, Ron Livne\, Alex Lubotzky\, and Shahar Moze
s.\n
LOCATION:https://stable.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:20260404T094428Z
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 sy
stem is a graph whose vertices\nare the sets\, two being connected by an e
dge if and only if they are disjoint.\nIt is known that the disjointness g
raph $G$ of any system of segments in\nthe plane is $\\chi$-bounded\, that
is\, its chromatic number $\\chi(G)$\nis upper bounded by a function of i
ts clique number $\\omega(G)$.\n\nWe show that this statement does not rem
ain true for systems of polygonal\nchains of length $2$. Moreover\, for po
lygonal chains of length\n$3$ the disjointness graph have arbitrarily larg
e 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://stable.researchseminars.org/talk/combgeostructures/48/
END:VEVENT
END:VCALENDAR