[ugrads] Discrete Seminar on Friday, 11/2, 12:45pm, RE119

Hemanshu Kaul kaul at iit.edu
Fri Nov 2 11:03:10 CDT 2018


Just a quick reminder that we have a seminar today at 12:45pm in RE 119.


Hemanshu


On Thu, Oct 25, 2018, 4:17 PM Hemanshu Kaul <kaul at iit.edu wrote:

> Hello all,
>
> Please mark your calendars. We have *Professor Marcus Schaefer,* from*
> CS, DePaul*, visiting us on Friday next week. He will give a talk at *12:45pm
> in RE119, on Friday, 11/2.*
> Professor Schaefer works in the intersection of Computer Science and Graph
> Theory and is an expert in Topological Graph Theory, the field which
> studies how to draw/embed graphs on surfaces.
>
> *Students take a look at*
> * https://www.jasondavies.com/planarity/
> <https://www.jasondavies.com/planarity/>*
> You have to move the vertices (dots) around so that no two edges (line
> segments) intersect each other. Its a fun game to play but how can we know
> whether or not we will succeed in our objective? There is very deep and
> interesting mathematics underlying this simple question.
>
> In his talk, Professor Schaefer will explain the mathematics underlying
> this game that asks you to draw a graph in a ``nice way''. I strongly
> encourage you to attend this fun talk with lots of pictures.
>
> --------------
> *The crossing number of graphs *
>
> *Marcus Schaefer, DePaul University*
>
> *Friday, 11/2, 12:45pm, RE119*
>
>
> *Abstract: *
>
> When drawing a graph in the plane, we may have to allow edges to cross
> each other. The crossing number of a graph is the smallest number of
> crossings required to draw the graph. The crossing number is a measure of
> the non-planarity of a graph, and it has become a central tool in graph
> drawing. In this talk, we will survey some famous results and open problems
> related to the graph crossing number, including Turan’s Brickyard Problem
> (which started it all), the Crossing Lemma, Sylvester’s Problem, Conway’s
> Thrackle Conjecture, and the Hanani-Tutte theorem.
> -----------
>
> I hope to see next Friday at the talk.
>
> 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, Oct 4, 2018 at 3:49 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>
>> Hello all,
>>
>> We have another alum, *Jeff Mudrock*, visiting us next week. He will
>> give a talk on a coloring problem in Graph Theory in the Discrete Applied
>> Math Seminar at *12:45pm, on Friday, October 12th, in RE106*. Jeff
>> successfully completed his PhD earlier this year and was awarded the Menger
>> Award for outstanding graduate student by the department.
>>
>> Jeff is a very good speaker and he intends to make the ideas in his *talk
>> accessible to all students with basic knowledge of Graph Theory*. So I
>> encourage all such students to attend the seminar.
>>
>> An important and widely applied problem in graphs is the conflict-free
>> allocation of limited resources. For example we want to assign frequencies
>> (a limited resource) to radio stations (the entities; each with its own
>> list of potential frequencies) so that close-by stations get different
>> frequencies so that there is no interference (the conflict relationship).
>> Such fundamental resource allocation problems are studied as *``list
>> coloring problems on graphs''*. Jeff's talk will be on the list coloring
>> problem on graphs represented as Cartesian products, an efficient way of
>> representing large graphs using smaller ones.
>>
>> -----------
>>
>> *Title: *List Coloring a Cartesian Product with a Complete Bipartite
>> Factor
>>
>> *Presenter: *Jeffrey Mudrock, College of Lake County
>>
>> *Date: *October 12, 2018
>>
>> *Time: *12:45pm-1:40pm
>>
>> *Location: *RE 106
>>
>>
>>
>> *Abstract:*
>> List coloring, a variation on the typical vertex coloring problem, was
>> introduced independently by Vizing and by Erdos, Rubin, and Taylor in
>> the 1970’s.  In list coloring the vertices of a graph are each assigned a
>> list of colors, a so called list assignment. For a given list
>> assignment, we seek a proper coloring of the graph such that the color we
>> use on each vertex comes from the list associated with the vertex.  The list
>> chromatic number of a graph is the smallest integer k such that the
>> graph has a proper list-coloring for any list assignment that assigns
>> lists of size k to each vertex in the graph.
>>
>>
>> Our work is motivated by a classic result demonstrating that complete
>> bipartite graphs can have arbitrarily large list chromatic number (far from
>> their chromatic number of 2). Here we study the list chromatic number of
>> the Cartesian product of a graph with a complete bipartite graph and when
>> it is as large as possible, far from its chromatic number. We prove tight
>> bounds, improving previously known best results. We also present
>> interesting results in the case that *G* is strongly chromatic-choosable
>> which is a notion of criticality that was recently introduced by H. Kaul
>> and the presenter. Our main tool for obtaining results is the list color
>> function which is a list analogue of the chromatic polynomial. This is
>> joint work with Hemanshu Kaul.
>>
>> ---------------
>>
>>
>> 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
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://math.iit.edu/pipermail/ugrads/attachments/20181102/2b10c3a8/attachment.html>


More information about the ugrads mailing list