[Discrete-math-seminar] Seminar on Tuesday, 4/3, 12:45pm, RE 119

Hemanshu Kaul kaul at iit.edu
Fri Mar 30 18:03:27 CDT 2018


Hello all,

Our next seminar will be by *Chris Mitillos on Tuesday, 4/3, at 12:45pm in
RE 119*. Chris will update us on the computational complexity of problems
related to the Fall coloring of graphs. See below for the abstract and
other details.

I hope to see you there.
Hemanshu

-------------------
*Title:* Complexity Results in Graph Fall-Colouring

*Speaker*: Christodoulos Mitillos

*Time and Location:* Tuesday, 4/3, 12:45pm in RE119

*Abstract:*
Graph fall-colouring is the partition of the vertices of a graph into
independent dominating sets. A problem is in NP if its solutions can be
verified in polynomial time. A problem is NP-complete if it is in NP and
every problem in NP can be efficiently converted to an instance of this
problem.
In this talk, we will look at some NP-complete problems in graph
fall-colouring. We will review the general problems *kFC*, *FC*, *FKC*, and
*FEDk*, known to be NP-complete for general graphs. We will also look at
specific families of graphs for which some instance of *kFC* is NP-complete.
Joint work with Juho Lauri (Nokia Bell Labs, Ireland)
-------------------



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, Mar 27, 2018, 1:44 PM Hemanshu Kaul <kaul at iit.edu> wrote:

> Hello all,
>
> Professor Joungmin Song (GIST and IIT) will give a talk tomorrow, *
> Wednesday, 3/28, in RE 106, at 12:45pm* on Characteristic Polynomials of
> Hyperplane Arrangements via Enumerative Combinatorics and Finite Field
> Method. This a great chance to learn about research at the intersection of
> Geometry, Algebra and Combinatorics, with a connection to the idea of
> enumerating certain graphs. Prof. Song will define and discuss most
> geometric and algebraic concepts in the talk. Only the knowledge of vector
> spaces and basic linear algebra will be assumed.
>
> See the abstract below for more details.
>
> I hope to see you tomorrow.
> Hemanshu
>
> -------------------------
> *Title: *Characteristic Polynomials of Hyperplane Arrangements via
> Enumerative Combinatorics and Finite Field Method
>
> *Speaker:* Joungmin Song, GIST and IIT
>
> *Time and Location:*12:45pm, Wednesday, 3/28, in RE 106
>
> *Abstract: * A hyperplane arrangement is a finite set of hyperplanes in
> the real affine space R^n. In this talk, we are concerned with the
> hyperplane arrangement J_n consisting of the planes satisfying equations:
> x_i = 0, x_j = 1, and/ or x_i + x_j = 1, 1 <= i, j <= n. The number of
> regions, i.e., the connected components of R^n after removing the
> hyperplanes in J_n is given by the characteristic polynomial of the
> arrangement J_n. We formulate this via enumerative combinatorics and finite
> field method. We also discuss a possible direction forward generalizing
> this process to a multinomial arrangements of similar form.
>
>
> Most geometric and algebraic concepts will be defined and discussed in the
> talk. Only the knowledge of vector spaces and basic linear algebra will be
> assumed.
> -------------------------
>
> 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, Mar 22, 2018 at 1:35 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>
>> 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/20180330/31657df8/attachment-0001.html>


More information about the Discrete-math-seminar mailing list