Abstracts

New identities for degrees of syzygies in numerical groups
Leonid Fel, Technion

Abstract: We derive a set of polynomial and quasipolynomial identities for the degrees of syzygies in the Hilbert series $H(d^m; Z)$ of nonsymmetric numerical subgroups $S(d^m)$ for an arbitrary generating set of positive integers $d^m = (d_1,\ldots,d_m)$, $m>2$ . These identities were obtained by studying together the rational representation of the Hilbert series $H(d^m; z)$ and the quasipolynomial representation of the Sylvester waves in the restricted partition function, $W(s,d^m)$. In the cases of symmetric semigroups and complete intersections these identities become more compact.

Back

On equivalence of polynomial conjectures in additive combinatorics
Shachar Lovett, Weizmann Institute of Science

Abstract: We will discuss two important conjectures in additive combinatorics. The first one is the polynomial Freiman-Rusza conjecture, which relates to the structure of sets with small doubling. The second is the inverse Gowers conjecture for U^3, which relates to functions which locally look like quadratics. In both conjectures a weak form, with exponential decay of parameters is known, and a strong form with only a polynomial decay of parameters is conjectured. We will show that the two conjectures are in fact equivalent. This was also discovered independently by Green and Tao.

Back

Policemen and thieves in graphs
Simon Litsyn, Tel-Aviv University

Abstract: To save on municipal budget we wish to minimize the number of policemen in a city described by a graph. The policemen are positioned at graph vertices (cross-roads) and are in control of their own vertex along with its neighbors. Whenever a criminal occurs in her vicinity, the guard sends alarm signal to the central office. The condition is that having known the set of worried policemen, the department head should be able to locate the unique vertex where the crime happens. We will prove that in Manhattan the police posts have to be placed at exactly 35% of the street intersections.  We will also survey known results on the problem in alternative settings: different types of graphs, the number of thieves greater than one, and the graphical radius of control greater than one.

Back

Permutations and triangulations
Yuval Roichman, Bar-Ilan University

Abstract: In our talk last year triangulations were encoded by elements in an affine Weyl group, yielding an exact evaluation of the diameter of a certain flip graph. This year triangulations are encoded by permutations, leading to a solution of a conjecture of Richard Stanley. We will present this result and some other applications, including introducing descents of triangulations and cyclic sieving phenomena.

This talk is a report on work in progress, partly joint with Bruce Sagan and Ron Adin.

Back

Complementary sets of integers
Aviezri Fraenkel, Weizmann Institute of Science

Abstract: Old and new results, problems and conjectures on sets that split the   integers. From Leopold Kronecker (1884), Lord John William Strutt Rayleigh (1894), Samuel Beatty (1926), Alexander Markowitsch Ostrowski (1927),    James V. Uspensky (1927), up to Ron Graham (1963), (1973), Thoralf Albert Skolem (1957), Th\o ger Bang (1957), Ryozo Morikawa (1985), Robert Jamie Simpson (1986, 1991, 2004), Robert Tijdeman (2000), Kevin O'Bryant (2002), Graham and O'Bryant (2005) and many others. Emphasis is on contemporary results such as fractal-like and fractional complementary sets of integers, including a 37-year old conjecture that has been solved for the integers and for the irrationals, yet is wide open for the rationals. Applications to combinatorial games will be indicated.

In part, this is joint work with Peter Hegarty and Urban Larsson.

Back

Symmetric LDPC codes and local testing
Tali Kaufman, CS, Bar-Ilan University

Abstract: Local computation tasks (as local testing, correcting, decoding) is possible in codes based on polynomials. This is related to the fact that such codes are highly symmetric, yet they are defined by short linear equations. Codes defined by short linear equations are called LDPC. In the heart of this work is the following question: Could we have high rate codes which are highly symmetric, yet are defined by short linear equations?  In this work we construct codes with rate better than polynomial codes that are defined by short equations.  Moreover we obtain bounds on the best rate of such symmetric codes.

Back

The number of standard tableaux in the (k,l) hook
Amitai Regev, Weizmann Institute of Science

Abstract: Exact formulas for the number of standard tableaux with at most k rows are known for k=2, 3, 4 and 5. We discuss the analogous problem for (k,l) hook shapes.

Back

A tight quantitative version of Arrow's Impossibility Theorem
Nathan Keller, Weizmann Institute of Science

Abstract: A Generalized Social Welfare Function (GSWF) is an election procedure in a society of n members, where the members are given m alternatives, and each member chooses a ranking of them. Then, the individual rankings are aggregated by some choice function to the "total preference of the society" amongst each pair of alternatives. The well-known Impossibility Theorem of Arrow shows a surprising relation between several "natural" properties of GSWFs:

1. Independence of Irrelevant Alternatives (IIA) - the resulting preference amongst any pair of candidates depends only on the individual preferences amongst that pair of candidates, and not on other candidates.

2. Unanimity - if all the voters prefer alternative A over B, then in the resulting preference A is also preferred over B.

3. Dictatorship - the preference of the society is determined by a single member.

4. Non-transitivity - the GSWF is non-transitive if there exists a combination of individual preferences for which the society prefers A over B, B over C, and C over A, for some alternatives A, B, C, thus yielding a "paradox".

Arrow's theorem asserts that any GSWF with at least three alternatives, which satisfies the IIA condition and Unanimity and is not a dictatorship, is necessarily non-transitive. In 2002, Kalai asked whether one can obtain the following quantitative version of the theorem: For any \epsilon \gt 0, there exists \delta such that if a GSWF on three alternatives satisfies the IIA condition and its probability of non-transitive outcome is at most \delta, then the GSWF is at most \epsilon-far from being a dictatorship or from breaching the Unanimity condition. In 2009, Mossel proved such quantitative version, with \delta=\exp(-C/\epsilon^{21}), and generalized it to GSWFs with m alternatives, for all m \geq 3.
 
In this talk we improve Mossel's result and show that the quantitative version holds with \delta=C \cdot \epsilon^3, and that this result is tight up to logarithmic factors. Furthermore, our result (like Mossel's) generalizes to GSWFs with m alternatives.

Back

Why Angelina Jolie and Brad Pitt are a couple
(or: Matching of like rank and the size of the core in the marriage problem)
Dov Samet, Tel-Aviv University

Abstract: When men and women are objectively ranked in a marriage problem, say by beauty, then pairing individuals of equal rank is the only stable matching. We generalize this observation by providing bounds on the size of the rank gap between mates in a stable matching in terms of the size of the ranking sets. Using a metric on the set of matchings, we provide bounds on the diameter of the core---the set of stable matchings---in terms of the size of the ranking sets and in terms of the size of the rank gap. We conclude that when the set of rankings is small, so are the core and the rank gap in stable matchings.

Back

The hat problem on a directed graph
Rani Hod, Tel-Aviv University

Abstract: A team of players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his or her own hat color by looking at the hat colors of other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom she or he is connected by an arc. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The team aims to maximize the probability of a win, and this maximum is called the hat number of the graph.

Previous works focused on the problem on complete graphs and on undirected graphs. Some cases were solved, e.g., complete graphs of certain orders, trees, cycles, bipartite graphs. These led Uriel Feige to conjecture that the hat number of any graph is equal to the hat number of its maximum clique.

We show that the conjecture does not hold for directed graphs, and build, for any fixed clique number, a family of directed graphs of asymptotically optimal hat number. We also determine the hat number of tournaments to be one half.

Joint work with Marcin Krzywkowski.

Back

Random Matrix Theory and combinatorial properties of random d-regular graphs
Uzy Smilansky (Weizmann Institute of Science, Hebrew University and Cardiff University)

Abstract: I shall describe two new results concerning the spectra of d-regular graphs:

1. Derive a 1-parameter family of trace formulae, expressing the spectral density in terms of periodic cycles on the graphs.
2. Using the known statistics of counts of cycles on the graphs and the trace formulae, I shall present a connection with Random Matrix Theory.

Based on these results, I would like to propose a conjecture which uses Random Matrix Theory to compute the variance of the t-periodic cycle counts in the limit $n,t \to \infty$ with t/n =constant (any constant). Numerical computations support this conjecture.

Back