- You are here:
- GT Home
- Home
- News & Events

Series: Combinatorics Seminar

We will explain the concept of aproximate well-supported Nash equilibrium
and show that one must consider equilibria with large supports to achieve
good approximation ratio. Our arguments use tools from probabilistic,
extremal and additive combinatorics.
Joint work with Y. Anbalagan, R. Savani and A. Vetta.

Series: Combinatorics Seminar

We study an old problem of Linial and Wilf to find the graphs with n vertices and m edges which maximize the number of proper q-colorings of their vertices. In a breakthrough paper, Loh, Pikhurko and Sudakov asymptotically reduced the problem to an optimization problem. We prove the following structural result which tells us how the optimal solutionlooks like: for any instance, each solution of the optimization problem corresponds to either a complete multipartite graph or a graph obtained from a complete multipartite graph by removing certain edges. We then apply this result on optimal graphs to general instances, including a conjecture of Lazebnik from 1989 which asserts that for any q>=s>= 2, the Turan graph T_s(n) has the maximum number of q-colorings among all graphs with the same number of vertices and edges. We disprove this conjecture by providing infinity many counterexamples in the interval s+7 <= q <= O(s^{3/2}). On the positive side, we show that when q= \Omega(s^2) the Turan graph indeed achieves the maximum number of q-colorings. Joint work with Humberto Naves.

Series: Combinatorics Seminar

We discuss the Maker-Breaker component game, played on the edge set of a sparse random graph. Given a graph G and positive integers s and b, the s-component (1:b) game is defined as follows. In every round Maker claims one free edge of G and Breaker claims b free edges. Maker wins this game if her graph contains a connected component of size at least s; otherwise, Breaker wins the game. For the Erdos-Renyi graph G(n,p), we show that the maximum component size achievable by Maker undergoes a phase transition around p = lambda_{b+2}/n, where lambda_k is the threshold for the appearance of a non-empty k-core in G(n,p) To this end, we analyze the stabilization time of the k-core process in G(n,p). Joint work with Michael Krivelevich, Tobias Mueller, Alon Naor, and Nicholas Wormald.

Series: Combinatorics Seminar

Abstract: There has been a recent flurry of interest in the spectral theory of tensors and hypergraphs as new ideas have faithfully analogized spectral graph theory to uniform hypergraphs. However, even in their simplest incarnation -- the homogeneous adjacency spectrum -- a large number of seemingly basic questions about hypergraph spectra remain out of reach. One of the problems that has yet to be resolved is the (asymptotically almost sure) spectrum of a random hypergraph in the Erd\H{o}s-R\'{e}nyi sense, and we still don't know the spectrum of complete hypergraphs (other than a kind of implicit description for 3-uniform). We introduce the requisite theoretical framework and discuss some progress in this area that involves tools from commutative algebra, eigenvalue stability, and large deviations.

Series: Combinatorics Seminar

We introduce a discrete dynamical system on the set of partial orientations
of a graph, which generalizes Gioan's cycle-cocycle reversal system. We
explain how this setup allows for a new interpretation of the linear
equivalence of divisors on graphs (chip-firing), and a new proof of Baker
and Norine's combinatorial Riemann Roch formula. Fundamental connections
to the max-flow min-cut theorem will be highlighted.

Series: Combinatorics Seminar

Sidorenko's conjecture states that the number of homomorphisms from a bipartite graph $H$ to a graph $G$ is at least the expected number of homomorphisms from $H$ to the binomial random graph with the same expected edge density as $G$. In this talk, I will present two approaches to the conjecture. First, I will introduce the notion of tree-arrangeability, where a bipartite graph $H$ with bipartition $A \cup B$ is tree-arrangeable if neighborhoods of vertices in $A$ have a certain tree-like structure, and show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices $a_1, a_2$ in $A$ such that each vertex $a \in A$ satisfies $N(a) \subseteq N(a_1)$ or $N(a) \subseteq N(a_2)$. Second, I will prove that if $T$ is a tree and $H$ is a bipartite graph satisfying Sidorenko's conjecture, then the Cartesian product of $T$ and $H$ also satisfies Sidorenko's conjecture. This result implies that, for all $d \ge 2$, the $d$-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture. Joint work w/ Jeong Han Kim (KIAS) and Joonkyung Lee (Oxford).

Series: Combinatorics Seminar

The number of permutations with specified descent set is maximized on the (classical) alternating permutations, which are counted by the Euler numbers. Asymptotics for the Euler numbers are well-studied. A counterpart of the descent statistic is the exceedance set statistic which is known to be maximized on a single run of consecutive exceedances. An exact enumeration is known, but the asymptotics have not been studied. We provide asymptotics using multivariate analytic combinatorics (providing a uniformity that goes beyond the range of a basic central limit theorem). This answers a question of E. Clark and R. Ehrenborg. As further applications we also discuss generalized pattern avoidance, and the number of orbit types (n-cycles) that admit a stretching pair (a certificate for "turbulence" in the context of combinatorial dynamics). This includes joint work with R. Ferraz de Andrade and B. Nagle and J. N. Cooper.

Series: Combinatorics Seminar

The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much nicer properties. In this talk we discuss smoothed analysis on trees, or equivalently on connected graphs. A connected graph G on n vertices can be a very bad expander, can have very large diameter, very high mixing time, and possibly has no long paths. The situation changes dramatically when \eps n random edges are added on top of G, the so obtained graph G* has with high probability the following properties:
- its edge expansion is at least c/log n;
- its diameter is O(log n);
- its vertex expansion is at least c/log n;
- it has a linearly long path;
- its mixing time is O(log^2n)
All of the above estimates are asymptotically tight. Joint work with Michael Krivelevich (Tel Aviv) and Wojciech Samotij (Tel Aviv/Cambridge).

Series: Combinatorics Seminar

An equitable two-coloring for a hypergraph is a proper vertex coloring such that the cardinalities of color classes differ by at most one. The well-known Hajnal-Szemerédi theorem states that any graph G with maximum vertex degree d admits an equitable coloring with d + 1 colors. In our talk we shall discuss a similar question for uniform hypergraphs and present a new bound in a Hajnal-Szemerédi-type theorem for some classes of uniform hypergraphs. The proof is based on the random recoloring method and the results of Lu and Székely concerning negative correlations in the space of random bijections.

Series: Combinatorics Seminar

The problem of extending results in extremal combinatorics to sparse random and pseudorandom structures has attracted the attention of many researchers in the last decades. The breakthroughs due to several groups in the last few years have led to a better understanding of the subject, however, many questions remain unsolved. After a short introduction into this field we shall focus on some results in extremal (hyper)graph theory and additive combinatorics. Along the way some open problems will be given.