Department of

Mathematics


Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Thursday, October 11, 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.
    September 2018          October 2018          November 2018    
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                    1       1  2  3  4  5  6                1  2  3
  2  3  4  5  6  7  8    7  8  9 10 11 12 13    4  5  6  7  8  9 10
  9 10 11 12 13 14 15   14 15 16 17 18 19 20   11 12 13 14 15 16 17
 16 17 18 19 20 21 22   21 22 23 24 25 26 27   18 19 20 21 22 23 24
 23 24 25 26 27 28 29   28 29 30 31            25 26 27 28 29 30   
 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.

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.

Tuesday, May 1, 2018

3:00 pm in 241 Altgeld Hall,Tuesday, May 1, 2018

Planar graphs without adjacent cycles of length at most 8 are 3-choosable

Xiangwen Li (Central China Normal University, Math)

Abstract: DP-coloring as a generation of list coloring was introduced by Dvořák and Postle in 2017, who proved that every planar graph without cycles from 4 to 8 is 3-choosable, which was conjectured by Brodian et al. in 2007. In this paper, we prove that planar graphs without adjacent cycles of length at most 8 are 3-choosable, which extends this result of Dvořák and Postle.

Tuesday, August 28, 2018

2:00 pm in 243 Altgeld Hall,Tuesday, August 28, 2018

The method of hypergraph containers

Jozsef Balogh (Illinois Math)

Abstract: We will give a gentle introduction to a recently-developed technique for bounding the number (and controlling the typical structure) of finite objects with forbidden substructures. This technique exploits a subtle clustering phenomenon exhibited by the independent sets of uniform hypergraphs whose edges are sufficiently evenly distributed; more precisely, it provides a relatively small family of 'containers' for the independent sets, each of which contains few edges. In the first half of the talk we will attempt to convey a general high-level overview of the method; in the second, we will describe a few illustrative applications in areas such as extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry. Note that it is a "repetition of the ICM 2018 talk", hence it will have overlap with several previous (seminar) talks, and no new result will be presented.

Tuesday, September 4, 2018

2:00 pm in 243 Altgeld Hall,Tuesday, September 4, 2018

Cut-edges and regular factors in regular graphs of odd degree

Dara Zirlin (Illinois Math)

Abstract: Previously, Hanson, Loten, and Toft proved that every $(2r+1)$-regular graph with at most $2r$ cut-edges has a 2-factor. We generalize their result by proving for $k \leq (2r+1)/3$ that every $(2r+1)$-regular graph with at most $2r-3(k-1)$ cut-edges has a $2k$-factor. We show that the restriction on $k$ and the restriction on the number of cut-edges are sharp and characterize the graphs that have exactly $2r-3(k-1)+1$ cut-edges but no $2k$-factor. This is joint work with Alexandr Kostochka, André Raspaud, Bjarne Toft, and Douglas West.

Tuesday, September 11, 2018

2:00 pm in 243 Altgeld Hall,Tuesday, September 11, 2018

Polynomial-Time Approximation Scheme for the Genus of Dense Graphs

Yifan Jing (Illinois Math)

Abstract: The graph genus problem is a fundamental problem in topological graph theory and theoretical computer science. In this talk, we provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. The running time of the algorithm is quadratic. Moreover, we extend the algorithm to output an embedding (rotation system), whose genus is arbitrarily close to the minimum genus, and the expected running time is also quadratic. This is joint work with Bojan Mohar.

Tuesday, September 18, 2018

2:00 pm in 243 Altgeld Hall,Tuesday, September 18, 2018

Typical structure of Gallai colorings

Lina Li (Illinois Math)

Abstract: An edge coloring of a graph G is a Gallai coloring if it contains no rainbow triangle. Like many of other extremal problems, it is interesting to study how many Gallai colorings are there and what is the typical structure of the Gallai colorings. We show that almost all the Gallai r-colorings of complete graphs are 2-colorings. We also study Gallai 3-colorings of non-complete graphs. This is joint work with Jozsef Balogh.

Tuesday, September 25, 2018

2:00 pm in 243 Altgeld Hall,Tuesday, September 25, 2018

Generalized Turán problems for graphs and hypergraphs

Ruth Luo (Illinois Math)

Abstract: We will talk about a generalization of the Turán problem for hypergraphs: given a graph $F$, what is the maximum number of hyperedges an $r$-uniform $n$-vertex Berge $F$-free hypergraph can have? In particular, we will discuss tools used to reduce the hypergraph problem to problems for graphs. Finally, I will present some recent results for graphs without long Berge cycles. This is joint work with (different subsets of) Zoltan Furedi and Alexandr Kostochka.

Tuesday, October 2, 2018

2:00 pm in 243 Altgeld Hall,Tuesday, October 2, 2018

Long paths and large matchings in ordered and convex geometric hypergraphs

Alexandr Kostochka (Illinois Math)

Abstract: An ordered $r$-graph is an $r$-uniform hypergraph whose vertex set is linearly ordered, and a convex geometric $r$-graph (cg $r$-graph, for short) is an $r$-uniform hypergraph whose vertex set is cyclically ordered. Extremal problems for ordered and cg graphs have rich history.

We consider extremal problems for two types of paths and matchings in ordered $r$-graphs and cg $r$-graphs: zigzag and crossing paths and matchings. We prove bounds on Turán numbers for these configurations; some of them are exact. Our theorem on zigzag paths in cg $r$-graphs is a common generalization of early results of Hopf and Pannwitz, Sutherland, Kupitz and Perles for cg graphs. It also yields the current best bound for the extremal problem for tight paths in uniform hypergraphs. There are interesting similarities and differences between the ordered setting and the convex geometric setting.

This is joint work with Zoltán Füredi, Tao Jiang, Dhruv Mubayi and Jacques Verstraëte.

Tuesday, October 9, 2018

2:00 pm in 243 Altgeld Hall,Tuesday, October 9, 2018

Independent sets in algebraic hypergraphs

Anush Tserunyan (Illinois Math)

Abstract: A modern trend in extremal combinatorics is extending classical results from the dense setting (e.g. Szemerédi's theorem) to the sparse random setting. More precisely, one shows that a property of a given "dense" structure is inherited by a randomly chosen "sparse" substructure. A recent breakthrough tool for proving such statements is the Balogh–Morris–Samotij and Saxton–Thomason hypergraph containers method, which bounds the number of independent sets in homogeneously dense finite hypergraphs, thus implying that a random sparse subset is not independent. Another trend in combinatorics is proving combinatorial properties for algebraic, or more generally, model theoretically definable structures. Jointly with A. Bernshteyn and M. Delcourt, we combine these trends, establishing a containers-type theorem for hypergraphs definable over an algebraically closed field: if such a hypergraph is "dense", then Zariski-generic low-dimensional sets of vertices induce a relatively "dense" subhypergraph (in particular, they are not independent).

Tuesday, October 16, 2018

2:00 pm in 243 Altgeld Hall,Tuesday, October 16, 2018

Sampling bipartite degree sequence realizations - the Markov chain approach

Péter L. Erdős (A. Rényi Institute of Mathematics)

Abstract: How to analyze real life networks? There are myriads of them and usually experiments cannot be performed directly. Instead, scientists define models, fix parameters and imagine the dynamics of evolution.

Then, they build synthetic networks on this basis (one, several, all) and they want to sample them. However, there are far too many such networks. Therefore, typically, some probabilistic method is used for sampling.

We will survey one such approach, the Markov Chain Monte Carlo method, to sample realizations of given degree sequences. Some new results will be discussed.