Department of


Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Monday, April 16, 2018.

events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
      March 2018             April 2018              May 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  4  5  6  7          1  2  3  4  5
  4  5  6  7  8  9 10    8  9 10 11 12 13 14    6  7  8  9 10 11 12
 11 12 13 14 15 16 17   15 16 17 18 19 20 21   13 14 15 16 17 18 19
 18 19 20 21 22 23 24   22 23 24 25 26 27 28   20 21 22 23 24 25 26
 25 26 27 28 29 30 31   29 30                  27 28 29 30 31      

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.

Tuesday, March 27, 2018

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

A containers-type theorem for algebraic hypergraphs

Anton Bernshteyn (Illinois Math)

Abstract: An active avenue of research in modern combinatorics is extending classical extremal results to the so-called sparse random setting. The basic hope is that certain properties that a given "dense" structure is known to enjoy should be inherited by a randomly chosen "sparse" substructure. One of the powerful general approaches for proving such results is the hypergraph containers method, developed independently by Balogh, Morris, and Samotij and Saxton and Thomason. Another major line of study is establishing combinatorial results for algebraic or, more generally, definable structures. In this talk, we will combine the two directions and consider the following problem: Given a "dense" algebraically defined hypergraph, can we show that the subhypergraph induced by a generic low-dimensional algebraic set of vertices is also fairly "dense"? This is joint work with Michelle Delcourt (University of Birmingham) and Anush Tserunyan (UIUC).

Tuesday, April 3, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, April 3, 2018

Packing chromatic number of subdivisions of cubic graphs

Xujun Liu (Illinois Math)

Abstract: A packing $k$-coloring of a graph $G$ is a partition of $V(G)$ into sets $V_1,\ldots,V_k$ such that for each $1\leq i\leq k$ the distance between any two distinct $x,y\in V_i$ is at least $i+1$. The packing chromatic number, $\chi_p(G)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. For a graph $G$, let $D(G)$ denote the graph obtained from $G$ by subdividing every edge. The questions on the value of the maximum of $\chi_p(G)$ and of $\chi_p(D(G))$ over the class of subcubic graphs $G$ appear in several papers. Gastineau and Togni asked whether $\chi_p(D(G))\leq 5$ for any subcubic $G$, and later Brešar, Klavžar, Rall and Wash conjectured this, but no upper bound was proved. Recently the authors proved that $\chi_p(G)$ is not bounded in the class of subcubic graphs $G$. In contrast, in this paper we show that $\chi_p(D(G))$ is bounded in this class, and does not exceed $8$. Joint work with József Balogh and Alexandr Kostochka.

Tuesday, April 10, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, April 10, 2018

Directed hypergraphs

Gyorgy Turan (UIC Math)

Abstract: Directed graphs can be generalized to directed hypergraphs in different ways. The version where hyperedges can have several vertices in their tail, but only a single head, comes up in many contexts, such as reasoning with implications and closure operators. Paths are defined using a forward chaining process. We discuss some extremal, algorithmic and probabilistic aspects of directed hypergraphs and mention several open problems.

Tuesday, April 17, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, April 17, 2018

The Erdős–Gallai theorem for cycles in hypergraphs

Ruth Luo (UIUC Math)

Abstract: The Erdős–Gallai theorem states that if a graph $G$ on $n$ vertices has no cycle of length $k$ or longer, then $e(G) \leq (k-1)(n-1)/2$. We present a hypergraph analogue of this theorem. A berge-cycle of length $\ell$ in an $r$-uniform hypergraph is a set of $\ell$ hyperedges $\{e_1, ..., e_\ell\}$ and $\ell$ vertices $\{v_1, ..., v_\ell\}$ such that hyperedge $e_i$ contains the vertices $v_i$ and $v_{i+1}$. We show that for $r \geq k+1$, if $H$ is an $r$-uniform hypergraph on $n$ vertices with no berge-cycle of length $k$ or longer, then $|H| \leq (k-1)(n-1)/r$. This is joint work with Alexandr Kostochka.

Tuesday, April 24, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, April 24, 2018

Colorings of signed graphs - a short survey

Andre Raspaud (LaBRI, Bordeaux University)

Abstract: The signed graphs and the balanced signed graphs were introduced by Harary in 1953. But all the notions can be found in the book of König (Theorie der endlichen und unendlichen graphen 1935). An important, fundamental and prolific work on signed graphs was done by Zaslavsky in 1982. In this talk we are interested in coloring of signed graphs. We will give a short survey of the different existing definitions and the recent results on the corresponding chromatic numbers. We will also present new results obtained by using the DP-coloring.