Combinatorics

The Combinatorics seminar meets on Mondays.
2020 Jan 13

Combinatorics: Michael Simkin (HUJI)

10:00am to 12:00pm

Location: 

C-400, CS building

Title: A randomized construction of high girth regular graphs

Abstract: We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k > 2$ and $0 < c < 1$ be fixed. Let $n$ be even and set $g = c \log_{k-1} (n)$. Begin with a Hamilton cycle $G$ on $n$ vertices. As long as the smallest degree $\delta (G)<k$, choose, uniformly at random, two vertices $u,v \in V(G)$ of degree $\delta(G)$ whose distance is at least $g-1$. If there are no such vertex pairs, abort. Otherwise, add the edge $uv$ to $E(G)$.
2020 Mar 23

Combinatorics:

Repeats every week every Monday until Mon Jun 29 2020 except Mon Apr 06 2020.
11:00am to 1:00pm

Location: 

Manchester 110

Speaker: TBA

Title: TBA

Abstract: TBA
2020 Jan 27

Combinatorics: Chaya Keller (Ariel)

10:00am to 12:00pm

Location: 

C-400, CS building

Title: The epsilon-t-net problem


Abstract:

In this talk we study a natural generalization of the classical \eps-net problem (Haussler-Welzl 1987), which we call 'the \eps-t-net problem': Given a hypergraph on n vertices and parameters t and \eps , find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least \eps n  contains a set in S. When t=1, this corresponds to the \eps-net problem.
2019 Dec 23

Combinatorics: Yinon Spinka (UBC)

10:00am to 12:00pm

Location: 

C-400, CS building



Speaker: Yinon Spinka (UBC)


Title: Random graphs on the circle

Abstract: It has long been known that two independent copies of the infinite Erdos-Renyi graph G(\infty,p) are almost surely isomorphic. The resulting graph is called the Rado graph. If the vertices are in a metric space and only nearby vertices may be connected, a similar result may or may not hold, depending on fine details of the underlying metric space. We present new results in the case where the metric space is a circle.
2019 Dec 16

Combinatorics: Orit Raz (HUJI)

10:00am to 12:00pm

Location: 

C-400, CS building

Combinatorics Seminar HUJI


When: Monday Dec 16, 10:00-11:45
Where: C-400, CS building


Speaker: Orit Raz (HUJI)


Title: Dense graphs have rigid parts


Abstract:
2019 Dec 02

Combinatorics: Boaz Slomka (Open U.)

10:00am to 12:00pm

Location: 

C-400, CS building

Speaker: Boaz Slomka (Open U.)
Title: On Hadwiger's covering problem



Abstract:
A long-standing open problem, known as Hadwiger’s covering problem, asks what is the smallest natural number N(n) such that every convex body in R^n can be covered by a union of the interiors of N(n) of its translates. 

In this talk, I will discuss some history of this problem and its close relatives, and present more recent results, including a general upper bound for N(n).
2019 Dec 09

Combinatorics: Ilan Newman (Haifa)

10:00am to 12:00pm

Location: 

C-400, CS building

Speaker: Ilan Newman (Haifa)

Title:  Some recent results on sublinear algorithms for graph related properties

Abstract:
I will describe property testing of (di)graph properties in bounded degree graph models, and talk about a characterization of the 1-sided error testable monotone graph properties and the 1-sided error testable hereditary graph properties in this model. I will introduce the notion of configuration-free properties and talk about some graph theoretic open problems.
2019 Nov 11

Combinatorics: Barak Weiss (TAU)

10:00am to 12:00pm

Location: 

C-400, CS building

Speaker: Barak Weiss (TAU)

Title:  New bounds on the covering radius of a lattice.

Abstract:

We obtain new upper bounds on the minimal density of lattice coverings of R^n by dilates of a convex body K. We also obtain bounds on the probability (with respect to the natural Haar-Siegel measure on the space of lattices) that a randomly chosen lattice L satisfies L + K = R^n. As a step in the proof, we utilize and strengthen results on the discrete Kakeya problem. This is joint work with Or Ordentlich and Oded Regev. 

Pages