BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Manfred Scheucher (TU Berlin)
DTSTART;VALUE=DATE-TIME:20210121T150000Z
DTEND;VALUE=DATE-TIME:20210121T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/1
DESCRIPTION:Title: Usi
ng SAT Solvers in Combinatorics and Geometry\nby Manfred Scheucher (TU
Berlin) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\nAbstract
: TBA\n
LOCATION:https://researchseminars.org/talk/CJCS/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Man-Wai Cheung (Harvard University)
DTSTART;VALUE=DATE-TIME:20210128T150000Z
DTEND;VALUE=DATE-TIME:20210128T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/2
DESCRIPTION:Title: Com
pactifications of cluster varieties and convexity\nby Man-Wai Cheung (
Harvard University) as part of Copenhagen-Jerusalem Combinatorics Seminar\
n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CJCS/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bruno Benedetti (U Miami)
DTSTART;VALUE=DATE-TIME:20210204T150000Z
DTEND;VALUE=DATE-TIME:20210204T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/3
DESCRIPTION:Title: A d
-dimensional version of interval graphs\, of Hamiltonian paths\, and of b
inomial edge ideals\nby Bruno Benedetti (U Miami) as part of Copenhage
n-Jerusalem Combinatorics Seminar\n\n\nAbstract\nWe study the d-dimensiona
l generalization of three mutually-related\nnotions in graph theory: (unit
)-interval graphs\, Hamiltonian cycles\, and\nbinomial edge ideals.\n\nThi
s is joint work with Matteo Varbaro and Lisa Seccia (arXiv:2101.09243).\n
LOCATION:https://researchseminars.org/talk/CJCS/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sebastian Manecke (University of Frankfurt)
DTSTART;VALUE=DATE-TIME:20210211T150000Z
DTEND;VALUE=DATE-TIME:20210211T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/4
DESCRIPTION:Title: Ins
cribable fans\, zonotopes\, and reflection arrangements\nby Sebastian
Manecke (University of Frankfurt) as part of Copenhagen-Jerusalem Combinat
orics Seminar\n\n\nAbstract\nSteiner posed the question if any 3-dimension
al polytope had a\nrealization with vertices on a sphere. Steinitz constru
cted the first\ncounter example and Rivin gave a complete resolution. In\n
dimensions 4 and up\, universality theorems by Mnev/Richter-Gebert\nrender
the question for inscribable combinatorial types hopeless.\n\nHowever\, f
or a given complete fan N\, we can decide in polynomial time\nif there is
an inscribed polytope with normal fan N. Linear\nhyperplane arrangements c
an be realized as normal fans via zonotopes.\nIt turns out that inscribed
zonotopes are rare and in this talk I\nwill focus on the question of class
ifying the corresponding\narrangements. This relates to localizatons and r
estrictions of\nreflection arrangements and Grünbaum's quest for the clas
sification of \nsimplicial arrangements. The talk is based on joint work w
ith Raman\nSanyal.\n
LOCATION:https://researchseminars.org/talk/CJCS/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Martin Tancer (Charles University Prague)
DTSTART;VALUE=DATE-TIME:20210218T150000Z
DTEND;VALUE=DATE-TIME:20210218T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/5
DESCRIPTION:Title: The
unbearable hardness of unknotting\nby Martin Tancer (Charles Universi
ty Prague) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbst
ract\nDuring the talk\, I will sketch a proof that deciding if a diagram o
f the unknot can be untangled using at most k Riedemeister moves (where k
is part of the input) is NP-hard. (This is not the same as the unknot reco
gnition but it reveals some difficulties.) Similar ideas can be also used
for proving that several other similar invariants are NP-hard to recognize
on links.\n\nJoint work with A. de Mesmay\, Y. Rieck and E. Sedgwick.\n
LOCATION:https://researchseminars.org/talk/CJCS/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vasso Petrotou (University of Ioannina)
DTSTART;VALUE=DATE-TIME:20210225T150000Z
DTEND;VALUE=DATE-TIME:20210225T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/6
DESCRIPTION:Title: Tom
& Jerry triples\nby Vasso Petrotou (University of Ioannina) as part o
f Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nUnprojection i
s a theory due to Reid which constructs and analyses more complicated ring
s from simpler ones. The talk will be about a new format of unprojection w
hich we call Tom & Jerry triples. As an application we will construct two
families of codimension 6 Fano 3-folds in weighted projective space.\n\nWe
will also give a brief introduction to Macaulay2.\n
LOCATION:https://researchseminars.org/talk/CJCS/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Irene Parada (TU Eindhoven)
DTSTART;VALUE=DATE-TIME:20210311T150000Z
DTEND;VALUE=DATE-TIME:20210311T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/7
DESCRIPTION:Title: Ins
erting edges into simple drawings\nby Irene Parada (TU Eindhoven) as p
art of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nSimple dr
awings of graphs are those in which each pair of edges share at most one p
oint\, either a common endpoint or a proper crossing. Given a simple drawi
ng D of a graph G\, in this talk we consider the problem of inserting a gi
ven set of missing edges (edges of the complement of G) into D such that t
he result is again a simple drawing. We show that it is NP-complete to dec
ide whether one edge can be inserted into a simple drawing. On the positiv
e side\, we present a Fixed-Parameter Tractable (FPT) algorithm for this p
roblem parameterized by the number of crossings that the edge to be insert
ed can have. This algorithm is tight under the Exponential Time Hypothesis
. We also obtain an FPT algorithm for inserting a bounded number of edges
with a bounded number of crossings. In these FPT algorithms\, after workin
g in the drawing\, the problem boils down to finding an algorithm for a la
beled abstract graph. To obtain these FPT algorithms we use different tool
s including the sunflower lemma\, representative families for matroids\, a
nd Courcelle's theorem. These techniques\, useful in many parameterized al
gorithms\, will be briefly introduced during the talk.\n
LOCATION:https://researchseminars.org/talk/CJCS/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pilar Cano (Université Libre de Bruxelles)
DTSTART;VALUE=DATE-TIME:20210304T150000Z
DTEND;VALUE=DATE-TIME:20210304T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/8
DESCRIPTION:Title: Fli
ps in higher order Delaunay triangulations\nby Pilar Cano (Université
Libre de Bruxelles) as part of Copenhagen-Jerusalem Combinatorics Seminar
\n\n\nAbstract\nWe study the flip graph of higher order Delaunay triangula
tions. A triangulation of a set S of n points in the plane is order-k Dela
unay if for every triangle its circumcircle encloses at most k points of S
. The flip graph of S has one vertex for each possible triangulation of S\
, and an edge connecting two vertices when the two corresponding triangula
tions can be transformed into each other by a flip (i.e.\, exchanging the
diagonal of a convex quadrilateral by the other one). The flip graph is an
essential structure in the study of triangulations\, but until now it had
been barely studied for order-k Delaunay triangulations. In this work we
show that\, even though the order-k flip graph might be disconnected for k
≥ 3\, any order-k triangulation can be transformed into some other orde
r-k triangulation by at most k − 1 flips\, such that the intermediate tr
iangulations are of order 2k − 2\, in the following settings: (1) for an
y k ≥ 0 when S is in convex position\, and (2) for any k ≤ 5 and any p
oint set S. Our results imply that the flip distance between two order-k t
riangulations is O(kn)\, as well as an efficient enumeration algorithm.\n
LOCATION:https://researchseminars.org/talk/CJCS/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lukas Kühne (Max Planck Institute of Mathematics in the Sciences)
DTSTART;VALUE=DATE-TIME:20210318T151500Z
DTEND;VALUE=DATE-TIME:20210318T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/9
DESCRIPTION:Title: Inv
estigating Terao's freeness conjecture with computer algebra\nby Lukas
Kühne (Max Planck Institute of Mathematics in the Sciences) as part of C
openhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nMotivated by sing
ularity theory\, Hiroaki Terao introduced a module of logarithmic derivati
ons associated with a hyperplane arrangement. This talk is concerned with
Terao’s freeness conjecture which asserts that the freeness of this deri
vation module is determined by the underlying combinatorics of the arrange
ment.\n\nTo investigate this conjecture\, we have enumerated all matroids
of rank 3 with up to 14 hyperplanes whose characteristic polynomial splits
over the integers and saved it in a public database. Using the GAP packag
e ZariskiFrames we have computed the moduli space and the free locus of th
e derivation module of each of these matroids as a quasi-affine set. As th
e main result\, this yields a computational proof of Terao’s freeness co
njecture for rank 3 arrangements with up to 14 hyperplanes in arbitrary ch
aracteristic.\n\nIn this talk\, I will explain the background of this conj
ecture without assuming prior knowledge and demonstrate the database and h
ighlights of the computations.\n\nThis talk is based on joint work with Mo
hamed Barakat\, Reimer Behrends\, Christopher Jefferson\, and Martin Lerne
r.\n
LOCATION:https://researchseminars.org/talk/CJCS/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pablo Soberon (CUNY)
DTSTART;VALUE=DATE-TIME:20210325T150000Z
DTEND;VALUE=DATE-TIME:20210325T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/10
DESCRIPTION:Title: Tv
erberg's theorem beyond prime powers\nby Pablo Soberon (CUNY) as part
of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nTverberg-type
theory aims to establish sufficient conditions for a simplicial complex $
\\Sigma$ such that every continuous map $f:\\Sigma \\to \\mathbb{R}^d$ map
s $q$ points from pairwise disjoint faces to the same point in $\\mathbb{R
}^d$. Such results are plentiful for $q$ a prime power. However\, for $q
$ with at least two distinct prime divisors\, results that guarantee the e
xistence of $q$-fold points of coincidence are non-existent— aside from
immediate corollaries of the prime power case. Here we present a general
method that yields such results beyond the case of prime powers. Joint wo
rk with Florian Frick.\n
LOCATION:https://researchseminars.org/talk/CJCS/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Torsten Mütze (University of Warwick)
DTSTART;VALUE=DATE-TIME:20210506T140000Z
DTEND;VALUE=DATE-TIME:20210506T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/11
DESCRIPTION:Title: Co
mbinatorial generation via permutation languages\nby Torsten Mütze (U
niversity of Warwick) as part of Copenhagen-Jerusalem Combinatorics Semina
r\n\n\nAbstract\nIn this talk I present a general and versatile algorithmi
c framework for exhaustively generating a large variety of different combi
natorial objects\, based on encoding them as permutations\, which provides
a unified view on many known results and allows us to prove many new ones
. This talk gives an overview over three main applications of our framewor
k: (1) the generation of pattern-avoiding permutations\; (2) the generatio
n of various classes of rectangulations\; (3) the generation of lattice co
ngruences of the weak order on the symmetric group and of graph associahed
ra.\n\nThis talk is based on joint work with Liz Hartung\, Hung P. Hoang\,
and Aaron Williams (SODA 2020)\, and with Arturo Merino (SoCG 2021) and J
ean Cardinal.\n
LOCATION:https://researchseminars.org/talk/CJCS/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sarah Peluse (Princeton)
DTSTART;VALUE=DATE-TIME:20210408T140000Z
DTEND;VALUE=DATE-TIME:20210408T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/12
DESCRIPTION:Title: Mo
dular zeros in the character table of the symmetric group\nby Sarah Pe
luse (Princeton) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n
\nAbstract\nIn 2017\, Miller conjectured\, based on computational evidence
\, that for any fixed prime $p$ the density of entries in the character ta
ble of $S_n$ that are divisible by $p$ goes to $1$ as $n$ goes to infinity
. I’ll describe a proof of this conjecture\, which is joint work with K.
Soundararajan. I will also discuss the (still open) problem of determinin
g the asymptotic density of zeros in the character table of $S_n$\, where
it is not even clear from computational data what one should expect.\n
LOCATION:https://researchseminars.org/talk/CJCS/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefan Felsner (TU Berlin)
DTSTART;VALUE=DATE-TIME:20210422T140000Z
DTEND;VALUE=DATE-TIME:20210422T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/13
DESCRIPTION:Title: Co
mbinatorics of Pseudocircle Arrangements\nby Stefan Felsner (TU Berlin
) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nIn
this talk we survey results for pseudocircle arrangements. Along the way w
e present several open problems. Among others we plan to touch the followi
ng topics:\n * The taxonomy of classes of pseudocircle arrangements.\n * T
he facial structure with emphasis on triangles and digons.\n * Circulariza
bility.\n * Coloring problems for pseudocircle arrangements.\nThe talk inc
ludes work of Grünbaum\, Snoeyink\, Pinchasi\, Scheucher\, and others.\n
LOCATION:https://researchseminars.org/talk/CJCS/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sean Eberhard (University of Cambridge)
DTSTART;VALUE=DATE-TIME:20210513T140000Z
DTEND;VALUE=DATE-TIME:20210513T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/14
DESCRIPTION:by Sean Eberhard (University of Cambridge) as part of Copenhag
en-Jerusalem Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CJCS/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yufei Zhao (MIT)
DTSTART;VALUE=DATE-TIME:20210429T140000Z
DTEND;VALUE=DATE-TIME:20210429T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/15
DESCRIPTION:Title: Th
e geometry of transitive sets\, with applications to eigenbasis of Cayley
graphs\nby Yufei Zhao (MIT) as part of Copenhagen-Jerusalem Combinator
ics Seminar\n\n\nAbstract\nI will discuss some counterintuitive facts and
conjectures about the width of a finite transitive subset of a high dimens
ional sphere (here "transitive" means transitive under the orthogonal grou
p). We were motivated by the question of whether Cayley graphs always have
a bounded eigenbasis. I will explain this connection\, and mention severa
l open problems.\n\nBased on joint work with Ashwin Sah and Mehtaab Sawhne
y: https://arxiv.org/abs/2005.04502 and https://arxiv.org/abs/2101.11207\n
LOCATION:https://researchseminars.org/talk/CJCS/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marc Lackenby (University of Oxford)
DTSTART;VALUE=DATE-TIME:20210520T140000Z
DTEND;VALUE=DATE-TIME:20210520T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/16
DESCRIPTION:Title: Un
knot recognition in quasi-polynomial time\nby Marc Lackenby (Universit
y of Oxford) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAb
stract\nI will outline a new algorithm for unknot recognition that runs in
quasi-polynomial time. The input is a diagram of a knot with n crossings\
, and the running time is 2^{O((log n)^3)}. The algorithm uses a wide vari
ety of tools from 3-manifold theory\, including normal surfaces\, hierarch
ies and Heegaard splittings. In my talk\, I will explain this background t
heory\, as well as explain how it fits into the algorithm.\n
LOCATION:https://researchseminars.org/talk/CJCS/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Victor Batyrev (Universität Tübingen)
DTSTART;VALUE=DATE-TIME:20210603T141500Z
DTEND;VALUE=DATE-TIME:20210603T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/17
DESCRIPTION:Title: Co
mbinatorics of lattice polytopes and MMP\nby Victor Batyrev (Universit
ät Tübingen) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\n
Abstract\nThe Minimal Model Program (MMP) was born in 80-ties from attempt
s to extend classical results on the birational classification of algebra
ic surfaces to algebraic varieties of dimension >2. The problem of birat
ional classification of higher dimensional algebraic varieties is so dif
ficult that its complete solution is not even expected. However\, a signi
ficant progress in understanding this \nproblem can be achieved if one re
stricts attention to some special and simultaneously sufficiently rich cl
ass of algebraic varieties under consideration.\n\nThe talk suggests to lo
ok at the class of algebraic varieties that are birational to non-degenera
te hypersurfaces Z in an algebraic torus T. It turns out that this class
is sufficiently rich to illustrate \nmany important ideas of MMP using c
ombinatorial properties of the Newton polytope P of the defining equation
of Z. The purpose of the talk is to explain the interplay between the com
binatorics of lattice polytopes and MMP which benefits from studing its
“combinatorial shadows”.\n
LOCATION:https://researchseminars.org/talk/CJCS/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oswin Aichholzer (TU Graz)
DTSTART;VALUE=DATE-TIME:20210610T141500Z
DTEND;VALUE=DATE-TIME:20210610T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/18
DESCRIPTION:Title: Or
der Types\, Rotation Systems\, and Crossing Numbers of $K_n$\nby Oswin
Aichholzer (TU Graz) as part of Copenhagen-Jerusalem Combinatorics Semina
r\n\n\nAbstract\nIn the area of crossing numbers we ask for minimizing th
e number of edge intersections in a drawing of a graph.\nThere is a rich v
ariety of crossing number problems: Which graphs do we consider\, what exa
ctly is a drawing of a graph\, and how are intersections counted? \nIn thi
s talk we will concentrate on the crossing number of complete graphs embed
ded in the plane as either geometric\nor simple drawing. We will have a cl
oser look at two useful combinatorial concepts for these representations:
order types for the\ngeometric case\, and rotation systes for the topologi
cal case.\n
LOCATION:https://researchseminars.org/talk/CJCS/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Miloš Stojakovic (University of Novi Sad)
DTSTART;VALUE=DATE-TIME:20210624T141500Z
DTEND;VALUE=DATE-TIME:20210624T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/19
DESCRIPTION:Title: De
aling with bichromatic non-crossing matchings\nby Miloš Stojakovic (U
niversity of Novi Sad) as part of Copenhagen-Jerusalem Combinatorics Semin
ar\n\n\nAbstract\nGiven a set of n red and n blue points in the plane\, we
are interested in matching red points with blue points by straight line s
egments so that the segments do not cross. We develop a range of tools for
dealing with the non-crossing matchings of points in convex position. It
turns out that the points naturally partition into groups that we refer to
as orbits\, with a number of properties that prove useful for studying an
d efficiently processing the non-crossing matchings.\n\n\nBottleneck match
ing is such a matching that minimizes the length of the longest segment. I
llustrating the use of the developed tools\, we show how to solve the prob
lem of finding bottleneck matchings of points in convex position faster th
an before.\n\nJoint work with Marko Savić.\n
LOCATION:https://researchseminars.org/talk/CJCS/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chaya Keller (Ariel University)
DTSTART;VALUE=DATE-TIME:20210527T140000Z
DTEND;VALUE=DATE-TIME:20210527T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/20
DESCRIPTION:Title: On
multicolor Ramsey numbers and subset-coloring of hypergraphs\nby Chay
a Keller (Ariel University) as part of Copenhagen-Jerusalem Combinatorics
Seminar\n\n\nAbstract\nThe multicolor hypergraph Ramsey number R_k(s\,r) i
s the minimal n\, such that in any k-coloring of all r-element subsets of
[n]\, there is a subset of size s\, all whose r-subsets are monochromatic.
We present a new "stepping-up lemma" for R_k(s\,r): If R_k(s\,r)>n\, the
n R_{k+3}(s+1\,r+1)>2^n. Using the lemma\, we improve some known lower bou
nds on multicolor hypergraph Ramsey numbers.\nFurthermore\, given a hyperg
raph H=(V\,E)\, we consider the Ramsey-like problem of coloring all r-subs
ets of V such that no hyperedge of size >r is monochromatic. We provide up
per and lower bounds on the number of colors necessary in terms of the chr
omatic number \\chi(H). In particular\, we show that this number is O(log^
{(r-1)} (r \\chi(H)) + r)\, where log^{(m)} denotes m-fold logarithm.\n\nJ
oint work with Bruno Jartoux\, Shakhar Smorodinsky\, and Yelena Yuditsky.\
n
LOCATION:https://researchseminars.org/talk/CJCS/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Linda Kleist (TU Braunschweig)
DTSTART;VALUE=DATE-TIME:20210617T141500Z
DTEND;VALUE=DATE-TIME:20210617T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/21
DESCRIPTION:Title: On
a Problem from Outer Space: Minimum Scan Covers\nby Linda Kleist (TU
Braunschweig) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nA
bstract\nIn this talk\, we investigate a natural geometric optimization pr
oblem motivated by questions in the context of satellite communication and
astrophysics. Given a graph embedded in Euclidean space\, the *Minimum S
can Cover Problem* (MSC) asks for a schedule of minimum makespan that *sca
ns* all edges. In order to scan an edge\, the incident vertices rotate at
their positions such that they face each other. Thereby\, rotations take t
ime proportional to the angular change. \n \nOur work reveals close conne
ctions to both the graph coloring problem and the minimum cut cover proble
m. In particular\, we show that the minimum scan time for instances in 1D
and 2D lies in Θ(log χ(G))\, while it is not upper bounded by χ(G) in 3
D. Unless P = NP\, these insights imply that no constant-factor approximat
ion exists even in 1D. Going to higher dimensions\, we discuss hardness an
d approximation results for special graph classes. The talk is based on jo
int work with Sándor Fekete and Dominik Krupke.\n
LOCATION:https://researchseminars.org/talk/CJCS/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Kwan (Stanford University)
DTSTART;VALUE=DATE-TIME:20210701T141500Z
DTEND;VALUE=DATE-TIME:20210701T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/22
DESCRIPTION:Title: Fr
iendly bisections of random graphs\nby Matthew Kwan (Stanford Universi
ty) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nR
esolving a conjecture of Füredi\, we prove that almost every n-vertex gra
ph admits a partition of its vertex set into two parts of equal size in wh
ich almost all vertices have more neighbours on their own side than across
. Our proof involves some new techniques for studying processes driven by
degree information in random graphs\, which may be of general interest. Th
is is joint work with Asaf Ferber\, Bhargav Narayanan\, Ashwin Sah and Meh
taab Sawhney.\n
LOCATION:https://researchseminars.org/talk/CJCS/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Natan Rubin (Ben-Gurion University)
DTSTART;VALUE=DATE-TIME:20210708T141500Z
DTEND;VALUE=DATE-TIME:20210708T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/23
DESCRIPTION:Title: St
ronger bounds for weak epsilon-nets in higher dimensions\nby Natan Rub
in (Ben-Gurion University) as part of Copenhagen-Jerusalem Combinatorics S
eminar\n\n\nAbstract\nGiven a finite point set $P$ in $R^d$\, and $\\varep
silon>0$ we say that a point set $N$ in $R^d$ is a weak $\\varepsilon$-ne
t if it pierces every convex set $K$ with $|K\\cap P|\\geq \\varepsilon |P
|$.\n \nLet $d\\geq 3$. We show that for any finite point set in $R^d$\, a
nd any $\\varepsilon>0$\, there exists a weak $\\varepsilon$-net of cardin
ality $O(1/\\varepsilon^{d-1/2+\\delta})$\, where $\\delta>0$ is an arbitr
ary small constant. \n\n\nThis is the first improvement of the bound of $O
^*(1/\\varepsilon^d)$ that was obtained in 1993 by Chazelle\, Edelsbrunner
\, Grigni\, Guibas\, Sharir\, and Welzl for general point sets in dimensio
n $d\\geq 3$.\n
LOCATION:https://researchseminars.org/talk/CJCS/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hunter Spink (Stanford University)
DTSTART;VALUE=DATE-TIME:20210715T141500Z
DTEND;VALUE=DATE-TIME:20210715T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/24
DESCRIPTION:Title: Ge
ometric and o-minimal Littlewood-Offord problems\nby Hunter Spink (Sta
nford University) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\
n\nAbstract\n(Joint with Jacob Fox and Matthew Kwan\, no o-minimal backgro
und required!) The classical Erdős-Littlewood-Offord theorem says that fo
r any n nonzero vectors in $\\mathbb{R}^d$\, a random signed sum concentra
tes on any point with probability at most $O(n^{-1/2})$. Combining tools f
rom probability theory\, additive combinatorics\, and o-minimality\, we ob
tain an anti-concentration probability of $n^{-1/2+o(1)}$ for any o-minima
l set $S$ in $\\mathbb{R}^d$ (such as a hypersurface defined by a polynomi
al in $x_1\,...\,x_n\,e^{x_1}\,...\,e^{x_n}$\, or a restricted analytic fu
nction) not containing a line segment. We do this by showing such o-minima
l sets have no higher-order additive structure\, complementing work by Pil
a on lower-order additive structure developed to count rational and algebr
aic points of bounded height.\n
LOCATION:https://researchseminars.org/talk/CJCS/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shoham Letzter (University College London)
DTSTART;VALUE=DATE-TIME:20210902T141500Z
DTEND;VALUE=DATE-TIME:20210902T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/25
DESCRIPTION:Title: Ti
ght cycles in hypergraphs\nby Shoham Letzter (University College Londo
n) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nHo
w many edges can an r-uniform hypergraph on n vertices with no tight cycle
s have? We determine the correct answer to this question up to a polylogar
ithmic factor\, improving on a recent result by Sudakov and Tomon.\n
LOCATION:https://researchseminars.org/talk/CJCS/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexandra Wesolek (Simon Fraser University)
DTSTART;VALUE=DATE-TIME:20210909T141500Z
DTEND;VALUE=DATE-TIME:20210909T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/26
DESCRIPTION:Title: Gr
aph Drawings and Graph Limits\nby Alexandra Wesolek (Simon Fraser Univ
ersity) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstrac
t\nIn this talk we will explain a setup which shows that the theory of gra
ph limits introduced by Lovász et al. can be applied to intersection grap
hs of graph drawings. In intersection graphs\, vertices correspond to edge
s of the drawing\, with two vertices being connected in the intersection g
raph if the corresponding edges cross. We consider models of random\, geod
esic drawings on the unit sphere for which the intersection graphs form a
convergent series (for n going to infinity). This talk is based on joint w
ork with Marthe Bonamy and Bojan Mohar.\n
LOCATION:https://researchseminars.org/talk/CJCS/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Georgios Petridis (University of Georgia)
DTSTART;VALUE=DATE-TIME:20210923T141500Z
DTEND;VALUE=DATE-TIME:20210923T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/28
DESCRIPTION:Title: Th
e q-analogue of almost orthogonal sets\nby Georgios Petridis (Universi
ty of Georgia) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\n
Abstract\nAn almost orthogonal set in $\\mathbb{R}^d$ is a collection of v
ectors with the property that among any three distinct elements there is a
n orthogonal pair. The maximum size of such sets was determined by Rosenfe
ld\, who verified a belief of Erdos. The same question was studied by Ahma
di and Mohammadian in $\\mathbb{F}_q^d$. We will present a proof of a conj
ecture of Ahmadi and Mohammadian and also see how it implies an “almost
” analogue of a theorem of Berlekamp on eventowns. Joint work with Ali M
ohammadi.\n
LOCATION:https://researchseminars.org/talk/CJCS/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Thang Pham (Vietnam National University)
DTSTART;VALUE=DATE-TIME:20211007T141500Z
DTEND;VALUE=DATE-TIME:20211007T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/29
DESCRIPTION:Title: Po
int-sphere incidence bounds in finite spaces\nby Thang Pham (Vietnam N
ational University) as part of Copenhagen-Jerusalem Combinatorics Seminar\
n\n\nAbstract\nIn this talk\, I present an approach to study the point-sph
ere incidence problem in the vector spaces over finite fields by using res
ults from restriction theory. This is joint work with Doowon Koh and Sujin
Lee.\n
LOCATION:https://researchseminars.org/talk/CJCS/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xavier Goaoc (École des Mines de Nancy)
DTSTART;VALUE=DATE-TIME:20211104T151500Z
DTEND;VALUE=DATE-TIME:20211104T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/30
DESCRIPTION:Title: Co
ncentration in order types of random point sets\nby Xavier Goaoc (Éco
le des Mines de Nancy) as part of Copenhagen-Jerusalem Combinatorics Semin
ar\n\n\nAbstract\nThe order type of a planar point set is a combinatorial
structure that \nencodes many of its geometric properties\, for instance t
he face lattice \nof its convex hull or the triangulations it supports. In
a sense\, it is \na generalization of the permutation associated to a seq
uence of real \nnumbers.\n\nThis talk will start with a quick introduction
to order types. Then\, \nI'll discuss a concentration phenomenon that ari
ses when taking order \ntypes of various natural models of random point se
ts\, and that makes \norder types hard to sample efficiently. This will gi
ve us an occasion to \n revisit Klein's celebrated proof of the classific
ation of finite \nsubgroups of SO(3).\n\nThis is joint work with Emo Welzl
(https://arxiv.org/abs/2003.08456).\n
LOCATION:https://researchseminars.org/talk/CJCS/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michael Simkin (Harvard University)
DTSTART;VALUE=DATE-TIME:20210930T141500Z
DTEND;VALUE=DATE-TIME:20210930T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/31
DESCRIPTION:Title: Th
e number of $n$-queens configurations\nby Michael Simkin (Harvard Univ
ersity) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstrac
t\nThe $n$-queens problem is to determine $\\mathcal{Q}(n)$\, the number o
f ways to place $n$ mutually non-threatening queens on an $n \\times n$ bo
ard. We show that there exists a constant $\\alpha = 1.942 \\pm 3 \\times
10^{-3}$ such that $\\mathcal{Q}(n) = ((1 \\pm o(1))ne^{-\\alpha})^n$. The
constant $\\alpha$ is characterized as the solution to a convex optimizat
ion problem in $\\mathcal{P}([-1/2\,1/2]^2)$\, the space of Borel probabil
ity measures on the square.\n\nThe chief innovation is the introduction of
limit objects for $n$-queens configurations\, which we call \\textit{quee
nons}. These are a convex set in $\\mathcal{P}([-1/2\,1/2]^2)$. We define
an entropy function that counts the number of $n$-queens configurations th
at approximate a given queenon. The upper bound uses the entropy method. F
or the lower bound we describe a randomized algorithm that constructs a co
nfiguration near a prespecified queenon and whose entropy matches that fou
nd in the upper bound. The enumeration of $n$-queens configurations is the
n obtained by maximizing the (concave) entropy function in the space of qu
eenons.\n\nBased on arXiv:2107.13460\n
LOCATION:https://researchseminars.org/talk/CJCS/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Arnau Padrol (Sorbonne Université)
DTSTART;VALUE=DATE-TIME:20211014T141500Z
DTEND;VALUE=DATE-TIME:20211014T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/32
DESCRIPTION:Title: Th
e convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flor
es Theorem\nby Arnau Padrol (Sorbonne Université) as part of Copenhag
en-Jerusalem Combinatorics Seminar\n\n\nAbstract\nI will present joint wor
k with Leonardo Martínez-Sandoval on the \nhypersimplicial generalization
of the linear van Kampen-Flores theorem: \nfor each n\, k and i we determ
ine onto which dimensions can the \n(n\,k)-hypersimplex be linearly projec
ted while preserving its \ni-skeleton. This is motivated by the study of t
he convex dimensions of \nhypergraphs. The convex dimension of a k-uniform
hypergraph is the \nsmallest dimension d for which there is an injective
mapping of its \nvertices into R^d such that the set of k-barycenters of a
ll hyperedges \nis in convex position. Our results completely determine th
e convex \ndimension of complete k-uniform hypergraphs. This settles an op
en \nquestion by Halman\, Onn and Rothblum\, who solved the problem for \n
complete graphs. We also provide lower and upper bounds for the extremal \
nproblem of estimating the maximal number of hyperedges of k-uniform \nhyp
ergraphs on n vertices with convex dimension d.\n
LOCATION:https://researchseminars.org/talk/CJCS/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christopher Eur (Harvard University)
DTSTART;VALUE=DATE-TIME:20211021T141500Z
DTEND;VALUE=DATE-TIME:20211021T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/33
DESCRIPTION:Title: Ta
utological classes of matroids\nby Christopher Eur (Harvard University
) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nWe
introduce a new way of geometrically studying matroids that unifies\, reco
vers\, and extends several recent developments in the interaction between
matroid theory and algebraic geometry. Joint work with Andrew Berget\, Hu
nter Spink\, and Dennis Tseng.\n
LOCATION:https://researchseminars.org/talk/CJCS/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean-Philippe Labbé (École de Technologie Supérieure Montreal)
DTSTART;VALUE=DATE-TIME:20211028T141500Z
DTEND;VALUE=DATE-TIME:20211028T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/34
DESCRIPTION:Title: Li
neup polytopes and applications in quantum physics\nby Jean-Philippe L
abbé (École de Technologie Supérieure Montreal) as part of Copenhagen-J
erusalem Combinatorics Seminar\n\n\nAbstract\nThe set of all possible spec
tra of 1-reduced density operators for systems of N\nparticles on a d-dime
nsional Hilbert space is a polytope called hypersimplex. If\nthe spectrum
of the original density operators is fixed\, the set of spectra (ordered\n
decreasingly) of 1-reduced density operators is also a polytope. A theoret
ical\ndescription of this polytope using inequalities was provided by Klya
chko in the\nearly 2000’s.\nAdapting and enhancing tools from discrete g
eometry and combinatorics (symmetric\npolytopes\, sweep polytopes\, and th
e Gale order)\, we obtained such necessary\ninequalities explicitly\, that
are furthermore valid for arbitrarily large N and d.\nThese may therefore
be interpreted as generalizations of Pauli's exclusion principle\nfor fer
mions. In particular\, this approach leads to a new class of polytopes cal
led\nlineup polytopes.\n\nThis is joint work with physicists Julia Liebert
\, Christian Schilling and mathematicians\nEva Philippe\, Federico Castill
o and Arnau Padrol.\n
LOCATION:https://researchseminars.org/talk/CJCS/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mats Boij (KTH)
DTSTART;VALUE=DATE-TIME:20211111T151500Z
DTEND;VALUE=DATE-TIME:20211111T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/35
DESCRIPTION:Title: Le
fschetz Properties\nby Mats Boij (KTH) as part of Copenhagen-Jerusalem
Combinatorics Seminar\n\n\nAbstract\nLefschetz properties have been in fo
cus in combinatorics and commutative algebra since Stanley’s proof of th
e g-Theorem for simplicial polytopes. I will give some background and then
I’ll present two projects that I have been working on recently. The fir
st is related to symmetric polynomial and is joint work with Migliore\, Na
gel and Miró-Roig. The second is related to powers of general linear form
s and is joint work with Lundqvist.\n
LOCATION:https://researchseminars.org/talk/CJCS/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Henry Adams (Colorado State University)
DTSTART;VALUE=DATE-TIME:20211202T151500Z
DTEND;VALUE=DATE-TIME:20211202T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/37
DESCRIPTION:Title: Bo
unding Gromov-Hausdorff distances with Borsuk-Ulam theorems and Vietoris-R
ips complexes\nby Henry Adams (Colorado State University) as part of C
openhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nThe Gromov-Hausdo
rff distance between two metric spaces is an important tool in geometry\,
but it is difficult to compute. For example\, the Gromov-Hausdorff distanc
e between unit spheres of different dimensions is unknown in nearly all ca
ses. I will introduce recent work by Lim\, Mémoli\, and Okutan that lower
bounds the Gromov-Hausdorff distance between spheres using Borsuk-Ulam th
eorems. We improve these lower bounds by connecting this story to Vietoris
-Rips complexes\, providing new generalizations of Borsuk-Ulam.\n
LOCATION:https://researchseminars.org/talk/CJCS/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Victor Reiner (Univerity of Minnesota)
DTSTART;VALUE=DATE-TIME:20211118T151500Z
DTEND;VALUE=DATE-TIME:20211118T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/39
DESCRIPTION:Title: To
pology of augmented Bergman complexes\nby Victor Reiner (Univerity of
Minnesota) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbst
ract\n(based on arxiv:2108.13394\; joint with REU students E. Bullock\, A.
Kelley\, K. Ren\, G. Shemy\, D. Shen\, B. Sun\, A. Tao\, Z. Zhang)\n\nThe
augmented Bergman complex of a matroid is a simplicial complex introduced
recently in work of Braden\, Huh\, Matherne\, Proudfoot and Wang. It may
be viewed as a hybrid of two well-studied pure shellable simplicial comple
xes associated to matroids: the independent set complex and the order comp
lex of the lattice of flats.\n\nAfter recalling the relevance of the augme
nted Bergman complex in the B-H-M-P-W work\, we show that it is shellable\
, via two different families of shelling orders. Both shellings determine
the homotopy type\, and comparing the two answers re-interprets a known co
nvolution formula counting bases of the matroid. One of the shellings lead
s to a surprisingly simple description for how symmetries of the matroid a
ct on the homology of the complex.\n
LOCATION:https://researchseminars.org/talk/CJCS/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jozsef Solymosi (University of British Columbia)
DTSTART;VALUE=DATE-TIME:20211216T151500Z
DTEND;VALUE=DATE-TIME:20211216T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/41
DESCRIPTION:Title: Ra
nk of matrices with entries from a multiplicative group\nby Jozsef Sol
ymosi (University of British Columbia) as part of Copenhagen-Jerusalem Com
binatorics Seminar\n\n\nAbstract\nWe establish lower bounds on the rank of
matrices in which all but the diagonal entries lie in a multiplicative gr
oup of small rank. Applying these bounds we show that the distance sets of
finite pointsets in ℝ^d generate high rank multiplicative groups and th
at multiplicative groups of small rank cannot contain large sumsets. (Join
t work with Noga Alon)\n
LOCATION:https://researchseminars.org/talk/CJCS/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Giorgis Petridis (University of Georgia)
DTSTART;VALUE=DATE-TIME:20211215T151500Z
DTEND;VALUE=DATE-TIME:20211215T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/42
DESCRIPTION:Title: Sm
all progress towards the Paley graph conjecture\nby Giorgis Petridis (
University of Georgia) as part of Copenhagen-Jerusalem Combinatorics Semin
ar\n\n\nAbstract\nThe question of determining the largest independent set
in a Paley graph (a special kind of Cayley graph) is connected to the clas
sical question of Vinogradov on determining the least quadratic non-residu
e modulo a given prime. This connection will be discussed and small progre
ss in the state-of-the-art will be presented.\n
LOCATION:https://researchseminars.org/talk/CJCS/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Igor Pak (UCLA)
DTSTART;VALUE=DATE-TIME:20211104T170000Z
DTEND;VALUE=DATE-TIME:20211104T190000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/43
DESCRIPTION:Title: Lo
g-concave poset inequalities\nby Igor Pak (UCLA) as part of Copenhagen
-Jerusalem Combinatorics Seminar\n\n\nAbstract\nIn the ocean of log-concav
e inequalities\, there are two islands that are especially difficult. Fir
st\, Mason's conjectures say that the number of forests in a graph with k
edges is log-concave. More generally\, the number of independent sets of
size k in a matroid is log-concave. Versions of these results were establ
ished just recently\, in a remarkable series of papers inspired by algebra
ic and geometric considerations. Second\, Stanley's inequality for the nu
mbers of linear extensions of a poset with value k at a given poset elemen
t\, is log-concave. This was originally conjectured by Chung\, Fishburn a
nd Graham\, and proved by Stanley in 1981 using the Alexandrov–Fenchel i
nequalities in convex geometry. In our recent paper\, we present a new fr
amework of combinatorial atlas which allows one to give elementary proofs
of both results\, and extend them in several directions. I will give an i
ntroduction to the area and then outline our approach. Joint work with Sw
ee Hong Chan.\n
LOCATION:https://researchseminars.org/talk/CJCS/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nina Kamcev (University of Zagreb)
DTSTART;VALUE=DATE-TIME:20211125T151500Z
DTEND;VALUE=DATE-TIME:20211125T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/44
DESCRIPTION:Title: Co
mmon systems of equations are rare\nby Nina Kamcev (University of Zagr
eb) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nS
everal classical results in Ramsey theory (including famous theorems of Sc
hur\, van der Waerden\, Rado) deal with finding monochromatic linear patte
rns in two-colourings of the integers. Our topic will be quantitative exte
nsions of such results.\n \nA linear system $L$ over $\\mathcal{F}_q$ is \
\emph{common} if the number of monochromatic solutions to $L=0$ in any two
-colouring of $\\mathcal{F}_q^n$ is asymptotically at least the expected n
umber of monochromatic solutions in a random two-colouring of $\\mathcal{F
}_q^n$. Motivated by existing results for specific systems (such as Schur
triples and arithmetic progressions)\, as well as extensive research on co
mmon and Sidorenko graphs\, the systematic study of common systems of line
ar equations was recently initiated by Saad and Wolf. Fox\, Pham and Zhao
characterised common linear equations. \n \nI will talk about recent prog
ress towards a classification of common systems of two or more linear equa
tions. In particular\, any system containing a four-term arithmetic progre
ssion is uncommon. This follows from a more general result which allows us
to deduce the uncommonness of a general system from certain properties of
one- or two-equation subsystems.\n \nJoint work with Anita Liebenau and N
atasha Morrison.\n
LOCATION:https://researchseminars.org/talk/CJCS/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matt Baker (Georgia Tech)
DTSTART;VALUE=DATE-TIME:20211209T150000Z
DTEND;VALUE=DATE-TIME:20211209T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/45
DESCRIPTION:Title: Th
e Foundation of a Matroid\nby Matt Baker (Georgia Tech) as part of Cop
enhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nMatroid theorists a
re interested in questions concerning representability of matroids over fi
elds. More generally\, one can ask about representability over partial fie
lds in the sense of Semple and Whittle. Pendavingh and van Zwam introduced
the universal partial field of a matroid\, which governs the representati
ons of over all partial fields. Unfortunately\, most matroids are not rep
resentable over any partial field\, and in this case\, the universal parti
al field is not defined.\n\nOliver Lorscheid and I have introduced a gener
alization of the universal partial field which we call the foundation of a
matroid\; it is always well-defined. The foundation is a type of algebrai
c object which we call a pasture\; pastures include both hyperfields and p
artial fields. As a particular application of this point of view\, I will
explain the classification of all possible foundations for matroids having
no minor isomorphic to U(2\,5) or U(3\,5). Among other things\, this prov
ides a short and conceptual proof of the 1997 theorem of Lee and Scobee wh
ich says that a matroid is both ternary and orientable if and only if it i
s dyadic.\n
LOCATION:https://researchseminars.org/talk/CJCS/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laura Escobar (Washington University in St. Louis)
DTSTART;VALUE=DATE-TIME:20220203T151500Z
DTEND;VALUE=DATE-TIME:20220203T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/46
DESCRIPTION:Title: Th
e harmonic polytope\nby Laura Escobar (Washington University in St. Lo
uis) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\n
This talk\, based on joint work with Federico Ardila\, is about the harmon
ic polytope\, which arose in Ardila\, Denham\, and Huh’s work on the Lag
rangian geometry of matroids. We show that the harmonic polytope is a (2n-
2)-dimensional polytope with (n!)^2(1+1/2+···+1/n) vertices and 3n-3 fa
cets. Lastly\, we use the Bernstein-Khovanskii-Kushnirenko Theorem to give
a formula for its volume.\n
LOCATION:https://researchseminars.org/talk/CJCS/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Adam Sheffer (City University of New York)
DTSTART;VALUE=DATE-TIME:20220310T151500Z
DTEND;VALUE=DATE-TIME:20220310T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/47
DESCRIPTION:Title: A
structural Szemerédi–Trotter theorem for cartesian products\nby Ada
m Sheffer (City University of New York) as part of Copenhagen-Jerusalem Co
mbinatorics Seminar\n\n\nAbstract\nThe Szemerédi–Trotter theorem can be
considered as the fundamental theorem of geometric incidences. This combi
natorial theorem has an unusually wide variety of applications\, and is us
ed in combinatorics\, theoretical computer science\, harmonic analysis\, n
umber theory\, model theory\, and more. Surprisingly\, hardly anything is
known about the structural question - characterizing the cases where the t
heorem is tight. We present such structural results for the case of cartes
ian products. This is a basic survey talk and does not require previous kn
owledge of the field.\n \nJoint work with Olivine Silier. Also\, a shamele
ss advertisement of the speaker's new book "Polynomial Methods and Inciden
ce Theory."\n
LOCATION:https://researchseminars.org/talk/CJCS/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Miloš Trujić (ETH Zürich)
DTSTART;VALUE=DATE-TIME:20220210T151500Z
DTEND;VALUE=DATE-TIME:20220210T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/48
DESCRIPTION:Title: Tw
o problems in (size-)Ramsey theory\nby Miloš Trujić (ETH Zürich) as
part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nIn 1978
\, Erdős\, Faudree\, Rousseau\, and Schelp introduced the study of the si
ze-Ramsey\nnumber of a graph H\, defined as a minimum positive integer m f
or which there exists a\ngraph G with m edges such that in every colouring
of its edges by two colours there is a\nmonochromatic copy of H. I will d
iscuss recent advances for two problems in this area when\nH is a large gr
aph of bounded maximum degree. This is joint work with David Conlon and \n
Rajko Nenadov.\n
LOCATION:https://researchseminars.org/talk/CJCS/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anschel Schaffer-Cohen (University of Pennsylvania)
DTSTART;VALUE=DATE-TIME:20220127T161500Z
DTEND;VALUE=DATE-TIME:20220127T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/49
DESCRIPTION:Title: Au
tomorphisms of the loop and arc graph of an infinite-type surface\nby
Anschel Schaffer-Cohen (University of Pennsylvania) as part of Copenhagen-
Jerusalem Combinatorics Seminar\n\n\nAbstract\nWe show that the extended b
ased mapping class group of an infinite-type surface is naturally isomorph
ic to the automorphism group of the loop graph of that surface. Additional
ly\, we show that the extended mapping class group stabilizing a finite se
t of punctures is isomorphic to the arc graph relative to that finite set
of punctures. This extends a known result for sufficiently complex finite-
type surfaces\, and provides a new angle from which to study the mapping c
lass groups of infinite-type surfaces.\n
LOCATION:https://researchseminars.org/talk/CJCS/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ana Chavez Caliz (Pennsylvania State University)
DTSTART;VALUE=DATE-TIME:20220106T161500Z
DTEND;VALUE=DATE-TIME:20220106T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/50
DESCRIPTION:Title: Pr
ojective self-dual polygons\nby Ana Chavez Caliz (Pennsylvania State U
niversity) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbst
ract\nIn his book "Arnold's Problems\," Vladimir Arnold shares a collectio
n of questions without answers formulated during seminars in Moscow and Pa
ris for over 40 years. One of these problems\, stated in 1994\, goes as fo
llows:\nFind all projective curves projectively equivalent to their duals.
The answer seems to be unknown even in RP^2.\n\nMotivated by this questio
n\, in their paper "Self-dual polygons and self-dual curves" from 2009\, D
. Fuchs and S. Tabachnikov explore a discrete version of Arnold's question
in 2-dimensions. If P is an n-gon with vertices A_1\, A_3\, ... A_{2n-1}\
, then its dual polygon P* has vertices B*_2\, B*_4\, ... B*_{2n}\, where
B*_i is the line connecting the points A_{i-1}\, A_{i+1}. Given an integer
m\, a polygon P is m-self-dual if there is a projective transformation f
such that f(A_i) = B_{i+m}. \n\nIn this talk\, I will discuss how we can g
eneralize Fuchs and Tabachnikov's work to polygons in higher dimensions. I
will include some conjectures which are supported by computational result
s.\n
LOCATION:https://researchseminars.org/talk/CJCS/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Arina Voorhaar (University of Geneva)
DTSTART;VALUE=DATE-TIME:20220106T151500Z
DTEND;VALUE=DATE-TIME:20220106T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/51
DESCRIPTION:Title: On
the Newton Polytope of the Morse Discriminant\nby Arina Voorhaar (Uni
versity of Geneva) as part of Copenhagen-Jerusalem Combinatorics Seminar\n
\n\nAbstract\nA famous classical result by Gelfand\, Kapranov and Zelevins
ky provides a combinatorial description of the vertices of the Newton poly
tope of the A-discriminant (the closure of the set of all non-smooth hyper
surfaces defined by polynomials with the given support A). Namely\, it giv
es a surjection from the set of all convex triangulations of the convex hu
ll of the set A with vertices in A (or\, equivalently\, the set of all pos
sible combinatorial types of smooth tropical hypersurfaces defined by trop
ical polynomials with support A) onto the set of vertices of this Newton p
olytope. In my talk\, I will discuss a similar problem for the Morse discr
iminant — the closure of the set of all polynomials with the given suppo
rt A which are non-Morse if viewed as polynomial maps. Namely\, for a 1-di
mensional support set A\, there is a surjection from the set of all possib
le combinatorial types of so-called Morse tropical polynomials onto the ve
rtices of the Newton polytope of the Morse discriminant.\n
LOCATION:https://researchseminars.org/talk/CJCS/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sophie Spirkl (University of Waterloo)
DTSTART;VALUE=DATE-TIME:20220113T151500Z
DTEND;VALUE=DATE-TIME:20220113T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/52
DESCRIPTION:Title: Ne
w results on polynomial $\\chi$-boundedness\nby Sophie Spirkl (Univers
ity of Waterloo) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n
\nAbstract\nThe number of colours required to colour a graph $G$ (the chro
matic number $\\chi(G)$) is at least its clique number\, that is\, the max
imum size of a set of pairwise adjacent vertices. A class of graphs is $\\
chi$-bounded if the converse is approximately true\, that is\, the chromat
ic number is at most some function of the clique number. In this talk\, we
are interested in when this function can be chosen as a polynomial. I wil
l discuss some recent results\, mostly concerning the case of forbidding a
single graph as an induced subgraph.\nJoint work with Maria Chudnovsky\,
Alex Scott and Paul Seymour.\n
LOCATION:https://researchseminars.org/talk/CJCS/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shubhangi Saraf (Rutgers University)
DTSTART;VALUE=DATE-TIME:20220120T151500Z
DTEND;VALUE=DATE-TIME:20220120T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/53
DESCRIPTION:Title: Fa
ctors of sparse polynomials: structural results and some algorithms\nb
y Shubhangi Saraf (Rutgers University) as part of Copenhagen-Jerusalem Com
binatorics Seminar\n\n\nAbstract\nAre factors of sparse polynomials sparse
? This is basic question\, and we are still quite far from understanding i
t in general. In this talk\, I will show that this is in some sense true f
or multivariate polynomials when the polynomial has each variable appearin
g only with bounded degree. Our sparsity bound uses techniques from convex
geometry\, such as the theory of Newton polytopes and an approximate vers
ion of the classical Caratheodory's Theorem. \nUsing our sparsity bound\,
we then show how to devise efficient deterministic factoring algorithms f
or sparse polynomials of bounded individual degree.\nThe talk is based on
joint work with Vishwas Bhargav and Ilya Volkovich.\n
LOCATION:https://researchseminars.org/talk/CJCS/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:William Gustafson (University of Kentucky)
DTSTART;VALUE=DATE-TIME:20220127T151500Z
DTEND;VALUE=DATE-TIME:20220127T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/54
DESCRIPTION:Title: La
ttice minors and Eulerian posets\nby William Gustafson (University of
Kentucky) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstr
act\nWe introduce a notion of deletion and contraction on lattices enriche
d with a generating set\, and from these operations a notion of minors. Wh
en considering the lattice of flats of a graph the lattice minors are in b
ijection with the simple minors of the graph when the vertices are labeled
and the edges are unlabeled. We show how this correspondence generalizes
to the setting of polymatroids. Then we introduce the minor poset of a giv
en generator enriched lattice and show these posets are Eulerian and PL sp
heres. Finally we discuss some inequalities between the cd-indices of mino
r posets.\n
LOCATION:https://researchseminars.org/talk/CJCS/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Clifton (Emory University)
DTSTART;VALUE=DATE-TIME:20220217T151500Z
DTEND;VALUE=DATE-TIME:20220217T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/55
DESCRIPTION:Title: Ra
msey Theory for Diffsequences\nby Alexander Clifton (Emory University)
as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nVan
der Waerden's theorem states that any coloring of $\\mathbb{N}$ with a fin
ite number of colors will contain arbitrarily long monochromatic arithmeti
c progressions. This motivates the definition of the van der Waerden numbe
r $W(r\,k)$ which is the smallest $n$ such that any $r$-coloring of $\\{1\
,2\,\\cdots\,n\\}$ guarantees the presence of a monochromatic arithmetic p
rogression of length $k$.\n\nIt is natural to ask what other arithmetic st
ructures exhibit van der Waerden-type results. One notion\, introduced by
Landman and Robertson\, is that of a $D$-diffsequence\, which is an increa
sing sequence $a_1 < a_2 <\\cdots< a_k$ in which the consecutive differenc
es $a_i-a_{i-1}$ all lie in some given set $D$. For each $D$ that exhibits
a van der Waerden-type result\, we let $\\Delta(D\,k\;r)$ represent the a
nalogue of the van der Waerden number $W(r\,k)$. One question of interest
is to determine the possible behaviors of $\\Delta$ as a function of $k$.
In this talk\, we will demonstrate that it is possible for $\\Delta(D\,k\;
r)$ to grow faster than polynomial in $k$. Time permitting\, we will also
discuss a class of $D$'s for which no van der Waerden-type result is possi
ble.\n
LOCATION:https://researchseminars.org/talk/CJCS/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marija Jelić Milutinović (University of Belgrade)
DTSTART;VALUE=DATE-TIME:20220224T151500Z
DTEND;VALUE=DATE-TIME:20220224T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/56
DESCRIPTION:Title: Ma
tching complexes of graphs\nby Marija Jelić Milutinović (University
of Belgrade) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAb
stract\nThe matching complex M(G) of a graph G is the simplicial complex w
ith the vertex set given by edges of G and faces given by subsets of pairw
ise disjoint edges\, i.e.\, matchings of G. There is a long history of the
study of matching complexes\, and there are many results on the topology
of the matching complexes of interesting classes of graphs. We will discus
s the reverse question: which simplicial complexes are matching complexes
of graphs? In this talk we will answer this question for the homology mani
folds\, with and without boundary. While in dimension 2 there are several
interesting manifolds\, in dimension three and higher the only matching co
mplexes are combinatorial spheres and combinatorial disks. Moreover\, the
graphs that produce manifold matching complexes are all constructed from t
he disjoint union of copies of a finite set of graphs. The talk is based o
n joint work with M. Bayer and B. Goeckner.\n
LOCATION:https://researchseminars.org/talk/CJCS/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lei Xue (University of Washington)
DTSTART;VALUE=DATE-TIME:20220127T171500Z
DTEND;VALUE=DATE-TIME:20220127T180000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/57
DESCRIPTION:Title: A
Proof of Grünbaum’s Lower Bound Conjecture for polytopes\, lattices\, a
nd strongly regular pseudomanifolds.\nby Lei Xue (University of Washin
gton) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\
nIn 1967\, Grünbaum conjectured that any $d$-dimensional polytope with $d
+ s \\leq 2d$ vertices has at least $\\phi_k (d + s\, d) = {d + 1 \\choos
e k + 1} + { d \\choose k + 1} - { d + 1 - s \\choose k + 1}$ $k$-faces. I
n the talk\, we will prove this conjecture and discuss equality cases. We
will then extend our results to lattices with diamond property (the inequa
lity part) and to strongly regular normal pseudomanifolds (the equality pa
rt). We will also talk about recent results on $d$-dimensional polytopes w
ith $2d + 1$ or $2d + 2$ vertices.\n
LOCATION:https://researchseminars.org/talk/CJCS/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Samuel Lundqvist (Stockholm University)
DTSTART;VALUE=DATE-TIME:20220317T151500Z
DTEND;VALUE=DATE-TIME:20220317T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/58
DESCRIPTION:Title: Th
e Fröberg conjecture and some questions on powers of general linear forms
\nby Samuel Lundqvist (Stockholm University) as part of Copenhagen-Jer
usalem Combinatorics Seminar\n\n\nAbstract\nThe longstanding Fröberg conj
ecture states that there are no non-trivial relations between general homo
geneous polynomials. But if we replace "general homogeneous polynomials" b
y ”powers of general linear forms” it turns out that in some cases the
re are in fact such non-trivial relations\, which may at first seem unnatu
ral. I will present some results and some combinatorial questions related
to these two classes of objects\, and will give brief connections to latti
ce paths\, the Exterior algebra\, the Lefschetz properties\, and fat point
schemes. No previous knowledge of the Fröberg conjecture is assumed.\n
LOCATION:https://researchseminars.org/talk/CJCS/58/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lorenzo Venturello (KTH Stockholm)
DTSTART;VALUE=DATE-TIME:20220331T141500Z
DTEND;VALUE=DATE-TIME:20220331T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/59
DESCRIPTION:Title: Go
renstein algebras from simplicial complexes\nby Lorenzo Venturello (KT
H Stockholm) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAb
stract\nGorenstein algebras form an intriguing class of objects which ofte
n show up in combinatorics and geometry. In this talk I will present a con
struction which associates to every pure simplicial complex a standard gra
ded Gorenstein algebra. We describe a presentation of this algebra as a po
lynomial ring modulo an ideal generated by monomials and pure binomials. W
hen the simplicial complex is flag\, i.e.\, it is the clique complex of it
s graph\, our main results establish equivalences between well studied pro
perties of the complex (being S_2\, Cohen-Macaulay\, Shellable) with those
of the algebra (being quadratic\, Koszul\, having a quadratic GB). Finall
y\, we study the h-vector of the Gorenstein algebras in our construction a
nd answer a question of Peeva and Stillman by showing that it is very ofte
n not gamma-positive. This is joint work with Alessio D'Alì.\n
LOCATION:https://researchseminars.org/talk/CJCS/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrew Suk (UC San Diego)
DTSTART;VALUE=DATE-TIME:20220428T141500Z
DTEND;VALUE=DATE-TIME:20220428T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/60
DESCRIPTION:Title: Un
avoidable patterns in simple topological graphs\nby Andrew Suk (UC San
Diego) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstrac
t\nA simple topological graph is a graph drawn in the plane so that its ve
rtices are represented by points\, and its edges are represented by non-se
lf-intersecting arcs connecting the corresponding points\, with the proper
ty that any two edges have at most one point in common. In 2003\, Pach-So
lymosi-Toth showed that every n-vertex complete simple topological graph c
ontains a topological subgraph on m = Omega(\\log^{1/8} n) vertices that i
s weakly isomorphic to the complete convex geometric graph or to the compl
ete twisted graph on m vertices. Here\, we improve this bound to (log n)^
{1/4 - o(1)}. I will also discuss other related problems as well.\nThis
is joint work with Ji Zeng.\n
LOCATION:https://researchseminars.org/talk/CJCS/60/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Simon Machado (University of Cambridge)
DTSTART;VALUE=DATE-TIME:20220407T141500Z
DTEND;VALUE=DATE-TIME:20220407T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/61
DESCRIPTION:Title: Wh
en are discrete subsets of Lie groups approximate subgroups ? Around a the
orem of Lagarias.\nby Simon Machado (University of Cambridge) as part
of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nMeyer sets ar
e fascinating objects: they are aperiodic subsets of Euclidean spaces that
nonetheless exhibit long-range aperiodic order. Sets of vertices of the P
enrose tiling (P3) and Pisot—Vijarayaghavan numbers of a real number fie
ld are some of the most well-known examples. In modern lingo\, they can be
defined as the discrete and co-compact approximate subgroups of Euclidean
spaces.\n\nLagarias found an elegant characterisation of Meyer sets: they
are those subsets X of a Euclidean space E that are relatively dense (any
point of E is within uniformly bounded distance of X) and whose Minkowski
difference X - X is uniformly discrete (the distance between any two poin
ts is uniformly bounded below). In essence\, his theorem provides a charac
terisation of discrete approximate subgroups that is analogous to the Plun
necke—Ruzsa theorem about sets of small doubling.\n\nI will discuss the
general theory of Meyer sets and state Lagarias theorem. I will explain ho
w additive combinatorics can be used to extend Lagarias result to discrete
subsets of amenable groups. Going beyond the framework of amenable groups
\, I will talk about how one can use simple ideas from additive combinator
ics in combination with powerful tools from ergodic theory - such as Zimme
r’s cocycle superrigidity - to generalise Lagarias theorem to discrete s
ubsets of $SL_n(\\mathbb{R})$ for n > 2.\n
LOCATION:https://researchseminars.org/talk/CJCS/61/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alan Lew (Technion)
DTSTART;VALUE=DATE-TIME:20220217T161500Z
DTEND;VALUE=DATE-TIME:20220217T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/62
DESCRIPTION:Title: Le
ray numbers of tolerance complexes\nby Alan Lew (Technion) as part of
Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nIn this talk
we will discuss the Leray and collapsibility numbers of a simplic
ial complex K\, and their role in Helly-type theorems in combinator
ial geometry. The Leray number is\, roughly speaking\, the hereditary hom
ological dimension of K\, while the collapsibility number captures the com
plexity of dismantling K by sequentially removing free faces from K.\nFoll
owing the formal definition of these parameters and their connection to th
e combinatorics of convex sets\, we will introduce the construction of the
“tolerance complex” of a complex K. We will explain its relation to
a tolerant version of Helly’s theorem due to Montejano and Oliveros and
present new results on the Leray numbers of these complexes.\nThe talk is
based on joint work with Minki Kim.\n
LOCATION:https://researchseminars.org/talk/CJCS/62/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shubhangi Saraf (University of Toronto)
DTSTART;VALUE=DATE-TIME:20220303T151500Z
DTEND;VALUE=DATE-TIME:20220303T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/63
DESCRIPTION:Title: Fa
ctors of sparse polynomials: structural results and some algorithms\nb
y Shubhangi Saraf (University of Toronto) as part of Copenhagen-Jerusalem
Combinatorics Seminar\n\n\nAbstract\nAre factors of sparse polynomials spa
rse? This is basic question\, and we are still quite far from understandin
g it in general. In this talk\, I will show that this is in some sense tru
e for multivariate polynomials when the polynomial has each variable appea
ring only with bounded degree. Our sparsity bound uses techniques from con
vex geometry\, such as the theory of Newton polytopes and an approximate v
ersion of the classical Caratheodory's Theorem. \nUsing our sparsity boun
d\, we then show how to devise efficient deterministic factoring algorithm
s for sparse polynomials of bounded individual degree.\nThe talk is based
on joint work with Vishwas Bhargav and Ilya Volkovich.\n
LOCATION:https://researchseminars.org/talk/CJCS/63/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ashwin Sah (MIT)
DTSTART;VALUE=DATE-TIME:20220324T151500Z
DTEND;VALUE=DATE-TIME:20220324T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/64
DESCRIPTION:Title: Hi
gh-Girth Steiner Triple Systems\nby Ashwin Sah (MIT) as part of Copenh
agen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nWe prove a 1973 conjec
ture due to Erdős on the existence of Steiner triple systems with arbitra
rily high girth. Our proof builds on the method of iterative absorption fo
r the existence of designs by Glock\, Kühn\, Lo\, and Osthus while inc
orporating a "high girth triangle removal process". In particular\, we dev
elop techniques to handle triangle-decompositions of polynomially sparse g
raphs\, construct efficient high girth absorbers for Steiner triple system
s\, and introduce a moments technique to understand the probability our ra
ndom process includes certain configurations of triples. In this talk we w
ill also give a high-level overview of iterative absorption. This work is
joint with Matthew Kwan\, Mehtaab Sawhney\, and Michael Simkin.\n
LOCATION:https://researchseminars.org/talk/CJCS/64/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Amita Malik (Max Planck Institute for Mathematics)
DTSTART;VALUE=DATE-TIME:20220421T141500Z
DTEND;VALUE=DATE-TIME:20220421T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/65
DESCRIPTION:Title: Pa
rtitions into primes with a Chebotarev condition\nby Amita Malik (Max
Planck Institute for Mathematics) as part of Copenhagen-Jerusalem Combinat
orics Seminar\n\n\nAbstract\nIn this talk\, we discuss the asymptotic beha
vior of the number of integer partitions into primes concerning a Chebotar
ev condition. In special cases\, this reduces to the study of partitions i
nto primes in arithmetic progressions. While the study for ordinary partit
ions goes back to Hardy and Ramanujan\, partitions into primes were recent
ly re-visited by Vaughan. Our error term is sharp and improves on previous
known estimates in the special case of primes as parts of the partition.
As an application\, monotonicity of this partition function is established
explicitly via an asymptotic formula in connection to a result of Bateman
and Erdõs.\n
LOCATION:https://researchseminars.org/talk/CJCS/65/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Roman Karasev
DTSTART;VALUE=DATE-TIME:20220505T141500Z
DTEND;VALUE=DATE-TIME:20220505T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/66
DESCRIPTION:Title: Co
vering by planks and avoiding zeros of polynomials\nby Roman Karasev a
s part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nWe not
e that the recent polynomial proofs of (particular \ncases of) the spheric
al and complex plank covering problems by Zhao and \nOrtega-Moreno give so
me general information on zeros of real and complex \npolynomials restrict
ed to the unit sphere. After that we establish \npolynomial analogs of the
Bang theorem by explaining how to find a point \nin the unit ball suffici
ently far from the zero set of a given \npolynomial. As a corollary of the
se results\, we establish a conjecture \nof Jiang and Polyanskii about cov
ering a sphere by spherical segments \ngeneralizing the zone conjecture of
Fejes Tóth.\n\nJoint work with Alexey Glazyrin and Alexander Polyanskii.
\n
LOCATION:https://researchseminars.org/talk/CJCS/66/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yelena Yuditsky (Université libre de Bruxelles)
DTSTART;VALUE=DATE-TIME:20220512T141500Z
DTEND;VALUE=DATE-TIME:20220512T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/67
DESCRIPTION:Title: We
ak Coloring Numbers of Intersection Graphs\nby Yelena Yuditsky (Univer
sité libre de Bruxelles) as part of Copenhagen-Jerusalem Combinatorics Se
minar\n\n\nAbstract\nWeak and strong coloring numbers are generalizations
of the degeneracy of a graph\, where for a positive integer $k$\,\nwe seek
a vertex ordering such every vertex can (weakly respectively strongly) re
ach in $k$ steps only few vertices that precede it in the ordering.\nBoth
notions capture the sparsity of a graph or a graph class\, and have intere
sting applications in the structural and algorithmic graph theory.\nRecent
ly\, Dvoràk\, McCarty\, and Norin observed a natural volume-based upper b
ound for the strong coloring numbers\nof intersection graphs of well-behav
ed objects in $\\mathbb{R}^d$\, such as homothets of a compact convex obje
ct\, or comparable axis-aligned boxes.\n \nWe prove upper and lower bounds
for the $k$-th weak coloring numbers of these classes of intersection gra
phs.\nAs a consequence\, we describe a natural graph class whose strong co
loring numbers are polynomial in $k$\, but the weak coloring numbers\nare
exponential. We also observe a surprising difference in terms of the depen
dence of the weak coloring numbers on the dimension\nbetween touching grap
hs of balls (single-exponential) and hypercubes (double-exponential).\n
LOCATION:https://researchseminars.org/talk/CJCS/67/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Erika Roldan (TU München)
DTSTART;VALUE=DATE-TIME:20220519T141500Z
DTEND;VALUE=DATE-TIME:20220519T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/68
DESCRIPTION:Title: Pa
rity Property of Hexagonal Sliding Puzzles\nby Erika Roldan (TU Münch
en) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nW
e study the puzzle graphs of hexagonal sliding puzzles of various shapes a
nd with various numbers of holes. The puzzle graph is a combinatorial mode
l which captures the solvability and the complexity of sequential mechanic
al puzzles. Questions relating to the puzzle graph have been previously st
udied and resolved for the 15 Puzzle which is the most famous\, and unsolv
able\, square sliding puzzle of all times. The puzzle graph is also a disc
rete model for the configuration space of hard tiles (hexagons or squares)
moving on different tessellation-based domains. Understanding the combina
torics of the puzzle graph leads to understanding some aspects of the topo
logy of these configuration spaces.\n
LOCATION:https://researchseminars.org/talk/CJCS/68/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mathilde Bouvel (LORIA)
DTSTART;VALUE=DATE-TIME:20220602T141500Z
DTEND;VALUE=DATE-TIME:20220602T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/69
DESCRIPTION:Title: Li
mits of permutations and graphs avoiding substructures\nby Mathilde Bo
uvel (LORIA) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAb
stract\nIn this talk\, I would like to present a survey of a series of pap
ers\, describing limits of random graphs or random permutations\, taken un
iformly at random conditioned to avoid certain substructures. \nOur first
results concern families of pattern-avoiding permutations. Our approach is
to use the co-called substitution decomposition of permutations\, thus en
coding permutations as trees. Using analytic combinatorics\, we are then a
ble to compute the expected densities of patterns in our permutations. Thi
s result can be interpreted in the framework of permutons\, thus providing
limit shape results for random pattern-avoiding permutations.\nAnalogous
results can be obtained for hereditary classes of graphs (defined by the a
voidance of induced subgraphs)\, following a similar methodology. The obta
ined results are limit shape results in the framework of graphons.\n
LOCATION:https://researchseminars.org/talk/CJCS/69/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Karin Baur (University of Leeds)
DTSTART;VALUE=DATE-TIME:20221006T141500Z
DTEND;VALUE=DATE-TIME:20221006T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/70
DESCRIPTION:by Karin Baur (University of Leeds) as part of Copenhagen-Jeru
salem Combinatorics Seminar\n\nInteractive livestream: https://ucph-ku.zoo
m.us/j/69204766431?pwd=bCtTczMzVEg2cG03cldKVjdvS09UUT09\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CJCS/70/
URL:https://ucph-ku.zoom.us/j/69204766431?pwd=bCtTczMzVEg2cG03cldKVjdvS09U
UT09
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jamie Tucker-Foltz (Harvard University)
DTSTART;VALUE=DATE-TIME:20220414T141500Z
DTEND;VALUE=DATE-TIME:20220414T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/71
DESCRIPTION:Title: Po
litical Redistricting\, Graph Partition Sampling\, and Counting Spanning T
rees\nby Jamie Tucker-Foltz (Harvard University) as part of Copenhagen
-Jerusalem Combinatorics Seminar\n\n\nAbstract\nSay you are handed a 10 X
10 grid graph and are asked to "randomly" partition the vertices into 10 c
onnected subgraphs of 10 vertices each. How do you do it? From a complexit
y perspective\, the asymptotic version of this question is largely unanswe
red\, and even for these small specific parameters there are some very bas
ic things we don't know how to do efficiently.\n\nThe primary motivation f
or these questions comes from an increasingly popular paradigm for fairnes
s in political redistricting whereby electoral maps are judged in comparis
on to ensembles of randomly generated maps. This is a truly amazing area w
here mathematical theorems are actually having a positive societal impact\
, and the primary goal of this talk will be to inspire more interest in it
. I'll focus on a recent paper of mine (https://arxiv.org/abs/2109.13394)
that sheds light on one particular angle\, but I will also discuss several
tantalizing questions I was unable to answer\, and are still very widely
open.\n
LOCATION:https://researchseminars.org/talk/CJCS/71/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jesus de Loera (UC Davis)
DTSTART;VALUE=DATE-TIME:20220526T141500Z
DTEND;VALUE=DATE-TIME:20220526T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/72
DESCRIPTION:Title: On
Polyhedra Parametrizing ALL pivot rules for the Simplex Method\nby Je
sus de Loera (UC Davis) as part of Copenhagen-Jerusalem Combinatorics Semi
nar\n\n\nAbstract\nThe simplex method is one of the most famous and popula
r algorithms in optimization. The engine of any version of the simplex met
hod is a pivot rule that selects the outgoing arc for a current vertex. Pi
vot rules come in many forms and types\, but after 80 years we are still i
gnorant whether there is one that can make the simplex method run in polyn
omial time. This talk is about the polyhedral combinatorics of the simplex
method. I will present two recent positive results: For 0/1 polytopes the
re are explicit pivot rules for which the number of non-degenerate pivots
is polynomial and even linear (joint work with A. Black\, S. Kafer\, L. Sa
nita). I also present a parametric analysis for all pívot rules. We cons
truct a polytope\, the pivot rule polytope\, that parametrizes all memoryl
ess pívot rules of a given LP. Its construction is a generalization of th
e Fiber polytope construction of Billera Sturmfels. This is an attempt to
get a complete picture of the structure “ space of all pivot rules of an
LP” (joint work with A. Black\, N. Lutjeharms\, and R. Sanyal). No pri
or knowledge of the simplex method will be assume\, I will only assume the
audience loves polytopes.\n
LOCATION:https://researchseminars.org/talk/CJCS/72/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shira Zerbib (Iowa State University)
DTSTART;VALUE=DATE-TIME:20220609T141500Z
DTEND;VALUE=DATE-TIME:20220609T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/73
DESCRIPTION:Title: KK
M-type theorems and their applications\nby Shira Zerbib (Iowa State Un
iversity) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstr
act\nThe KKM theorem\, due to Knaster\, Kuratowski and Mazurkiewicz in 192
9\, is a topological lemma reminiscent of Sperner's lemma and Brouwer's fi
xed point theorem. It has numerous applications in combinatorics\, discret
e geometry\, economics\, game theory and other areas. Generalizations of t
his lemma in several different directions were proved over the years (e.g.
\, by Shapley\, Gale\, Komiya\, Soberon) and have been widely applied as w
ell. We will discuss a recent common generalization of all these theorems.
We will also show two very different applications of KKM-type theorems: o
ne is a proof of a conjecture of Eckhoff from 1994 on the line piercing nu
mbers in certain families of convex sets in the plane\, and the other is a
theorem on fair division of multiple cakes among players with subjective
preferences.\n
LOCATION:https://researchseminars.org/talk/CJCS/73/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Soohyun Park (University of Chicago)
DTSTART;VALUE=DATE-TIME:20220623T141500Z
DTEND;VALUE=DATE-TIME:20220623T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/74
DESCRIPTION:Title: An
ti-Ramsey theory\, lattice points on polytopes\, and Hodge structures on t
oric hypersurfaces\nby Soohyun Park (University of Chicago) as part of
Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nThe relation be
tween the topics in the title is obtained by combining combinatorial inter
pretations of the simplicial chromatic polynomial. A reinterpretation of t
he definition yields the connection to edge colorings of graphs avoiding m
onochromatic colorings of specified subgraphs. As for lattice point counts
on polytopes and Hodge structures on toric hypersurfaces\, we specialize
an expression of the polynomial in terms of the h-vector of an auxiliary s
implicial complex.\n
LOCATION:https://researchseminars.org/talk/CJCS/74/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean Cardinal (Université Libre de Bruxelles)
DTSTART;VALUE=DATE-TIME:20220630T141500Z
DTEND;VALUE=DATE-TIME:20220630T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/75
DESCRIPTION:Title: Di
ameter estimates for graph associahedra\nby Jean Cardinal (Université
Libre de Bruxelles) as part of Copenhagen-Jerusalem Combinatorics Seminar
\n\n\nAbstract\nGraph associahedra are generalized permutohedra arising as
special cases of nestohedra and hypergraphic polytopes. The graph associa
hedron of a graph G encodes the combinatorics of search trees on G\, defin
ed recursively by a root r together with search trees on each of the conne
cted components of G−r. In particular\, the skeleton of the graph associ
ahedron is the rotation graph of those search trees. We investigate the di
ameter of graph associahedra as a function of some graph parameters such a
s treedepth and treewidth\, and give tight estimates for specific families
of graphs\, including trivially perfect\, complete split and complete bip
artite graphs. This is a joint work with Lionel Pournin and Mario Valencia
-Pabon from Université Sorbonne Paris Nord.\n
LOCATION:https://researchseminars.org/talk/CJCS/75/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marie-Charlotte Brandenburg (MPI MiS)
DTSTART;VALUE=DATE-TIME:20220811T141500Z
DTEND;VALUE=DATE-TIME:20220811T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/76
DESCRIPTION:Title: Tr
opical Positivity and Determinantal varieties\nby Marie-Charlotte Bran
denburg (MPI MiS) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\
n\nAbstract\nA determinantal variety is the set of (d x n)-matrices of bou
nded rank.\nWe study the tropicalization of the set of matrices with posit
ive entries and bounded rank\, i.e. the positive part of determinant varie
ties. Given such a (d x n)-matrix of fixed rank r\, we can interpret the c
olumns of the tropicalization of this matrix as n points in d-dimensional
space\, lying on a common r-dimensional tropical linear space. We consider
such tropical point configurations\, and introduce a combinatorial criter
ion to characterize configurations which can be obtained from the tropical
ization of matrices with positive entries.\nNo prior knowledge of tropical
geometry will be assumed for this talk. This is based on joint work with
Georg Loho and Rainer Sinn.\n
LOCATION:https://researchseminars.org/talk/CJCS/76/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mehtaab Sawhney (MIT)
DTSTART;VALUE=DATE-TIME:20220818T141500Z
DTEND;VALUE=DATE-TIME:20220818T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/77
DESCRIPTION:Title: On
low-degree dependencies for sparse random graphs\nby Mehtaab Sawhney
(MIT) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\
nVery sparse random graphs are known to typically be singular (i.e.\, have
singular adjacency matrix)\, due to the presence of "low-degree dependenc
ies" such as isolated vertices and pairs of degree-1 vertices with the sam
e neighborhood. We prove that these kinds of dependencies are in some sens
e the only causes of singularity: for constants $k\\geq 3$ and $\\lambda>0
$\, an Erdős–Rényi random graph of $n$ vertices and edge probability $
\\lambda/n$ typically has the property that its $k$-core (largest subgraph
with min-degree at least $k$) is nonsingular. This resolves a conjecture
of Vu from the 2014 ICM\, and adds to a short list of known nonsingularity
theorems for "extremely sparse" random matrices with density $O(1/n)$. In
subsequent work\, we draw on related techniques to give a precise combina
torial characterization of the co-rank of the Erdős–Rényi random graph
with density $\\lambda/n$ coming from the Karp-Sipser core. A key aspect
of our proof is a technique to extract high-degree vertices and use them t
o "boost" the rank\, starting from approximate rank bounds obtainable from
(non-quantitative) spectral convergence machinery due to Bordenave\, Lela
rge and Salez.\n\nThis talk is based on joint works with Asaf Ferber\, Mar
galit Glasgow\, Matthew Kwan\, and Ashwin Sah.\n
LOCATION:https://researchseminars.org/talk/CJCS/77/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Radoslav Fulek (UC San Diego)
DTSTART;VALUE=DATE-TIME:20220825T141500Z
DTEND;VALUE=DATE-TIME:20220825T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/78
DESCRIPTION:Title: At
omic Embeddability\, Clustered Planarity\, and Thickenability\nby Rado
slav Fulek (UC San Diego) as part of Copenhagen-Jerusalem Combinatorics Se
minar\n\n\nAbstract\nThe planarity testing problem is the algorithmic prob
lem of testing whether a given input graph is planar\, that is\, whether i
t can be drawn in the plane without edge crossings. C-planarity was introd
uced in 1995 by Feng\, Cohen\, and Eades as a generalization of graph plan
arity\, in which the vertex set of the input graph is endowed with a hiera
rchical clustering and we seek an embedding (edge crossing-free drawing) o
f the graph in the plane that respects the clustering in a certain natural
sense.\n\nThe problem of thickenability for simplicial complexes emerged
in the topology of manifolds in the 1960s. A 2-dimensional simplicial comp
lex is thickenable if it embeds in some orientable 3 dimensional manifold.
\n\nWe study the atomic embeddability testing problem\, which is a common
generalization of clustered planarity (c-planarity\, for short) and thicke
nability testing\, and present a polynomial time algorithm for this proble
m\, thereby giving the first polynomial time algorithm for c-planarity.\n\
nBefore our work\, it has been an open problem whether c-planarity can be
tested efficiently\, despite relentless efforts. Recently\, Carmesin annou
nced that thickenability can be tested in polynomial time. Our algorithm f
or atomic embeddability combines ideas from Carmesin's work with algorithm
ic tools previously developed for so-called weak embeddability testing.\n\
nJoint work with Csaba Tóth.\n
LOCATION:https://researchseminars.org/talk/CJCS/78/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joachim Kock (KU)
DTSTART;VALUE=DATE-TIME:20220929T140000Z
DTEND;VALUE=DATE-TIME:20220929T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/79
DESCRIPTION:Title: Fr
om Möbius inversion to renormalisation\nby Joachim Kock (KU) as part
of Copenhagen-Jerusalem Combinatorics Seminar\n\nInteractive livestream: h
ttps://ucph-ku.zoom.us/j/69204766431?pwd=bCtTczMzVEg2cG03cldKVjdvS09UUT09\
n\nAbstract\nAlthough Möbius inversion originates in number theory\, its
standard formulation\, due to Rota\, is in the setting of posets\, where i
t is about splitting of intervals. It has become a standard and widely us
ed counting device in combinatorics and application areas. The goal of th
e talk is to show how a slight generalisation of the Möbius inversion pri
nciple can also explain (the algebraic aspect of) one of the main approach
es to renormalisation of perturbative quantum field theories\, the so-call
ed BPHZ renormalisation (after Bogoliubov\, Parasiuk\, Hepp\, and Zimmerma
n)\, in the Hopf-algebraic formulation due to Kreimer. In the talk\, I wil
l explain all the words above. (In particular\, no prior knowledge of ph
ysics is assumed.)\n\nDietary info: the talk does not contain category the
ory.\n
LOCATION:https://researchseminars.org/talk/CJCS/79/
URL:https://ucph-ku.zoom.us/j/69204766431?pwd=bCtTczMzVEg2cG03cldKVjdvS09U
UT09
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zilin Jiang (Arizona State University)
DTSTART;VALUE=DATE-TIME:20220707T141500Z
DTEND;VALUE=DATE-TIME:20220707T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/80
DESCRIPTION:Title: Ra
inbow structures via topological methods\nby Zilin Jiang (Arizona Stat
e University) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nA
bstract\nGiven a family of structures\, is it possible to choose an elemen
t from each structure to form a new structure of the same kind? This new s
tructure is poetically called rainbow because we can think of each given s
tructure in a different color. Some long standing combinatorial problems\,
such as transversals in a Latin square and the Caccetta–Haggkvist conje
cture\, are rainbow in nature. In this talk\, we will discuss a line of at
tacks to related problems via algebraic topology.\n
LOCATION:https://researchseminars.org/talk/CJCS/80/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Federico Castillo (Universidad Católica de Chile)
DTSTART;VALUE=DATE-TIME:20220714T141500Z
DTEND;VALUE=DATE-TIME:20220714T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/81
DESCRIPTION:Title: Ta
ngent hyperplanes to convex bodies\nby Federico Castillo (Universidad
Católica de Chile) as part of Copenhagen-Jerusalem Combinatorics Seminar\
n\n\nAbstract\nThe Greeks two thousand years ago already knew that two dis
joint circles have four tangent lines. We will explore this question when
the circles are replaced by convex bodies in arbitrary dimensions. Bisztri
czky (1990) proved that\, with the right generalization of disjointness\,
d convex bodies in dimension d have 2^d tangent hyperplanes. In this talk
we present a general description of the set of tangent hyperplanes to m co
nvex bodies in dimension d (with mPu
re-Circuit: Strong Inapproximability for PPAD\nby Alexandros Hollender
(University of Oxford) as part of Copenhagen-Jerusalem Combinatorics Semi
nar\n\n\nAbstract\nPPAD is a complexity class that contains search problem
s that are guaranteed to always have a solution. Due to its close connecti
on with topological tools such as Brouwer's fixed point theorem\, it has e
merged as the class characterizing the complexity of many fundamental prob
lems in game theory and economics. In this talk\, I will introduce the Pur
e-Circuit problem: a new tool for proving hardness of approximation for pr
oblems in the class PPAD. We will see how this new technique can be used t
o show tight inapproximability results for various Nash equilibrium comput
ation problems.\n\nBased on joint work with Argyrios Deligkas\, John Fearn
ley\, and Themistoklis Melissourgos.\n
LOCATION:https://researchseminars.org/talk/CJCS/82/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lisa Sauermann (MIT)
DTSTART;VALUE=DATE-TIME:20220908T141500Z
DTEND;VALUE=DATE-TIME:20220908T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/83
DESCRIPTION:Title: An
ticoncentration in Ramsey graphs and a proof of the Erdös-McKay Conjectur
e\nby Lisa Sauermann (MIT) as part of Copenhagen-Jerusalem Combinatori
cs Seminar\n\n\nAbstract\nThis talk will discuss recent joint work with Ma
tthew Kwan\, Ashwin Sah\, and Mehtaab Sawhney\, proving an old conjecture
of Erdös and McKay (for which Erdős offered $100). This conjecture conce
rns Ramsey graphs\, which are (roughly speaking) graphs without large comp
lete or empty subgraphs. In order to prove the conjecture\, we study edge-
statistics in Ramsey graphs\, i.e. we study the distribution of the number
of edges in a random vertex subset of a Ramsey graph. After discussing so
me background on Ramsey graphs\, the talk will explain our results and giv
e an overview of our proof approach.\n
LOCATION:https://researchseminars.org/talk/CJCS/83/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Déborah Oliveros (UNAM)
DTSTART;VALUE=DATE-TIME:20220915T141500Z
DTEND;VALUE=DATE-TIME:20220915T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/84
DESCRIPTION:Title: In
tersection Patterns and Tverberg type theorems\nby Déborah Oliveros (
UNAM) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\
nOne of the most beautiful and classic theorems in Discrete Geometry is Tv
erberg’s theorem\, which says that any set with sufficiently many points
in $R^d$ can always be partitioned into m parts so that their convex hull
s intersect. In this talk we will give some generalizations of this theore
m that are related to some interesting computing and graph theory problems
as well as some cool applications.\n
LOCATION:https://researchseminars.org/talk/CJCS/84/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ruy Fabila Monroy (Cinvestav)
DTSTART;VALUE=DATE-TIME:20220922T141500Z
DTEND;VALUE=DATE-TIME:20220922T160000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/85
DESCRIPTION:Title: To
ken graph reconstruction in Diamond and C_4 free graphs\nby Ruy Fabila
Monroy (Cinvestav) as part of Copenhagen-Jerusalem Combinatorics Seminar\
n\n\nAbstract\nLet G be a graph on n vertices and 0< k Ne
wton polytope of good symmetric functions\nby Khanh Nguyen Duc (State
University of New York at Albany) as part of Copenhagen-Jerusalem Combinat
orics Seminar\n\nInteractive livestream: https://ucph-ku.zoom.us/j/6920476
6431?pwd=bCtTczMzVEg2cG03cldKVjdvS09UUT09\n\nAbstract\nWe introduce a gene
ral class of symmetric functions that has saturated Newton polytope and th
eir Newton polytope has integer decomposition property. The class covers n
umerous previously studied symmetric functions.\n
LOCATION:https://researchseminars.org/talk/CJCS/94/
URL:https://ucph-ku.zoom.us/j/69204766431?pwd=bCtTczMzVEg2cG03cldKVjdvS09U
UT09
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nick Early (MPI MiS)
DTSTART;VALUE=DATE-TIME:20221215T151500Z
DTEND;VALUE=DATE-TIME:20221215T170000Z
DTSTAMP;VALUE=DATE-TIME:20220929T082100Z
UID:CJCS/95
DESCRIPTION:by Nick Early (MPI MiS) as part of Copenhagen-Jerusalem Combin
atorics Seminar\n\nInteractive livestream: https://ucph-ku.zoom.us/j/69204
766431?pwd=bCtTczMzVEg2cG03cldKVjdvS09UUT09\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CJCS/95/
URL:https://ucph-ku.zoom.us/j/69204766431?pwd=bCtTczMzVEg2cG03cldKVjdvS09U
UT09
END:VEVENT
END:VCALENDAR