# [Discrete-math-seminar] Reminder: PhD Defense Talk on Friday, 3/23, 12pm, RE 034

Hemanshu Kaul kaul at iit.edu
Thu Mar 22 13:35:29 CDT 2018

This is just a reminder that we have a PhD defense talk by  *Jeff
Mudrock*  *tomorrow
(Friday, 3/23), 12pm, at RE 034*.  Please see the email below for details.

Also, mark your calendars for the* next Discrete Math seminar talk on
Wednesday, 3/28, in RE 106, at 12:45pm*. Our long-term visitor, Prof.
Joungmin Song from GIST South Korea, will tell us about Hyperplane
arrangements in real affine space, a research problem that lies at the
intersection of Combinatorics, Geometry and Algebra.

Hemanshu

On Mon, Mar 19, 2018 at 7:40 PM, Hemanshu Kaul <kaul at iit.edu> wrote:

> Hello all,
>
> You are all invited to a talk by *Jeff Mudrock* on *Friday, 3/23, 12pm,
> at RE 034*. This talk constitutes the public portion of Jeff's PhD
> defense and is open to all. Jeff will tell us about the research he has
> conducted as a part of his PhD thesis on the list coloring problem and its
> equitable variants.
>
> See below for the detailed abstract.
>
> Hemanshu
>
> -----------------
>
> *Title:  *On the list coloring problem and its equitable variants
>
> *Speaker:  *Jeffrey Mudrock
>
> *Date:  *March 23, 2018
>
> *Time:  *12:00-1:00pm
>
> *Location:  *RE 034
>
> *Abstract*
>
> List coloring was introduced independently by Vizing and Erdos, Rubin, and
> Taylor in the 1970s.  Suppose we associate with each vertex, *v*, of a
> graph a list, *L(v)*, of available colors.  A proper *L*-coloring of the
> graph is a proper coloring such that the color used on each vertex, *v*,
> comes from *L(v)*.  The list chromatic number of a graph *G* is the
> minimum *k* such that there is a proper *L*-coloring of *G* whenever *L*
> assigns lists of *k* colors to each vertex in *V(G)*.
>
> The list chromatic number of the Cartesian product of graphs is not well
> understood. The best result is by Borowiecki et al. (2006) who proved that
> the list chromatic number of the Cartesian product of two graphs can be
> bounded in terms of the list chromatic number and the coloring number of
> the factors.  We use the Alon-Tarsi Theorem and an extension of it
> discovered by Schauz (2010) to find improved bounds on the list chromatic
> number and online list chromatic number of the Cartesian product of an odd
> cycle or complete graph with a traceable graph.  We also generalize the
> notion of strong critical graphs, introduced by Stiebitz et al. (2008), to
> strong *k*-chromatic-choosable graphs, and we get a strictly larger
> family of graphs that includes odd cycles, cliques, the join of a clique
> and any strongly chromatic-choosable graph, and many more families of
> graphs. We prove sharp bounds on the list chromatic number of certain
> Cartesian products where one factor is a strong *k*-chromatic-choosable
> graph satisfying an edge bound.  Our proofs rely on the notion of
> unique-choosability as a sufficient condition for list colorability,
> discovered by Akbari et al. (2006), and the list color function which is a
> list version of the chromatic polynomial.
> We also study list analogues of equitable coloring.  We begin by studying
> equitable choosability which was introduced by Kostochka, Pelsmajer, and
> West in 2003. Expounding upon a conjecture of Fu (1994) on total
> equitable coloring, we form a conjecture regarding the equitable
> choosability of total graphs, and we prove our conjecture for all graphs of
> maximum degree at most 2.  Finally, we introduce a new list analogue of
> equitable coloring: proportional choosability.  For this new notion, the
> number of times a color is used must be proportional to the number of lists
> in which the color appears. Proportional choosability has several useful
> and surprising properties.  We study the proportional choosability of
> graphs with small order and disconnected graphs, and we completely
> characterize proportionally 2-choosable graphs.
> --------------------------
>
>
> 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 Mon, Feb 26, 2018 at 5:17 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>
>> 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/20180322/a08c1c83/attachment-0001.html>