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

Hemanshu Kaul kaul at iit.edu
Thu Oct 25 16:17:22 CDT 2018


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/20181025/b29fc989/attachment.html>


More information about the ugrads mailing list