Department of

Mathematics

Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Tuesday, March 13, 2018.

.
events for the
events containing

More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
    February 2018            March 2018             April 2018
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2  3                1  2  3    1  2  3  4  5  6  7
4  5  6  7  8  9 10    4  5  6  7  8  9 10    8  9 10 11 12 13 14
11 12 13 14 15 16 17   11 12 13 14 15 16 17   15 16 17 18 19 20 21
18 19 20 21 22 23 24   18 19 20 21 22 23 24   22 23 24 25 26 27 28
25 26 27 28            25 26 27 28 29 30 31   29 30



Tuesday, January 23, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, January 23, 2018

Topological version of Pach's overlap theorem

Boris Bukh (Carnegie Mellon Math)

Abstract: Given a large point set in the plane, where is its 'center'? Unlike the 1-dimensional case, there is not a single answer. We will discuss some of these answers, with the focus on the result of Pach. He showed that one can always find three large subsets A,B,C and a 'central point' p such that every A-B-C triangle contains p. We will then explain the topological generalization of this and related results, where for example the triangle edges are no longer assumed to be straight. Based on a joint work with Alfredo Hubard.

Tuesday, January 30, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, January 30, 2018

An improved upper bound for the (5,5)-coloring number of K_n

Emily Heath (Illinois Math)

Abstract: A $(p,q)$-coloring of a graph $G$ is an edge-coloring of $G$ in which each $p$-clique contains edges of at least $q$ distinct colors. We denote the minimum number of colors needed for a $(p,q)$-coloring of the complete graph $K_n$ by $f(n,p,q)$. In this talk, we will describe an explicit $(5,5)$-coloring of $K_n$ which proves that $f(n,5,5)\leq n^{1/3+o(1)}$ as $n\rightarrow\infty$, improving the best known probabilistic upper bound of $O(n^{1/2})$ given by Erdős and Gyárfás. This is joint work with Alex Cameron.

Tuesday, February 6, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, February 6, 2018

The Slow-coloring Game: Online Sum-Paintability

Douglas B. West (Illinois Math and Zhejiang Normal University)

Abstract: The slow-coloring game is played by Lister and Painter on a graph $G$. Initially, all vertices of $G$ are uncolored. In each round, Lister marks a non-empty set $M$ of uncolored vertices, and Painter colors a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. The score of the game is the sum of the sizes of all sets marked by Lister. The goal of Painter is to minimize the score, while Lister tries to maximize it; the score under optimal play is the cost. A greedy strategy for Painter keeps the cost of $G$ to at most $\chi(G)n$ when $G$ has $n$ vertices, which is asyptotically sharp for Turan graphs. On various classes Painter can do better. For $n$-vertex trees the maximum cost is $\lfloor 3n/2\rfloor$. There is a linear-time algorithm and inductive formula to compute the cost on trees, and we characterize the extremal $n$-vertex trees. Also, Painter can keep the cost to at most $(1+3k/4)n$ when $G$ is $k$-degenerate, $7n/3$ when $G$ is outerplanar, and $3.9857n$ when $G$ is planar. These results involve various subsets of Grzegorz Gutowski, Tomasz Krawczyk, Thomas Mahoney, Gregory J. Puleo, Hehui Wu, Michal Zajac, and Xuding Zhu.

Tuesday, February 13, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, February 13, 2018

Proportional Choosability: A New List Analogue of Equitable Coloring

Jeffrey Mudrock (Department of Applied Mathematics, Illinois Institute of Technology)

Abstract: The study of equitable coloring began with a conjecture of Erdős in 1964, and it was formally introduced by Meyer in 1973. An equitable $k$-coloring of a graph $G$ is a proper $k$-coloring of $G$ such that the sizes of the color classes differ by at most one. In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring, called equitable choosability. Specifically, given lists of available colors of size $k$ at each vertex of a graph $G$, a proper list coloring is equitable if each color appears on at most $\lceil |V(G)|/k \rceil$ vertices. Graph $G$ is equitably $k$-choosable if such a coloring exists whenever all the lists have size $k$. In this talk we introduce a new list analogue of equitable coloring which we call proportional choosability. For this new notion, the number of times we use a color must be proportional to the number of lists in which the color appears. Proportional $k$-choosability implies both equitable $k$-choosability and equitable $k$-colorability, and the graph property of being proportionally $k$-choosable is monotone. We will discuss proportional choosability of graphs with small order, completely characterize proportionally 2-choosable graphs, and illustrate some of the techniques we have used to prove results. This is joint work with Hemanshu Kaul, Michael Pelsmajer, and Benjamin Reiniger.

Tuesday, February 20, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, February 20, 2018

Fractional DP-Colorings

Anton Bernshteyn (Illinois Math)

Abstract: DP-coloring is a generalization of list coloring introduced by Dvořák and Postle in 2015. This talk will be about a fractional version of DP-coloring. There is a natural way to define fractional list coloring; however, Alon, Tuza, and Voigt proved that the fractional list chromatic number of any graph coincides with its ordinary fractional chromatic number. This result does not extend to fractional DP-coloring: The difference between the fractional DP-chromatic number and the ordinary fractional chromatic number of a graph can be arbitrarily large. A somewhat surprising fact about DP-coloring is that the DP-chromatic number of a triangle-free regular graph is essentially determined by its degree. It turns out that for fractional DP-coloring, this phenomenon extends to a much wider class of graphs (including all bipartite graphs, for example). This is joint work with Alexandr Kostochka (UIUC) and Xuding Zhu (Zhejiang Normal University).

Tuesday, February 27, 2018

3:00 pm in 110 Speech and Hearing Building,Tuesday, February 27, 2018

Extending edge-colorings of complete hypergraphs into regular colorings

Amin Bahmanian (Illinois State Math)

Abstract: Let $({X \atop h})$ be the collection of all $h$-subsets of an $n$-set $X\supseteq Y$. Given a coloring (partition) of a set $S\subseteq ({X \atop h})$, we are interested in finding conditions under which this coloring is extendible to a coloring of $({X \atop h})$ so that the number of times each element of $X$ appears in each color class (all sets of the same color) is the same number $r$. The case $S=\emptyset, r=1$ was studied by Sylvester in the 18th century, and remained open until the 1970s. The case $h=2,r=1$ is extensively studied in the literature and is closely related to completing partial symmetric Latin squares. An $r$-factorization is a coloring of $({[n] \atop h})$ so that the number of times each element of $[n]$ appears in each color class is $r$. Let $\chi (m,h,r)$ be the smallest $n$ such that any "partial" $r$-factorization of $({[m] \atop h})$ satisfying $r \mid ({{n-1} \atop {h-1}})$, $h \mid rn$ can be extended to an $r$-factorization of $({[n] \atop h})$. We show that $2m\leq \chi (m,4,r)\leq 4.847323m$, and $2m\leq \chi (m,5,r)\leq 6.285214m$.

Tuesday, March 6, 2018

3:00 pm in Talbot 104,Tuesday, March 6, 2018

Some important combinatorial sequences

Zoltan Furedi (Renyi Institute of Mathematics, Budapest, Hungary and UIUC)

Abstract: The sequence $a(1), a(2), a(3), \dots$ of reals is called subadditive if $a(n+m) \leq a(n)+ a(m)$ for all integers $n,m$. Fekete's lemma states that the sequence $\{a(n)/n\}$ has a limit (it could be negative infinity). Let $f(n)$ be a non-negative, non-decreasing sequence. De Bruijn and Erdos (1952) called the sequence $(a(n))$ nearly $f$-subadditive if $a(n+m) \leq a(n)+ a(m) + f(n+m)$ holds for all $n\leq m \leq 2n$. They showed that if the error term $f$ is small, $\sum_{ n=1}^{\infty} f(n)/n^2$ is finite, then the limit $a(n)/n$ still exists. Their results is listed in the Bollobas-Riordan book (2006) as one of the most useful tools in Percolation Theory. Among other things we show that the de Bruijn-Erdos condition for the error term in their improvement of Fekete's Lemma is not only sufficient but also necessary in the following strong sense. If $\sum_{ n=1}^{\infty} f(n)/n^2 =\infty$, then there exists an nearly $f$-subadditive sequence $(b(n))$, such that the sequence of slopes $(b(n)/n)$ takes every rational number. This is a joint work with I. Ruzsa.

Tuesday, March 13, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, March 13, 2018

On large bipartite subgraphs in dense H-free graphs

Bernard Lidicky (Iowa state University)

Abstract: A long-standing conjecture of Erdős states that any n-vertex triangle-free graph can be made bipartite by deleting at most n^2/25 edges. In this talk, we study how many edges need to be removed from an H-free graph for a general graph H. By generalizing a result of Sudakov for 4-colorable graphs H, we show that if H is 6-colorable then G can be made bipartite by deleting at most 4n^2/25 edges. Moreover, this amount is needed only in the case G is a complete 5-partite graph with balanced parts. As one of the steps in the proof, we use a strengthening of a result of Füredi on stable version of Turán's theorem. This is a joint work with P. Hu,T. Martins-Lopez, S. Norin and J. Volec.