# [Discrete-math-seminar] Colloquium tomorrow (Monday, 3/5, 1:50pm, RE 104)

Hemanshu Kaul kaul at iit.edu
Sun Mar 4 11:42:52 CST 2018

Hello all,

This is just a reminder that *Professor Alexandr Kostochka *(UIUC) will
give a colloquium talk on *Monday, 3/5, at 1:50pm in RE 104*, on
DP-coloring, a generalization of list coloring.

You can find the abstract and other details at
https://science.iit.edu/events/2018/mar/05/alexandr-kostochka

I hope to see you there,
Hemanshu

-------------------
From: Hemanshu Kaul <kaul at iit.edu>
Date: Mon, Feb 26, 2018 at 5:17 PM
Subject: Discrete Math Colloquium on Monday, 3/5, 1:50pm, RE 104
To: <discrete-math-seminar at math.iit.edu>

Hello all,

Professor Alexandr Kostochka (UIUC) will give a colloquium talk on Monday,
3/5, at 1:50pm in RE 104. He will talk about the exciting new developments
in the field of graph coloring through the topic of DP-coloring, a
generalization of list coloring. Its a colloquium talk so most of it will
be accessible to students. I strongly encourage all students to take
advantage of this opportunity to hear one of the leading graph theorists in
the world.

You can find the abstract and other details at
https://science.iit.edu/events/2018/mar/05/alexandr-kostochka

I hope to see you there.
Hemanshu

Hemanshu Kaul
Associate Professor of Applied Mathematics
Co-Director, Graduate Program on Decision Sciences (CDSOR)
Illinois Institute of Technology
http://www.math.iit.edu/~kaul/
http://iit.edu/cdsor

On Tue, Feb 20, 2018 at 1:03 PM, Hemanshu Kaul <kaul at iit.edu> wrote:

> Hello all,
>
> This is just a reminder that we have a seminar tomorrow, * Wednesday,
> 2/21, at 12:45pm in RE119*. We will have a visitor,* Xujun Liu*, from
> UIUC, give a talk on packing chromatic number of cubic graphs. The talk
> abstract is given below.
>
> I hope to see you there.
>
> Hemanshu
>
>
> On Wed, Feb 14, 2018 at 3:21 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>
>> Hello all,
>>
>> Please mark your calendars for our next seminar on* Wednesday, 2/21, at
>> 12:45pm in RE119*. We will have a visitor,* Xujun Liu*, from UIUC, give
>> a talk on packing chromatic number of cubic graphs. The talk abstract is
>> given below.
>>
>> Also note that we will have Professor Kostochka will be visiting us for a
>> colloquium talk on Monday, March 5th at 1:50pm.
>>
>> I hope to see you at the talk.
>> Hemanshu
>>
>> --------------------------
>> *Title:* Packing chromatic number of cubic graphs
>> *Speaker*: Xujun Liu, UIUC
>> *Time/Location: *Wednesday, 2/21, at 12:45pm in RE119
>> *Abstract: *A packing k-coloring of a graph G is a partition of the
>> vertex set V(G) into sets V_1, ....,V_k, such that for each i, the distance
>> between any two distinct x,y in V_i is at least i+1. The packing chromatic
>> number of a graph G is the minimum k such that G has a packing k-coloring.
>> Sloper showed that there are 4-regular graphs with arbitrarily large
>> packing chromatic number. The question whether the packing chromatic number
>> of subcubic graphs is bounded appears in several papers. We answer this
>> question in the negative. Moreover, we show that for every fixed k and g >
>> 2k+1, almost every n-vertex cubic graph of girth at least g has the packing
>> chromatic number greater than k. Joint work with Jozsef Balogh and Alexandr
>> Kostochka.
>> ---------------------------
>>
>>
>> Hemanshu Kaul
>> Associate Professor of Applied Mathematics
>> Co-Director, Graduate Program on Decision Sciences (CDSOR)
>> Illinois Institute of Technology
>> http://www.math.iit.edu/~kaul/
>> http://iit.edu/cdsor
>>
>>
>> On Tue, Feb 6, 2018 at 1:08 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>>
>>> Hello all,
>>>
>>> This is just a reminder that we have a visitor tomorrow, * Anton
>>> Bernshteyn, from UIUC, giving a talk about a classic problem of coloring
>>> triangle-free graphs, on Wednesday, 2/7, at 12:45pm in RE 106.* It will
>>> include an exposition of some fundamental ideas in graph theory and
>>> probability. particularly Lovasz Local Lemma.
>>>
>>> *Title*: *Upper bounds on the chromatic number for triangle-free graphs*
>>> *Speaker: Anton Bernshteyn, UIUC*
>>> *Time/Location: *
>>> * Wednesday, 2/7, at 12:45pm in RE 106*
>>> *Abstract: *A classical theorem of Johansson from 1996 asserts that
>>> $\chi(G)=O(\Delta/\ln\Delta)$ for triangle-free graphs $G$ of maximum
>>> degree $\Delta$. Johansson's original proof of this result was quite
>>> intricate and involved iterated applications of the Lov\'asz Local Lemma.
>>> Recently, Molloy has sharpened Johansson's bound to
>>> $\chi(G)\leq(1+o(1))\Delta/\ln\Delta$ using the so-called entropy
>>> compression method---an algorithmic alternative to the Lov\'asz Local Lemma
>>> developed by Moser and Tardos. In this talk, I will present a simple proof
>>> of the Johansson--Molloy theorem that avoids the technicalities of the
>>> entropy compression method and only uses the standard Local Lemma (albeit
>>> in a somewhat nonstandard way). I will also talk about some extensions of
>>> this result to more general notions of coloring, such as list and
>>> DP-coloring.
>>>
>>> Hope to see you there,
>>> Hemanshu
>>>
>>> Hemanshu Kaul
>>> Associate Professor of Applied Mathematics
>>> Co-Director, Graduate Program on Decision Sciences (CDSOR)
>>> Illinois Institute of Technology
>>> http://www.math.iit.edu/~kaul/
>>> http://iit.edu/cdsor
>>>
>>>
>>> On Thu, Feb 1, 2018 at 2:15 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>>>
>>>> Hello all,
>>>>
>>>> First, a reminder that we have a seminar tomorrow *(Friday, 2/2) at
>>>> 12:45pm in RE 106. Jeff Mudrock, will talk about Proportional Choosability,
>>>> *a form of equitable allocation of resources through list coloring.
>>>> See the email below for the details including an abstract.
>>>>
>>>> Second, please note that we will have* Anton Bernshteyn, from UIUC,
>>>> talk about a classic problem of coloring triangle-free graphs, on
>>>> Wednesday, 2/7, at 12:45pm in RE 106.* It will include an exposition
>>>> of some fundamental ideas in graph theory and probability. particularly
>>>> Lovasz Local Lemma. Undergraduates who have not heard of Lovasz Local
>>>> Lemma, stop by my office on Tuesday afternoon (after 1:30pm) and ask me. I
>>>> strongly encourage you all to attend the seminar. Here is the abstract:
>>>>
>>>> *Title*: *Upper bounds on the chromatic number for triangle-free
>>>> graphs*
>>>> *Speaker: Anton Bernshteyn, UIUC*
>>>> *Time/Location: *
>>>> * Wednesday, 2/7, at 12:45pm in RE 106*
>>>> *Abstract: *A classical theorem of Johansson from 1996 asserts that
>>>> $\chi(G)=O(\Delta/\ln\Delta)$ for triangle-free graphs $G$ of maximum
>>>> degree $\Delta$. Johansson's original proof of this result was quite
>>>> intricate and involved iterated applications of the Lov\'asz Local Lemma.
>>>> Recently, Molloy has sharpened Johansson's bound to
>>>> $\chi(G)\leq(1+o(1))\Delta/\ln\Delta$ using the so-called entropy
>>>> compression method---an algorithmic alternative to the Lov\'asz Local Lemma
>>>> developed by Moser and Tardos. In this talk, I will present a simple proof
>>>> of the Johansson--Molloy theorem that avoids the technicalities of the
>>>> entropy compression method and only uses the standard Local Lemma (albeit
>>>> in a somewhat nonstandard way). I will also talk about some extensions of
>>>> this result to more general notions of coloring, such as list and
>>>> DP-coloring.
>>>>
>>>>
>>>> best regards,
>>>> Hemanshu
>>>>
>>>>
>>>> On Fri, Jan 26, 2018 at 11:38 AM, Hemanshu Kaul <kaul at iit.edu> wrote:
>>>>
>>>>> Hello all,
>>>>>
>>>>> We will have the first talk of the semester on *Friday, Feb 2nd at
>>>>> 12:45pm in RE 106*. *Jeff Mudrock* will talk about *Proportional
>>>>> Choosability*, a new notion of list coloring with equitable
>>>>> allocation of colors, that arose out of questions and discussion after a
>>>>> talk by Jeff in this seminar last year. The talk will be accessible to any
>>>>> one with a semester of graph theory under their belts. See below for the
>>>>> abstract.
>>>>>
>>>>> [Please mark your calendars also for a talk on Wednesday, Feb 7th at
>>>>> 12:45pm in RE106 by a visitor from UIUC (I will send details later).]
>>>>>
>>>>> ---------------------
>>>>> *Proportional Choosability: A New List Analogue of Equitable Coloring*
>>>>>
>>>>> *Jeff Mudrock, IIT*
>>>>> *Date/Time/Location: Friday, 2/2/18, 12:45pm, RE 106. *
>>>>>
>>>>> *Abstract*
>>>>> The study of equitable coloring began with a conjecture of Erdos 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 ceiling(|V(G)|/k) 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.
>>>>> --------------------
>>>>>
>>>>>
>>>>> Hope to see you there.
>>>>> Hemanshu
>>>>>
>>>>> Hemanshu Kaul
>>>>> Associate Professor of Applied Mathematics
>>>>> Co-Director, Graduate Program on Decision Sciences (CDSOR)
>>>>> Illinois Institute of Technology
>>>>> http://www.math.iit.edu/~kaul/
>>>>> http://iit.edu/cdsor
>>>>>
>>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://math.iit.edu/pipermail/discrete-math-seminar/attachments/20180304/585ea33b/attachment-0001.html>