BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//6.3//EN
TZID:Asia/Jerusalem
X-WR-TIMEZONE:Asia/Jerusalem
BEGIN:VEVENT
UID:18@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230322T143000
DTEND;TZID=Asia/Jerusalem:20230322T152000
DTSTAMP:20230329T063940Z
URL:https://math.technion.ac.il/en/events/nathan-lindzey-jack-derangements
/
SUMMARY:Nathan Lindzey - Jack Derangements
DESCRIPTION:Lecturer:\n Location:\n The Jack characters are a one-parameter
deformation of the characters of the symmetric group\; a deformation give
n by the coefficients in the expansion of the Jack polynomials in the bas
is of power-sum symmetric functions. For each integer partition of n\, we
give a simple combinatorial formula for the sum of the corresponding Jack
character evaluated over all integer partitions of n with no singleton par
ts. As a corollary\, we obtain closed forms for the eigenvalues of the so-
called permutation and perfect matching derangement graphs\, resolving an
open question in algebraic graph theory. Our proofs center around a Jack a
nalogue of a hook product related to Cayley's Omega-process in classical i
nvariant theory\, which we call the principal lower hook product.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:29@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230329T143000
DTEND;TZID=Asia/Jerusalem:20230329T152000
DTSTAMP:20230329T063921Z
URL:https://math.technion.ac.il/en/events/pavel-chebotarev-majority-domina
tion-on-regular-graphs-a-new-look/
SUMMARY:Pavel Chebotarev - Majority domination on regular graphs: A new loo
k
DESCRIPTION:Lecturer:Pavel Chebotarev\n Location:814 Amado\n A {–1\, 1}-v
ertex-labeled d-regular graph with loops having n vertices and h labels 1
is favorable if a majority of its vertices have a positive sum of labels i
n their neighborhood. Given n and d\, what is the minimum h for which ther
e exists a favorable graph? What is the minimum h for which all labeled gr
aphs are favorable? We answer these questions for all odd n and d\, interp
ret the results from a decision point of view\, and discuss links to exist
ing literature.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:35@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230419T143000
DTEND;TZID=Asia/Jerusalem:20230419T152000
DTSTAMP:20230420T125629Z
URL:https://math.technion.ac.il/en/events/asaf-cohen-antonir-tau-the-upper
-tail-problem-for-irregular-graphs/
SUMMARY:Asaf Cohen Antonir (TAU) -- The upper tail problem for irregular gr
aphs
DESCRIPTION:Lecturer:Asaf Cohen Antonir\n Location:814 Amado\n For any grap
h H we let X_H denote the random variable counting the number of (unlabele
d) copies of H in G_{n\,p}.The study of this random variable goes way back
to the early works of Erdos and Renyi and its typical deviations are well
understood. In this talk\, we will discuss large deviations of X_H. In pa
rticular\, we will be interested in the upper tail problem\, that is – w
hat is the probability of X_H >\; (1+delta) E[X_H]?The upper tail proble
m proved to be very difficult\, and even when H is the triangle\, it was c
ompletely solved only recently by a breakthrough due to Harel\, Mousset an
d Samotij. More generally\, they gave almost optimal bounds when H is a no
n-bipartite regular graph. Building on this breakthrough\, Basak and Basu
obtained optimal bounds for any regular graph H.In this talk we will discu
ss the difficulties of using this method in the case of irregular graphs.
We will show how to overcome these issues for a certain range of p and imp
rove the state-of-the-art result of Cook\, Dembo\, and Pham for almost all
graphs.The talk will be based on a joint work with Matan Harel\, Frank Mo
usset and Wojciech Samotij.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:47@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230503T143000
DTEND;TZID=Asia/Jerusalem:20230503T152000
DTSTAMP:20230430T172657Z
URL:https://math.technion.ac.il/en/events/shachar-lovett-ucsd-tba/
SUMMARY:Shachar Lovett (UCSD) -- The monomial structure of boolean function
s
DESCRIPTION:Lecturer:Shachar Lovett\n Location:814 Amado\n Let f:{0\,1}^n \
\to {0\,1} be a boolean function. It can be uniquely represented as a mult
ilinear polynomial. What is the structure of its monomials? This question
turns out to be connected to some well-studied problems\, such as the log-
rank conjecture in communication complexity and the union-closed conjectur
e in combinatorics. I will describe these connections\, and a new structur
al result\, showing that set systems of monomials of boolean functions hav
e small hitting sets\, concretely of poly-logarithmic size. The proof uses
a combination of algebraic\, probabilistic and combinatorial techniques.\
n\nBased on joint work with Alexander Knop\, Sam McGuire\, and Weiqiang Yu
an.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:56@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230510T143000
DTEND;TZID=Asia/Jerusalem:20230510T152000
DTSTAMP:20230503T085538Z
URL:https://math.technion.ac.il/en/events/igal-sason/
SUMMARY:Igal Sason (Technion) -- On the Lovász theta-Function\, Graph Capa
city\, and Strong Products
DESCRIPTION:Lecturer:Igal Sason\n Location:814 Amado\n This talk is focused
on observations on the Lovász theta-function and capacity of graphs. The
se include a simple closed-form expression of that function for all strong
ly regular graphs\, together with upper and lower bounds on that function
for all regular graphs. These bounds are expressed in terms of the second-
largest and smallest eigenvalues of the adjacency matrix of the regular gr
aph\, together with sufficient conditions for equalities (the upper bound
is due to Lovász\, followed by a new sufficient condition for its tightne
ss). These results are shown to be useful in many ways\, leading to the de
termination of the exact value of the Shannon capacity of some graphs\, ei
genvalue inequalities\, and bounds on the clique and chromatic numbers of
graphs.\n\nThe utility of these bounds is exemplified\, leading in some ca
ses to an exact determination of the chromatic numbers of strong products
or strong powers of graphs. The published version of this work as a journa
l paper appears in https://doi.org/10.3390/e25010104.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:57@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230517T143000
DTEND;TZID=Asia/Jerusalem:20230517T152000
DTSTAMP:20230514T161254Z
URL:https://math.technion.ac.il/en/events/bogdan-chornomaz/
SUMMARY:Bogdan Chornomaz -- Geometric obstruction to replicability in learn
ing
DESCRIPTION:Lecturer:Bogdan Chornomaz\n Location:814 Amado\n We are going t
o talk about the following nice little problem: Given n Boolean functions\
, let us "color" every sample\, compatible with one of these functions\, w
ith some Boolean function\, not necessarily one of the original n\, that i
s compatible with this sample. What is the smallest number of colors that
every chain of samples should have?\n\nWe are going to solve this one\, an
d\, additionally\, we are going to talk about the machine-learning roots o
f this problem\, and about some other nice little questions in the area wh
ere the solution would lead us.\n\nThe talk is based on the joint work wit
h Zachary Chase\, Shay Moran\, and Amir Yehudayoff.\n\n \;\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:73@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230524T143000
DTEND;TZID=Asia/Jerusalem:20230524T152000
DTSTAMP:20230518T143911Z
URL:https://math.technion.ac.il/en/events/yuval-filmus/
SUMMARY:Yuval Filmus -- Nearly linear functions on the symmetric group
DESCRIPTION:Lecturer:Yuval Filmus\n Location:814 Amado\n A linear function
on the symmetric group is is specified by an nxn matrix A\, and its value
at a permutation π is A(1\,π(1)) + … + A(n\,π(n)).\n\nSuch functions
arise naturally in Erdos-Ko-Rado theory on the symmetric group.\n\nWhat ca
n we say about such functions if they are Boolean?\n\nWhat if they are onl
y approximately Boolean?\n\n \;\n\nBased on https://discreteanalysisjo
urnal.com/article/30186-boolean-functions-on-s_n-which-are-nearly-linear\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:58@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230531T143000
DTEND;TZID=Asia/Jerusalem:20230531T152000
DTSTAMP:20230528T092258Z
URL:https://math.technion.ac.il/en/events/jonathan-shafer/
SUMMARY:Jonathan Shafer (UC Berkeley) -- A Trichotomy for Transductive Onli
ne Learning
DESCRIPTION:Lecturer:Jonathan Shafer\n Location:814 Amado\n I will discuss
some recent bounds on the number of learner mistakes in the ‘transductiv
e’ online learning setting of Ben-David\, Kushilevitz and Mansour (1997)
. We show a trichotomy\, stating that the optimal number of mistakes made
by the learner as a function of the sequence length n can take only one of
three possible values: n\, Theta(log n)\, or Theta(1). This behavior is d
etermined by a combination of the VC dimension and the Littlestone dimensi
on. Understanding the precise value in the Theta(1) case is still open\, b
ut we show a quadratic improvement over the previously-known lower bound f
or this quantity.\n\nThe talk will be accessible to a general mathematical
audience\, no prior familiarity with online learning is required.\n\nJoin
t work with Zachary Chase (Oxford Technion)\, Steve Hanneke (Purdue) and S
hay Moran (Technion).\n\n \;\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:59@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230607T143000
DTEND;TZID=Asia/Jerusalem:20230607T152000
DTSTAMP:20230604T135732Z
URL:https://math.technion.ac.il/en/events/daniel-carmon/
SUMMARY:Daniel Carmon -- Dual systolic graphs
DESCRIPTION:Lecturer:Daniel Carmon\n Location:814 Amado\n We define a famil
y of graphs we call dual systolic graphs. This definition comes from graph
s that are duals of systolic simplicial complexes. Our main result is a sh
arp (up to constants) isoperimetric inequality for dual systolic graphs. T
he first step in the proof is an extension of the classical isoperimetric
inequality of the boolean cube. The isoperimetric inequality for dual syst
olic graphs\, however\, is exponentially stronger than the one for the boo
lean cube. Interestingly\, we know that dual systolic graphs exist\, but w
e do not yet know how to efficiently construct them. We\, therefore\, defi
ne a weaker notion of dual systolicity. We prove the same isoperimetric in
equality for weakly dual systolic graphs\, and at the same time provide an
efficient construction of a family of graphs that are weakly dual systoli
c. We call this family of graphs clique products. We show that there is a
non-trivial connection between the small set expansion capabilities and th
e threshold rank of clique products\, and believe they can find further ap
plications.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:76@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230614T133000
DTEND;TZID=Asia/Jerusalem:20230614T142000
DTSTAMP:20230612T195643Z
URL:https://math.technion.ac.il/en/events/igor-balla/
SUMMARY:Igor Balla (HUJI) -- Equiangular lines via matrix projection
DESCRIPTION:Lecturer:Igor Balla (HUJI)\n Location:814 Amado\n [NOTE THE UNU
SUAL TIME] \n\nIn 1973\, Lemmens and Seidel posed the problem of determin
ing the maximum number of equiangular lines in a R^r with angle arccos(alp
ha) and gave a partial answer in the regime r <\;= 1/alpha^2 - 2. At the
other extreme where r is at least exponential in 1/alpha\, recent breakth
roughs have led to an almost complete resolution of this problem. In this
talk\, we introduce a new method for obtaining upper bounds which unifies
and improves upon all previous approaches\, thereby yielding bounds which
bridge the gap between the aforementioned regimes and are best possible ei
ther exactly or up to a small multiplicative constant.\n\nOur approach is
based on orthogonal projection of matrices with respect to the Frobenius i
nner product and it also yields the first extension of the Alon--Boppana t
heorem to dense graphs\, with equality for strongly regular graphs corresp
onding to r(r+1)/2 equiangular lines in R^r. Applications of our method in
the complex setting will be discussed as well.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:60@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230621T143000
DTEND;TZID=Asia/Jerusalem:20230621T152000
DTSTAMP:20230618T170712Z
URL:https://math.technion.ac.il/en/events/wojciech-samotij/
SUMMARY:Wojciech Samotij (TAU) -- Simonovits’s theorem in random graphs
DESCRIPTION:Lecturer:Wojciech Samotij\n Location:814 Amado\n Let H be a gra
ph with chi(H) = r+1. Simonovits's theorem states that\, if H is edge-crit
ical\, the unique largest H-free subgraph of K_n is its largest r-partite
subgraph\, provided that n is sufficiently large. We show that the same ho
lds with K_n replaced by the binomial random graph G_{n\,p} whenever H is
also strictly 2-balanced and p >\;= (theta_H+o(1)) n^(-1/m_2(H)) (log n)
^(1/(e_H-1)) for some explicit constant theta_H\, which we believe to be o
ptimal. This (partially) resolves a conjecture of DeMarco and Kahn.\nThis
is joint work with Ilay Hoshen (TAU).\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:77@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230628T143000
DTEND;TZID=Asia/Jerusalem:20230628T152000
DTSTAMP:20230625T163204Z
URL:https://math.technion.ac.il/en/events/paul-duncan/
SUMMARY:Paul Duncan (HUJI) -- Plaquette Percolation and Ising Lattice Gauge
Theory
DESCRIPTION:Lecturer:Paul Duncan\n Location:814 Amado\n A lattice gauge the
ory is a random assignments of spins to edges of a lattice that offers a m
ore tractable model in which to study path integrals that appear in partic
le physics. We demonstrate the existence of a phase transition correspondi
ng to deconfinement in a simplified model called Ising lattice gauge theor
y on the cubical lattice Z^3. Our methods involve studying the topology of
a random 2-dimensional cubical complex on Z^3 called random-cluster plaqu
ette percolation\, which in turn can be reduced to the study of a random d
ual graph. This is based on joint work with Benjamin Schweinhart.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:108@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20230705T143000
DTEND;TZID=Asia/Jerusalem:20230705T152000
DTSTAMP:20230702T151637Z
URL:https://math.technion.ac.il/en/events/shlomo-hoory/
SUMMARY:Shlomo Hoory (Tel Hai) -- The Girth of Graph Lifts
DESCRIPTION:Lecturer:Shlomo Hoory\n Location:814 Amado\n The size of the sm
allest k-regular graph of girth g is denoted by the well studied function
n(k\,g). We suggest generalizing this function to n(H\,g)\, defined as the
smallest size girth g graph covering the\, possibly non-regular\, graph H
. We prove that the two main combinatorial bounds on n(k\,g)\, the Moore L
ower bound and the Erdos--Sachs upper bound\, carry over to the new settin
g of lifts\, even in their non-asymptotic form.\n\nWe also explore two oth
er generalizations of n(k\,g). Namely\, the minimal size girth g graph sha
ring a universal cover with H\, and the minimal size girth g graph with th
e same degree distribution as H. We show that the former is the same as n(
H\,g) up to a multiplicative constant\, but the latter may or may not be s
eparated by an exponential gap\, depending on the base graph H. We concl
ude with experimental results for a specific base graph and a conjecture.\
n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:148@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240110T110000
DTEND;TZID=Asia/Jerusalem:20240110T120000
DTSTAMP:20240107T135033Z
URL:https://math.technion.ac.il/en/events/high-girth-steiner-triple-system
s/
SUMMARY:High-girth Steiner triple systems
DESCRIPTION:Lecturer:Michael Simkin (MIT)\n Location:Amado 719\n I will dis
cuss our resolution of a 1973 conjecture of Erdős on the existence of Ste
iner triple systems with arbitrarily large girth. (A Steiner triple system
(STS) is a collection of triples on n vertices such that each pair is con
tained in exactly one triple. Its girth is the smallest g >\; 3 for whic
h there exist g vertices spanning at least g-2 triples.) Our construction
builds on the methods of iterative absorption (Glock\, Kühn\, Lo\, and Os
thus) and the high-girth triangle removal process (Glock\, Kühn\, Lo\, an
d Osthus\; Bohman and Warnke).\n\nI will begin by motivating the problem a
nd giving an overview of iterative absorption. As time permits\, I will di
scuss the difficulties present in the high-girth setting and some ideas ne
eded to overcome these challenges\, related to sparsification\, efficient
absorption\, and retrospective analysis of random processes.\n\nThis is jo
int work with Matthew Kwan\, Ashwin Sah\, and Mehtaab Sawhney. Based on ar
Xiv:2201.04554\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:153@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240117T143000
DTEND;TZID=Asia/Jerusalem:20240117T152000
DTSTAMP:20240122T162802Z
URL:https://math.technion.ac.il/en/events/he-guo-technion-non-uniform-degr
ees-and-rainbow-versions-of-the-caccetta-haggkvist-conjecture/
SUMMARY:He Guo (Technion) -- Non-uniform degrees and rainbow versions of th
e Caccetta-Häggkvist conjecture
DESCRIPTION:Lecturer:He Guo\n Location:814 Amado\n \nThe famous Caccetta-H
äggkvist conjecture states that for any n-vertex directed graph D\, the d
irected girth of D (the minimum length of a directed cycle in D) is at mos
t \\lceil n/k \\rceil\, where k is the minimum out-degree of D. Aharoni ra
ised a strengthening conjecture: for any n-vertex graph G equipped with an
edge coloring (not necessarily proper) using n colors\, the rainbow girth
of G (the minimum length of a cycle in G with distinctly colored edges) i
s at most \\lceil n/k \\rceil\, where k is the minimum size of the color c
lass. We will discuss some results in the non-uniform degrees and rainbow
versions of the Caccetta-Häggkvist conjecture.\nBased on works joint with
Ron Aharoni\, Eli Berger\, Maria Chudnovsky\, and Shira Zerbib.\n\n\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:152@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240124T143000
DTEND;TZID=Asia/Jerusalem:20240124T152000
DTSTAMP:20240122T162518Z
URL:https://math.technion.ac.il/en/events/ohad-klein-tel-hai-verifying-gro
ups-in-linear-time/
SUMMARY:Ohad Klein (HUJI) -- Verifying Groups in Linear time
DESCRIPTION:Lecturer:Ohad Klein\n Location:814 Amado\n Given an n × n mult
iplication table\, how can one efficiently check whether it corresponds to
a group? We will give a linear-time test.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:154@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240131T143000
DTEND;TZID=Asia/Jerusalem:20240131T152000
DTSTAMP:20240122T163343Z
URL:https://math.technion.ac.il/en/events/janos-makowsky-technion-supercon
gruences/
SUMMARY:Janos Makowsky (Technion) -- Supercongruences
DESCRIPTION:Lecturer:Janos Makowsky\n Location:814 Amado\n \nLet M be set o
f positive integers. A sequence s(n) satisfies a supercongruence for M if
for every m in M the sequence s(m) mod m is ultimately periodic. s(n) is
MC-finite if M=\\mathbb{N}. We discuss how to prove supercongruences and
give various applications to integer sequences.\n\nJoint work with Y. Film
us\, E. Fischer and V. Rakita.\n\n(Published as: MC-finiteness of restrict
ed set partition functions\, Journal of Integer sequences\, vol. 26 (2023)
Article 23.7.4)\n\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:171@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240207T143000
DTEND;TZID=Asia/Jerusalem:20240207T152000
DTSTAMP:20240206T215916Z
URL:https://math.technion.ac.il/en/events/chaim-even-zohar/
SUMMARY:Chaim Even Zohar (Technion) -- The BCFW Tiling of the Amplituhedron
DESCRIPTION:Lecturer:Chaim Even Zohar\n Location:814 Amado\n The amplituhed
ron A(n\,k\,m) is a geometric object that encodes scattering amplitudes in
various quantum field theories. It has been studied since its discovery i
n 2013 by Arkani-Hamed and Trnka. One of the central conjectures about it
has been that a certain collection of simpler subspaces forms a tiling of
the amplituhedron A(n\,k\,4). In joint work with Tsviqa Lakrec and Ran Tes
sler\, we have settled this conjecture. In the talk\, I will define the am
plituhedron\, discuss the tiling problem\, present the combinatorial struc
tures that appear in its solution\, and outline the main ideas from the pr
oof.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:172@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240214T143000
DTEND;TZID=Asia/Jerusalem:20240214T152000
DTSTAMP:20240212T222303Z
URL:https://math.technion.ac.il/en/events/eli-berger/
SUMMARY:Eli Berger (Haifa) -- Rainbow Matchings
DESCRIPTION:Lecturer:Eli Berger\n Location:814 Amado\n Let M1\,...\,Mm be m
atchings in some graph G. A rainbow matching is a matching with at most
one edge from each of M1\,...\,Mm. Let n>\;=2 be some natural number.
In this talk\, I show that a sufficient condition for the existence of
a rainbow matching of size n is sum_{i=n}^m (|M_i|-n+1) >\; 5 n log2(n)\
, (Where here we assume that each of M1\,...\,M(n-1) is at least as big
as Mn\,...\,Mm). In particular\, this holds when m >\;= n+sqrt(5 n log
2(n)) and each of M1\,...\,Mm has size at least n+sqrt(5 n log2(n)). Thi
s improves a similar result by Correia\, Pokrovskiy\, and Sudakov with 20n
^(7/8) instead of sqrt(5 n log2(n)).\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:173@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240221T143000
DTEND;TZID=Asia/Jerusalem:20240221T152000
DTSTAMP:20240212T123416Z
URL:https://math.technion.ac.il/en/events/idan-mehalel/
SUMMARY:Idan Mehalel (Technion) -- Optimal Prediction Using Expert Advice a
nd Randomized Littlestone Dimension
DESCRIPTION:Lecturer:Idan Mehalel \n Location:814 Amado\n Suppose that n fo
recasting experts (or functions) are providing daily rain/no-rain predicti
ons\, and the best among them is mistaken in at most k many days. For how
many days will a person allowed to observe the predictions\, but has no we
ather-forecasting prior knowledge\, mispredict?\n\nIn this talk\, we will
discuss how such classical problems can be reduced to calculating the (ave
rage) depth of binary trees\, by using newly introduced complexity measure
s (aka dimensions) of the set of experts/functions. All of those measures
are variations of the classical Littlestone dimension (Littlestone ’88).
\n\nFor the forecasting problem outlined above\, Cesa-Bianchi\, Freund\, H
elmbold\, and Warmuth [’93\, ’96] provided a nearly optimal bound for
deterministic learners\, and left the randomized case as an open problem.
We resolve this problem by providing an optimal randomized learner\, and s
howing that its expected mistake bound equals half of the deterministic bo
und of Cesa-Bianchi et al.\, up to negligible additive terms.\n\nFor gener
al (possibly infinite) function classes\, we show that the optimal expecte
d regret (= #mistakes – k) when learning a function class with Littlesto
ne dimension d is of order d + (kd)^0.5.\n\nBased on a joint work with Yuv
al Filmus\, Steve Hanneke\, and Shay Moran.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:174@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240228T143000
DTEND;TZID=Asia/Jerusalem:20240228T152000
DTSTAMP:20240219T161932Z
URL:https://math.technion.ac.il/en/events/lianna-hambardzumyan/
SUMMARY:Lianna Hambardzumyan (HUJI) -- On a problem in Additive Combinatori
cs and Communication Complexity
DESCRIPTION:Lecturer:Lianna Hambardzumyan\n Location:814 Amado\n A central
question in additive combinatorics is to understand how large arithmetic p
rogression free sets can be. In this talk\, I will focus on this question
for high-dimensional generalization of arithmetic progressions (AP) known
as corners.\n\nA (2-dimensional) corner is a triple of the form (x\, y)\,(
x + d\, y)\,(x\, y + d) for some d >\; 0 in [N] × [N]. Extending this d
efinition to higher dimensions\, a k-dimensional corner in [N]^k is a (k+1
)-tuple defined similarly. It is known that corner-free sets have a vanish
ingly small density\, but the precise bounds on their size are unknown. Un
til recently\, the best-known corner-free sets were derived from construct
ions of AP-free sets: a construction of a 3-term AP-free set by Behrend fr
om 1946\, and a generalization by Rankin for k-term APs in 1961. New resul
ts by Linial and Shraibman (CCC 2021) and Green (New Zealand Journal of Ma
thematics 2021) changed this picture\; they improved the upper bound for k
= 2 by adopting a communication complexity point of view.\n\nIn our recen
t work we employ the same perspective of communication complexity and obta
in the first improvement on the upper bound of the size of high-dimensiona
l (k >\; 2) corner-free sets since the original construction of Rankin.\
n\nBased on joint work with Toniann Pitassi\, Suhail Sherif\, Morgan Shirl
ey\, and Adi Shraibman.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:175@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240306T143000
DTEND;TZID=Asia/Jerusalem:20240306T152000
DTSTAMP:20240206T222052Z
URL:https://math.technion.ac.il/en/events/ilay-hoshen/
SUMMARY:Ilay Hoshen (Tel Aviv) -- Stability of large cuts in random graphs
DESCRIPTION:Lecturer:Ilay Hoshen\n Location:814 Amado\n We prove that the f
amily of largest cuts in the binomial random graph exhibits the following
stability property:\n\nIf 1/n <\;<\; p <\; 1-Omega(1)\, then\, with
high probability\, there is a set of n-o(n) vertices that is partitioned i
n the same manner by all maximum cuts of G(n\,p). Moreover\, the analogous
statement remains true when one replaces maximum cuts with nearly-maximum
cuts.\n\nWe then demonstrate how one can use this statement as a tool for
showing that certain properties of G(n\,p) that hold in a fixed balanced
cut hold simultaneously in all maximum cuts. We provide two example applic
ations of this tool. In this talk\, we show that maximum cuts in G(n\,p) t
ypically partition the neighbourhood of every vertex into nearly equal par
ts\; this resolves a conjecture of DeMarco and Kahn for all but a narrow r
ange of densities p. We will also mention another application regarding sh
arp thresholds in Tura'n-type problems.\n\nThis is joint work with Wojciec
h Samotij and Maksim Zhukovskii.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:176@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240313T143000
DTEND;TZID=Asia/Jerusalem:20240313T152000
DTSTAMP:20240311T162409Z
URL:https://math.technion.ac.il/en/events/chaya-keller/
SUMMARY:Chaya Keller (Ariel) -- New Bounds for Zarankiewicz's Problem via e
psilon-t-Nets
DESCRIPTION:Lecturer:Chaya Keller \n Location:814 Amado\n The classical Zar
ankiewicz's problem asks for the maximum number of edges in a bipartite gr
aph on n vertices which does not contain the complete bipartite graph K_{t
\,t}. In one of the cornerstones of extremal graph theory\, Kővari\, Sós
and Turán proved an upper bound of O(n^{2-1/t}). In a celebrated result\
, Fox\, Pach\, Sheffer\, Suk and Zahl obtained an improved bound of O(n^{2
-1/d}) for graphs of VC-dimension d (where d<\;t). Recently\, Chan and H
ar-Peled presented (quasi-)linear upper bounds for several classes of geom
etrically-defined incidence graphs\, including a bound of O(n log log n) f
or the incidence graph of points and pseudo-discs in the plane.\n\nIn this
talk we present a new approach to Zarankiewicz's problem\, via epsilon-t-
nets -- a recently introduced generalization of the classical notion of ep
silon-nets. We show that the existence of `small'-sized epsilon-t-nets imp
lies upper bounds for Zarankiewicz's problem. Using the new approach\, we
obtain a new proof of the O(n^{2-1/d}) bound of Fox et al.\, and a sharp b
ound of O(n) for the intersection graph of two families of pseudo-discs\,
thus both improving and generalizing the result of Chan and Har-Peled from
incidence graphs to intersection graphs.\n\nWe also obtain improved bound
s for several other classes of geometric intersection graphs\, including a
sharp O(n log n / log log n) bound for the intersection graph of two fami
lies of axis-parallel rectangles.\n\nJoint work with Shakhar Smorodinsky.\
n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:177@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240320T143000
DTEND;TZID=Asia/Jerusalem:20240320T152000
DTSTAMP:20240311T165015Z
URL:https://math.technion.ac.il/en/events/sahar-diskin/
SUMMARY:Sahar Diskin (Tel Aviv) -- Percolation through isoperimetry
DESCRIPTION:Lecturer:Sahar Diskin\n Location:814 Amado\n Let G be a d-regul
ar graph of growing degree on n vertices. Form a random subgraph G_p of G
by retaining each edge independently with probability p=p(d). Which condit
ions suffice to observe a phase transition at p=1/d\, similar to that in t
he binomial random graph G(n\,p)?\n\nWe argue that in the supercritical re
gime p=(1+epsilon)/d\, epsilon>\;0 a small constant\, it suffices that e
very subset S of G of at most n/2 vertices has edge-boundary of size at le
ast C|S|\, for some large enough constant C=C(epsilon)>\;0\, to guarante
e the likely appearance of the giant component in G_p. Moreover\, its asym
ptotic order is equal to that in the random graph G(n\,(1+epsilon)/n)\, an
d all other components are typically much smaller.\n\nWe further give exam
ples demonstrating the tightness of this result in several key senses.\n\n
Joint work with Joshua Erde\, Mihyun Kang\, and Michael Krivelevich.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:193@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240327T143000
DTEND;TZID=Asia/Jerusalem:20240327T152000
DTSTAMP:20240326T090217Z
URL:https://math.technion.ac.il/en/events/michael-chapman/
SUMMARY:Michael Chapman -- Proper subgroup testing
DESCRIPTION:Lecturer:Michael Chapman\n Location:814 Amado\n Property testin
g algorithms are designed to extract global properties of the input object
by sampling it locally. In this talk we discuss the following problem: De
sign a proper subgroup tester\, namely\, one that is given a subgroup H of
a group G as input and needs to decide whether H=G or not. To that end\,
we first translate the problem into a purely combinatorial group theory on
e\, which can be shown to be a non-commutative counterpart of error correc
ting codes. We then use the standard theory of error correcting codes as i
nspiration\, and provide several solutions to this problem with various pa
rameters.\n\nThis talk is based on a joint work with Irit Dinur and Alex L
ubotzky.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:178@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240403T143000
DTEND;TZID=Asia/Jerusalem:20240403T152000
DTSTAMP:20240509T154526Z
URL:https://math.technion.ac.il/en/events/johnathan-spiegelman/
SUMMARY:Johnathan Spiegelman (Technion) -- Degree one boolean functions on
some permutation groups.
DESCRIPTION:Lecturer:Johnathan Spiegelman \n Location:814 Amado\n Boolean f
unctions in their original setting are functions f:{0\,1}^n ->\; {0\,1}.
These functions are well studied.\nIn recent years\, researchers have tri
ed to widen the scope and investigate boolean functions on various finite
mathematical objects\, for example\, the Johnson Graph J(n\,k)\, the Grass
man Graph Jq(n\,k)\, the Multislice M(k1\,...\,km)\, the Symmetric Group S
_n\, the Perfect Matching Scheme M_2n.\n\nIn all these cases\, some theore
ms classify degree 1 functions on them. Moreover\, for some of them we kno
w that degree 1 functions are exactly the dictators\, which are functions
that depend on exactly 1 coordinate. This is also the case for the hypercu
be {0\,1}^n on which boolean degree 1 functions are exactly the dictator f
unctions 1\, 0\, x_i\, 1-x_i.\n\nWe investigate boolean functions on the A
lternating Group A_n and the Generalized Symmetric Group S(m\,n)=Z_m \\wr
S_n\, and in particular the Hyperoctheadral Group B_n = S(2\,n). We prove
that except for some anomaly in A_4\, degree 1 boolean functions on them a
re also exactly the dictators.\n\nJoint work with Yuval Filmus.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:231@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240515T143000
DTEND;TZID=Asia/Jerusalem:20240515T152000
DTSTAMP:20240509T154909Z
URL:https://math.technion.ac.il/en/events/omer-moyal/
SUMMARY:Omer Moyal (Technion) -- Topology of random two-dimensional posets
DESCRIPTION:Lecturer:Omer Moyal\n Location:814 Amado\n Random simplicial co
mplexes are one generalization of random graphs. In this seminar\, we will
consider the model of 'permutations complexes'\, a simplicial complex obt
ained from random permutations. More precisely\, let \\pi be a permutation
of length n. Our model is the order complex of the partial order induced
by \\pi on the set [n].\nWe will discuss various topological properties of
this complex\, including homological dimension and homotopy type. Our mai
n result is that w.h.p. the complex is r-connected for r=log(n)/loglog(n).
We will also show that the complex contains an octahedral sphere of dimen
sion c\\sqrt(n)\, and give an upper bound and a new lower bound on c.\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:234@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240529T143000
DTEND;TZID=Asia/Jerusalem:20240529T152000
DTSTAMP:20240509T155927Z
URL:https://math.technion.ac.il/en/events/omri-marcus/
SUMMARY:Omri Marcus (Bar Ilan) -- TBA
DESCRIPTION:Lecturer:Omri Marcus \n Location:814 Amado\n TBA\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:232@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240605T143000
DTEND;TZID=Asia/Jerusalem:20240605T152000
DTSTAMP:20240509T155537Z
URL:https://math.technion.ac.il/en/events/sagi-snir/
SUMMARY:Sagi Snir (Haifa) -- TBA
DESCRIPTION:Lecturer:Sagi Snir\n Location:814 Amado\n TBA\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VEVENT
UID:233@math.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20240619T143000
DTEND;TZID=Asia/Jerusalem:20240619T152000
DTSTAMP:20240509T160010Z
URL:https://math.technion.ac.il/en/events/hilla-schefler/
SUMMARY:Hilla Schefler (Technion) -- TBA
DESCRIPTION:Lecturer:Hilla Schefler \n Location:814 Amado\n TBA\n
CATEGORIES:Combinatorics Seminar
END:VEVENT
BEGIN:VTIMEZONE
TZID:Asia/Jerusalem
X-LIC-LOCATION:Asia/Jerusalem
BEGIN:STANDARD
DTSTART:20221030T010000
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:IST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20230324T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:IDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20231029T010000
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:IST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20240329T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:IDT
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR