We will discuss results given by Csikvari who proved that certain graph parameters have their extreme points at the star and at the path among the trees on a fixed number of vertices. He gave many applications of the so-called generalized tree shift which induces a partially ordered set on trees having fixed number of vertices. He proved that certain graph parameters (Wiener-index, Estada index, the number of closed walks of a fixed length, largest eigenvalue of the adjacency matrix A and Laplacian matrix L, coefficients of independence polynomial, coefficients of the edge cover polynomial, coefficients of the characteristic polynomials of A and L in absolute value) increase or decrease along this poset of trees

A total weighting of a graph G is a mapping f which assigns to each element z a real number f(z) as its weight. The vertex sum of v with respect to f is the sum of weight of v and weights of edges adjacent to v. A total weighting is proper if vertex sums of adjacent vertices are distinct. A (k, k')-list assignment is a mapping L which assigns to each vertex v a set L(v) of k permissible weights, and assigns to each edge e a set L(e) of k’ permissible weights. We say G is (k, k')-choosable if for any (k,k')-list assignment L, there is a proper total weighting f of G with f(z) L(z) for each z. It was conjectured by Wong and Zhu that every graph is (2,2)-choosable and every graph with no isolated edge is (1, 3)-choosable. We will see a proof of the statement in the title, due to Wong and Zhu.

Suppose we want to label the edges of the complete bipartite graph K_{n,n} with elements of F_2^d in such a way that the sum of labels over any simple cycle is nonzero. What is the smallest possible value of d be for such a labeling to exist? It was proved by Gopalan et. al. that log^2(n) \leq d \leq nlog(n). Kane, Lovett and Rao recently proved that d is in fact linear in n. In particular we have n/2-2 \leq d < 6n. Upper bound is established by explicit construction while lower bound is obtained by bounding the size of independent sets in certain Cayley graphs of S_n.

Let n be any positive integer, n]:={1,2,...,n}, and suppose $D\subset\{-n,-n+1,..,-1,0,1,...,n}$. Let F be a family of subsets of [n]. A family F' of subsets of [n] is said to be D-secting for F if for every A in the family F, there exists a subset A'in F' such that $|A\cap A'|-|A\cap ([n]\setminus A')| = i$, for some $i\in D$. A D-secting family F' of F, where D = {-1,0,1}, is a bisecting family ensuring the existence of a subset $A'\in F'$ such that $|A\cap A'|\in{\lfloor |A|/2\rfloor, \lceil |A|/2\rceil\}$ for each $A\in F$. We consider the problem of determining minimal D-secting families F' for certain families F and some related questions. This is based on joint work with Rogers Mathew, Tapas Mishra, and Sudebkumar Prashant Pal.

In this talk, we will have a look at three results, starting with the following. [Berlekamp-Welch] Given a univariate polynomial function over F_q with data corruption at t < q/2 points, we can recover the function completely if the degree of the function is sufficiently low. A generalization of the above is as follows, where instead of 'recovering' the function, we find all its 'close approximates'. [Madhu Sudan] Given data points (x_i,y_i), i \in [n], and parameters k and t, we can list all polynomials with degree at most k, which satisfy at least t data points. This result can further be generalized as follows. [Madhu Sudan] Given data points (x_i,y_i) with weights w_i, i \in [n], and parameters k and W, we can list all polynomials with degree at most k such that the sum of weights of data points satisfied by the polynomial is at least W. The last two results provide list-decoding of Reed-Solomon codes.

It is well known that a "good" large subset of the Euclidean space contains approximately as many lattice points as its volume. This need not hold for a general subset. On the other hand, a classical theorem of Siegel asserts that for any subset of positive measure, the "average" number of points (in an appropriate sense) of a general unimodular lattice contained in it, equals the measure of the set. In place of the average over the entire space of lattices one may also ask for analogous results for smaller subclasses. In a recent work with Jayadev Athreya, we explored this issue, with some modifications that place the problem in perspective, for the case of symplectic lattices, viz. lattices (in even-dimensional spaces) obtained from the standard lattice under symplectic transformations. In this talk I shall describe the overall asymptotics in this case, together with the historical background of the results and techniques involved.

A tricolored-sum-free set in F_2^n is a collection of triples {(a_i,b_i,c_i)}_{I=1..m} such that a) for each I, a_i+b_i+c_i=0 b) If a_i+b_j+c_k = 0, then I=j=k. The notion of a tricoloured-sum-free set generalizes the notion of a capset to F_2^n. The basic question here is: How large can a tricolored-sum-free set be? We will see the following two (recent) results. i) Kleinberg's upper bound of 6\binom{n}{n/3} for a tricolored-sum-free set. This in conjunction with a previous result of his establishing a lower bound of \binom{n {n/3}2^{-\sqrt{16n/3}} gives almost asymptotically tight results. ii) Ben Green (in 2005) proved the following BOOLEAN REMOVAL LEMMA: Given \epsilon>0 there exists \delta depending only on epsilon such that the following holds: Write N=2^n. If X,Y,Z are subsets of F_2^n if by deleting \epsilon N elements from X,Y, Z altogether, one can eliminate all arithmetic triangles (triples (x,y,z) with \in X,y\in Y,z\in Z such that x+y+z=0) then there are at most \delta N^2 arithmetic triangles in (X,Y,Z). Green's proof establishes a bound for1/(\delta) which is a tower of 2s of length poly(1/\epsilon). We will look at a recent result of Fox and Lovasz (junior) who obtained an almost tight bound for this delta-epsilon dependence with \delta =O(\epsilon^{O(1)}).

A tricolored-sum-free set in F_2^n is a collection of triples {(a_i,b_i,c_i)}_{I=1..m} such that a) for each I, a_i+b_i+c_i=0 b) If a_i+b_j+c_k = 0, then I=j=k. The notion of a tricoloured-sum-free set generalizes the notion of a capset to F_2^n. The basic question here is: How large can a tricolored-sum-free set be? We will see the following two (recent) results. i) Kleinberg's upper bound of 6\binom{n}{n/3} for a tricolored-sum-free set. This in conjunction with a previous result of his establishing a lower bound of \binom{n {n/3}2^{-\sqrt{16n/3}} gives almost asymptotically tight results. ii) Ben Green (in 2005) proved the following BOOLEAN REMOVAL LEMMA: Given \epsilon>0 there exists \delta depending only on epsilon such that the following holds: Write N=2^n. If X,Y,Z are subsets of F_2^n if by deleting \epsilon N elements from X,Y, Z altogether, one can eliminate all arithmetic triangles (triples (x,y,z) with \in X,y\in Y,z\in Z such that x+y+z=0) then there are at most \delta N^2 arithmetic triangles in (X,Y,Z). Green's proof establishes a bound for1/(\delta) which is a tower of 2s of length poly(1/\epsilon). We will look at a recent result of Fox and Lovasz (junior) who obtained an almost tight bound for this delta-epsilon dependence with \delta =O(\epsilon^{O(1)}).

A sunflower with p petals is a family of sets A_1,...,A_p such that the intersections of all pairs of distinct sets are the same. A famous conjecture in combinatorics, called the Sunflower conjecture, asserts a bound on the maximum size of any family of k-sets that does not contain a p-sunflower. We review some recent work by Ellenberg-Gijswijt and Naslund-Swain that proves a weak variant of this conjecture due to Erdos and Szemeredi.

A construction of Behrend from the 1940s shows that there are subsets of [N] of size N^{1-o(1)} that contain no 3-term APs (also called capsets). For a long time, it was open whether there is such a construction over F_3^n (i.e. a capset in F_3^n of size 3^{n-o(n)}). Recently, building on work of Croot, Lev and Pach, it was shown by Ellenberg and Gijswijit ( https://arxiv.org/abs/1605.09223 ) that such a construction does not exist: i.e. any capset in F_3^n can have size at most c^n for some c < 3. The construction has had several applications already in Combinatorics and Theoretical Computer Science. We will see a proof of the theorem of Ellenberg and Gijswijt