<div dir="ltr"><div>This is just a reminder that we have a PhD defense talk by  
 <b>Jeff Mudrock</b>  <b>tomorrow (Friday, 3/23), 12pm, at RE 034</b>.  

Please see the email below for details.<br><br></div>Also, mark your calendars for the<b> next Discrete Math seminar talk on Wednesday, 3/28, in RE 106, at 12:45pm</b>. 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.<br><div><div><div class="gmail_extra"><br></div><div class="gmail_extra">Hemanshu<br clear="all"></div><div class="gmail_extra"><div><div class="m_5847147560098246775m_165059904953583986gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><br></div></div></div></div>
<br><div class="gmail_quote">On Mon, Mar 19, 2018 at 7:40 PM, Hemanshu Kaul <span dir="ltr">&lt;<a href="mailto:kaul@iit.edu" target="_blank">kaul@iit.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div>Hello all,<br><br></div>You are all invited to a talk by <b>Jeff Mudrock</b> on <b>Friday, 3/23, 12pm, at RE 034</b>. This talk constitutes the public portion of Jeff&#39;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. <br><br></div>See below for the detailed abstract.<br><br></div>Hemanshu <br><div><div><br><div style="text-align:left"><font size="2">-----------------<br></font></div><font size="2">
</font><p class="MsoNormal" style="margin:0in 0in 10pt;line-height:115%;font-family:&quot;Times New Roman&quot;,serif;text-align:left"><font size="2"><b>Title:<span>  </span></b>On the list coloring problem and its
equitable variants<span></span><b> <br></b></font></p><p class="MsoNormal" style="margin:0in 0in 10pt;line-height:115%;font-family:&quot;Times New Roman&quot;,serif;text-align:left"><font size="2"><b>Speaker:<span>  </span></b>Jeffrey Mudrock<span></span></font>

</p><p class="MsoNormal" style="margin:0in 0in 10pt;line-height:115%;font-family:&quot;Times New Roman&quot;,serif;text-align:left"><font size="2"><b>Date:<span>  </span></b><span class="m_5847147560098246775m_165059904953583986m_4364509647247769333gmail-aBn"><span class="m_5847147560098246775m_165059904953583986m_4364509647247769333gmail-aQJ">March 23, 2018</span></span><span></span></font></p><div style="text-align:left">

</div><p class="MsoNormal" style="margin:0in 0in 10pt;line-height:115%;font-family:&quot;Times New Roman&quot;,serif;text-align:left"><font size="2"><b>Time:<span>  </span></b><span class="m_5847147560098246775m_165059904953583986m_4364509647247769333gmail-aBn"><span class="m_5847147560098246775m_165059904953583986m_4364509647247769333gmail-aQJ">12:00-1:00pm</span></span><span></span></font></p><div style="text-align:left">

</div><p class="MsoNormal" style="margin:0in 0in 10pt;line-height:115%;font-family:&quot;Times New Roman&quot;,serif;text-align:left"><font size="2"><b>Location:<span>  </span></b>RE 034<span></span></font></p><div style="text-align:left">

</div><p class="MsoNormal" style="margin:0in 0in 10pt;line-height:115%;font-family:&quot;Times New Roman&quot;,serif;text-align:left"><font size="2"><b>Abstract<span></span></b></font><font size="2"><br></font></p><p class="MsoNormal" style="margin:0in 0in 10pt;line-height:115%;font-family:&quot;Times New Roman&quot;,serif;text-align:left"><font size="2">List coloring was introduced independently by Vizing and
Erdos, Rubin, and Taylor in the 1970s.<span> 
</span>Suppose we associate with each vertex, <i>v</i>, of a graph a list, <i>L(v)</i>,
of available colors.<span>  </span>A proper <i>L</i>-coloring of the graph is a proper
coloring such that the color used on each vertex, <i>v</i>, comes from <i>L(v)</i>.<span>  </span>The list chromatic number of a graph <i>G</i> is the minimum <i>k</i> such that there is a proper <i>L</i>-coloring
of <i>G</i> whenever <i>L</i> assigns lists of <i>k</i>
colors to each vertex in <i>V(G)</i>.<span>  </span><span></span></font></p><div style="text-align:left">

</div><p class="MsoNormal" style="margin:0in 0in 10pt;line-height:115%;font-family:&quot;Times New Roman&quot;,serif;text-align:left"><font size="2">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.<span>  </span>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.<span>  </span>We also generalize the notion of strong
critical graphs, introduced by Stiebitz et al. (2008), to strong <i>k</i>-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 <i>k</i>-chromatic-choosable graph satisfying an edge bound.<span>  </span>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.<span></span></font></p><div style="text-align:left"><font size="2">

<span style="line-height:115%;font-family:&quot;Times New Roman&quot;,serif">We also study list
analogues of equitable coloring.<span>  </span>We
begin by studying equitable choosability which was introduced by Kostochka,
Pelsmajer, and West in 2003. <span></span>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.<span>  </span>Finally, we introduce a new list analogue of
equitable coloring: proportional choosability.<span> 
</span>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.<span> 
</span>We study the proportional choosability of graphs with small order and
disconnected graphs, and we completely characterize proportionally 2-choosable
graphs.</span> 

<br>--------------------------</font><br></div><br><div><div><div><div class="gmail_extra"><br clear="all"><div><div class="m_5847147560098246775m_165059904953583986m_4364509647247769333gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div>Hemanshu Kaul<br>Associate Professor of Applied Mathematics<br>Co-Director, Graduate Program on Decision Sciences (CDSOR)<br>Illinois Institute of Technology<br><a href="http://www.math.iit.edu/~kaul/" target="_blank">http://www.math.iit.edu/~kaul/</a><br><a href="http://iit.edu/cdsor" target="_blank">http://iit.edu/cdsor</a><br><br></div></div></div></div>
<br><div class="gmail_quote">On Mon, Feb 26, 2018 at 5:17 PM, Hemanshu Kaul <span dir="ltr">&lt;<a href="mailto:kaul@iit.edu" target="_blank">kaul@iit.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Hello all,<br><br></div>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.<br><div><div><div class="gmail_extra"><br></div><div class="gmail_extra">You can find the abstract and other details at <br></div><div class="gmail_extra"><a href="https://science.iit.edu/events/2018/mar/05/alexandr-kostochka" target="_blank">https://science.iit.edu/events<wbr>/2018/mar/05/alexandr-kostochk<wbr>a</a><br><br></div><div class="gmail_extra">I hope to see you there.<br></div><div class="gmail_extra">Hemanshu<br></div><div class="gmail_extra"><br clear="all"><div><div class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail_signature"><div dir="ltr"><div>Hemanshu Kaul<br>Associate Professor of Applied Mathematics<br>Co-Director, Graduate Program on Decision Sciences (CDSOR)<br>Illinois Institute of Technology<br><a href="http://www.math.iit.edu/~kaul/" target="_blank">http://www.math.iit.edu/~kaul/</a><br><a href="http://iit.edu/cdsor" target="_blank">http://iit.edu/cdsor</a><br><br></div></div></div></div>
<br><div class="gmail_quote">On Tue, Feb 20, 2018 at 1:03 PM, Hemanshu Kaul <span dir="ltr">&lt;<a href="mailto:kaul@iit.edu" target="_blank">kaul@iit.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div>Hello all,<br><br></div>This is just a reminder that we have a seminar tomorrow, 
<b> Wednesday, 2/21, at 12:45pm in RE119</b>. We will have a visitor,<b> Xujun Liu</b>, from UIUC, give a talk on packing chromatic number of cubic graphs. The talk abstract is given below. 

<br><br></div>I hope to see you there.<br><br></div>Hemanshu<br><br><div><div><br><div><div><div class="gmail_extra"><div class="gmail_quote">On Wed, Feb 14, 2018 at 3:21 PM, Hemanshu Kaul <span dir="ltr">&lt;<a href="mailto:kaul@iit.edu" target="_blank">kaul@iit.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div>Hello all,<br><br></div>Please mark your calendars for our next seminar on<b> Wednesday, 2/21, at 12:45pm in RE119</b>. We will have a visitor,<b> Xujun Liu</b>, from UIUC, give a talk on packing chromatic number of cubic graphs. The talk abstract is given below. <br><br></div><div>Also note that we will have Professor Kostochka will be visiting us for a colloquium talk on Monday, March 5th at 1:50pm.<br></div><div><br></div>I hope to see you at the talk.<br></div>Hemanshu<br><div><div><br>--------------------------<br><b>Title:</b> Packing chromatic number of cubic graphs<br></div><div><b>Speaker</b>: Xujun Liu, UIUC<br></div><div><b>Time/Location: </b>Wednesday, 2/21, at 12:45pm in RE119</div><div><b>Abstract: </b>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 &gt; 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.<br>---------------------------<br><br><div><div><div class="gmail_extra"><br clear="all"><div><div class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail_signature"><div dir="ltr"><div>Hemanshu Kaul<br>Associate Professor of Applied Mathematics<br>Co-Director, Graduate Program on Decision Sciences (CDSOR)<br>Illinois Institute of Technology<br><a href="http://www.math.iit.edu/~kaul/" target="_blank">http://www.math.iit.edu/~kaul/</a><br><a href="http://iit.edu/cdsor" target="_blank">http://iit.edu/cdsor</a><br><br></div></div></div></div>
<br><div class="gmail_quote">On Tue, Feb 6, 2018 at 1:08 PM, Hemanshu Kaul <span dir="ltr">&lt;<a href="mailto:kaul@iit.edu" target="_blank">kaul@iit.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hello all,<br><br></div>This is just a reminder that we have a visitor tomorrow, <b> <span class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-il">Anton</span> 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.</b>
 It will include an exposition of some fundamental ideas in graph theory
 and probability. particularly Lovasz Local Lemma.<br><br><div class="gmail_extra"><b>Title</b>: <b>Upper bounds on the chromatic number for triangle-free graphs</b><br>
<b>Speaker: <span class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-il">Anton</span> Bernshteyn, UIUC</b></div><div class="gmail_extra"><b>Time/Location: </b><b> Wednesday, 2/7, at 12:45pm in RE 106<br></b></div><div class="gmail_extra">
<b>Abstract: </b>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&#39;s original proof of this result was quite 
intricate and involved iterated applications of the Lov\&#39;asz Local 
Lemma. Recently, Molloy has sharpened Johansson&#39;s bound to 
$\chi(G)\leq(1+o(1))\Delta/\ln<wbr>\Delta$ using the so-called entropy 
compression method---an algorithmic alternative to the Lov\&#39;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.<br>
</div><div class="gmail_extra"><br></div><div><div><div class="gmail_extra">Hope to see you there,</div><div class="gmail_extra">Hemanshu</div><div class="gmail_extra"><br clear="all"></div><div class="gmail_extra"><div><div class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail_signature"><div dir="ltr"><div>Hemanshu Kaul<br>Associate Professor of Applied Mathematics<br>Co-Director, Graduate Program on Decision Sciences (CDSOR)<br>Illinois Institute of Technology<br><a href="http://www.math.iit.edu/~kaul/" target="_blank">http://www.math.iit.edu/~kaul/</a><br><a href="http://iit.edu/cdsor" target="_blank">http://iit.edu/cdsor</a><br><br></div></div></div></div>
<br><div class="gmail_quote">On Thu, Feb 1, 2018 at 2:15 PM, Hemanshu Kaul <span dir="ltr">&lt;<a href="mailto:kaul@iit.edu" target="_blank">kaul@iit.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hello all,<br><br></div>First, a reminder that we have a seminar tomorrow <b>(Friday, 2/2) at 12:45pm in RE 106. Jeff Mudrock, will talk about Proportional Choosability, </b>a form of equitable allocation of resources through list coloring. See the email below for the details including an abstract.<br><div><div><div><div class="gmail_extra"><br></div><div class="gmail_extra">Second, please note that we will have<b> Anton Bernshteyn, from UIUC, talk about a classic problem of coloring triangle-free graphs, on Wednesday, 2/7, at 12:45pm in RE 106.</b> 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:</div><div class="gmail_extra"><br></div><div class="gmail_extra"><b>Title</b>: <b>Upper bounds on the chromatic number for triangle-free graphs</b><br>
<b>Speaker: Anton Bernshteyn, UIUC</b></div><div class="gmail_extra"><b>Time/Location: </b><b> Wednesday, 2/7, at 12:45pm in RE 106<br></b></div><div class="gmail_extra">
<b>Abstract: </b>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&#39;s original proof of this result was quite 
intricate and involved iterated applications of the Lov\&#39;asz Local 
Lemma. Recently, Molloy has sharpened Johansson&#39;s bound to 
$\chi(G)\leq(1+o(1))\Delta/\ln<wbr>\Delta$ using the so-called entropy 
compression method---an algorithmic alternative to the Lov\&#39;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.<br>
</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br clear="all"></div><div class="gmail_extra"><div><div class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-m_2923295150549904417gmail_signature"><div dir="ltr"><div>best regards,<br></div><div>Hemanshu<br></div><div><br></div></div></div></div>
<br><div class="gmail_quote">On Fri, Jan 26, 2018 at 11:38 AM, Hemanshu Kaul <span dir="ltr">&lt;<a href="mailto:kaul@iit.edu" target="_blank">kaul@iit.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div>Hello all,<br><br></div>We will have the first talk of the semester on <b>Friday, Feb 2nd at 12:45pm in RE 106</b>. <b>Jeff Mudrock</b> will talk about <b>Proportional Choosability</b>, 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.<br></div><div><br></div><div> [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).]<br></div><div><br></div><div>---------------------<br></div><div><div><b>Proportional Choosability: A New List Analogue of Equitable Coloring</b></div><div><b>Jeff Mudrock, IIT<br></b></div><div><b>Date/Time/Location: <span class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-m_2923295150549904417gmail-m_8269606349498308854gmail-aBn"><span class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-m_2923295150549904417gmail-m_8269606349498308854gmail-aQJ">Friday, 2/2/18, 12:45pm, RE 106. </span></span></b><br><b><b><span class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-m_2923295150549904417gmail-m_8269606349498308854gmail-aBn"><span class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-m_2923295150549904417gmail-m_8269606349498308854gmail-aQJ"></span></span></b></b></div><div><br></div><div><b>Abstract</b></div>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. <br></div><div>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. </div><div>--------------------</div><div><br></div><div><br></div><div>Hope to see you there.</div><div>Hemanshu<span class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-m_2923295150549904417gmail-HOEnZb"><font color="#888888"><br></font></span></div><span class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-m_2923295150549904417gmail-HOEnZb"><font color="#888888"><div><br clear="all"><div><div><div><div class="m_5847147560098246775m_165059904953583986m_4364509647247769333m_129384003042697974gmail-m_2715157681680958496m_-4601196174937260838gmail-m_-8160927674333741694gmail-m_2923295150549904417gmail-m_8269606349498308854gmail_signature"><div dir="ltr"><div>Hemanshu Kaul<br>Associate Professor of Applied Mathematics<br>Co-Director, Graduate Program on Decision Sciences (CDSOR)<br>Illinois Institute of Technology<br><a href="http://www.math.iit.edu/~kaul/" target="_blank">http://www.math.iit.edu/~kaul/</a><br><a href="http://iit.edu/cdsor" target="_blank">http://iit.edu/cdsor</a><br><br></div></div></div></div>
</div></div></div></font></span></div>
</blockquote></div><br></div></div></div></div></div>
</blockquote></div><br></div></div></div></div>
</blockquote></div><br></div></div></div></div></div></div>
</blockquote></div><br></div></div></div></div></div></div>
</blockquote></div><br></div></div></div></div>
</blockquote></div><br></div></div></div></div></div></div></div>
</blockquote></div><br></div></div></div></div>