[Discrete-math-seminar] Seminar on Wednesday, 3/28, 12:45pm, RE 106

Hemanshu Kaul kaul at iit.edu
Tue Mar 27 13:44:21 CDT 2018


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/20180327/fdec7f98/attachment-0001.html>


More information about the Discrete-math-seminar mailing list