Garth Isaak's Mathematics Information

Students who I have advised or am advising:

- Sam Donelley, Undergraduate honors thesis, 1997. `Powers of Hamiltonian paths and Powers of Hamiltonian Cycles in Threshold Graphs'. Now am member of the Database Research Group, University of Pennsylvania.
- Darren Narayan , PhD May 2000. `The Reversing Number of a Digraph'. Now at Rochester Institute of Technology
- Trisha Moller , PhD August 2004. `t-split interval orders'. Initially at DeSales University. Now working part time at Moravian College and part time with family.
- Brian Heinold, PhD May 2006. `Sum List Coloring and Choosability'. Now at Mt. St. Mary's University Maryland.
- Jen Scancella Gorman, PhD August 2007, `Nested Traveling Salesperson Problems', Now at Gannon University.
- Ellen Panofsky, PhD May 2008. `Graph Labeling Problems with Distance Conditions', Now at Cabrini College.
- Jonelle Hook, PhD student, starting fall 2007, expected completion spring 2010.

Postdoctoral visitors to Lehigh that I have worked with:

- Art Busch 2005-2006, now at University of Dayton.
- Colton Magnant, starting Fall 2008.


I have also served on the PhD thesis committees of over a dozen students from various departments: computer science, electrical engineering, industrial engineering and mathematics.

Here is a list of my published research papers. I have links to most of the papers (many are prepublication versions nearly in final
form).  For the others if you want a copy please send me an email for a hard copy.

1.G. Isaak and B. Tesman, The Weighted Reversing Number of a Digraph, Congressus Numerantium, 83 (1991) 115-124
2. H. Abeledo and G. Isaak, A Characterization of Graphs that Ensure the Existence of Stable Matchings, Math. Social Sciences, 22 (1991) 93-96
3. G. Isaak, S. Kim, T.A. McKee, F.R. McMorris and F.S. Roberts, 2-Competition Graphs, SIAM J. Discrete Math., 5 (1992) 524-538.
4. G. Isaak, Bounded Discrete Representations of Interval Orders, Discrete Appl. Math., 44 (1993) 157-183.
5. G. Hurlbert and G. Isaak, On the de Bruijn Torus Problem , J. Combinatorial Theory A, 64 (1993) 50-62.
6. G. Hurlbert and G. Isaak, A Meshing Technique for deBruijn Tori , Contemporary Math.  178 (1994) 153-160.
7. G. Isaak, Scheduling Rooted Forests with Communication Delays, Order, 11 (1994) 309-316.
8. J.P. Barthelemy, O. Hudry, G. Isaak, F.S. Roberts and B. Tesman, The Reversing Number of a Digraph , Discrete Appl. Math., 60 (1995) 39-76.
9. K.P. Bogart, P.C. Fishburn, G. Isaak and L. Langley, Proper and Unit Tolerance Graphs , Discrete Appl. Math., 60 (1995) 99-117.
10. G. Hurlbert and G. Isaak, New Constructions for de Bruijn Tori, Designs, Codes and Cryptography, 6 (1995) 47-56.
11. G. Isaak, Tournaments as Feedback Arc Sets , Electronic Journal of Combinatorics, 2 (1995) #R20, 19pp.
12. J. Driscoll, D. Healy and G. Isaak, Scheduling Dyadic Intervals , Discrete Appl. Math., 63 (1995) 101-116.
13. G. Hurlbert and G. Isaak, Equivalence Class Universal Cycles for Permutations , Discrete Math., 149 (1996) 123-129.
14. G. Hurlbert and G. Isaak, On Higher Dimensional Perfect Factors , Ars Combinatoria, 45 (1997) 129-139.
15. K.P. Bogart and G. Isaak, Proper and Unit Bitolerance Orders , Discrete Math., 181 (1998) 37-51.
16. G. Isaak, Powers of Hamilton Paths in Interval Graphs , J. Graph Theory 27 (1998) 31-38.
17. S. Donelley and G. Isaak, Hamiltonian Powers in Threshold and Arborescent Comparability Graphs, Discrete Math., 202 (1999) 33-44.
18. A.B. Evans, G. Isaak and D. Narayan, Representations of Graphs Modulo n, Discrete Math., 223 (2000) 109-123.
19. K.P. Bogart, G. Isaak, J. Liason and A. Trenk, Comparability Invariance Results for Tolerance Orders, Order, 18 (2001) 281-294.
20. G. Isaak, Constructions for Higher Dimensional Perfect Factors , Aequationes Math., 64 (2002) 70-88.
21. G. Isaak, Sum List Coloring 2 by n Arrays, Electron. J. Combinatorics 9 (2002) Note 8, 7 pp.
22. G. Isaak, K. Nyman and A. Trenk, A Heirarchy of Classes of Bounded Bitolerance Orders, Ars Combinatoria, 69 (2003) 33-53.
23. D. Narayan and G.Isaak, A Complete Classifcation of Tournaments having a Disjoint Union of Directed Paths as a Minimum Feedback Arc Set , J. Graph Theory, 45 (2004) 28 - 47.
24.G. Isaak Sum List Coloring Block Graphs, Graphs and Combinatorics 20 (2004) 499-506.
25. D. Narayan and G. Isaak, A Classification of Tournaments having an Acyclic Tournament as a Minimum Feedback Arc Set , Inf. Proc. Let. 92 (2004) 107-111.
26. G. Isaak, Hamiltonicity of Digraphs for Universal Cycles of Permutations, European Journal of Combinatorics 27 (2006) 801-805.
27. A.H. Busch and G. Isaak, Recognizing Bipartite Unbounded Tolerance Graphs in Linear Time, Lecture Notes in Computer Science 4769 (2007) 12-20 .
28. M.J. Fisher and G. Isaak, Distinguishing Colorings of Cartesian Products of Complete Graphs, Discrete Mathematics 308 (2008) 2240-2246.
29. G. Isaak, Interval Order representation via Shortest Paths, in The Mathematrics of Preference, Choice and Order - Essays in honor of Peter Fishburn,
S. Brams, W.V. Gehrlein, F.S. Roberts eds, Springer (2009) 303-311.
30. G. Isaak, R. Jamison, D. Narayan, Greedy Rankings and Arank Numbers, Information processing Letters 109 (2009) 825-827.
31. D.E. Brown, A.H. Busch, G. Isaak, Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance and Probe Interval Graphs, manuscript, submitted June 2009.
32. J. Hook and G. Isaak, Star Avoiding Ramsey Numbers , manuscript, submitted August 2009.
33. G. Isaak and D.B. West, The Edge-Count Criterion for Graphic Lists , manuscript, submitted September 2009.
34. J. Carroll and G. Isaak, Degree Matrices Realized by Edge Colored Forsts , manuscript

Here are several unpublished papers:

- Examples of Combinatorial Duality : an expository paper giving examples of the theorem of the alternative for linear
inequalities is used to prove Hoffman's circulation theorem and then from this Fishburn's Interval order representation
theorem and Landau's theorem for score sequences of tournaments.
- Chain Packings and Odd Subtree Packings : an old unpublished paper building on work from my PhD thesis. It seems that part of what I did had been done before and the other part done several years later by others.

Here are slides from some talks:

- Perfect maps and factors : My first computer based talk.
- When does x < a, x > 0 have a solution? : A talk for undergraduates based on my expository paper `Examples of combinatorial duality'.
- Score sequences for tournaments Another talk for undergraduates
- An edge Count Criterion for Degree Sequences On degree sequences for edge colored graphs
- Intervals and orders: what comes after interval orders A talk for a special session in memory of Ken Bogart
- Distinguishing number of cartersian products of complete graphs
- Structure of bipartite probe interval graphs
- Star avoiding Ramsey numbers

Some combinatorial questions

This is an out of date description. The papers also are linked in the list above.

A research statement from my tenure file in 1998

Here are some of my current research interests and favorite problems. Well - not really; my favorite problems are the hard well known ones. I will mention problems that are less well known and closely related to my current research

Feedback Arc Digraphs: who gets upset in tournament rankings

A feedback arc set in a digraph is a set of arcs whose removal makes the digraph acyclic. A minimum size feedback arc set in a tournament is also the set of arc inconsistent with a `ranking' which minimizes inconsistencies. Every acyclic digraph is a feedback arc set of some tournament. That is, given an acyclic digraph, which we think of as the inconsistencies from a ranking, what is the smallest size of a tournament in which the ranking procedure described above gives exactly those inconsistencies. (We do allow a ranking procedure to produce several equal rankings and we search for the inconsistencies under one of these.) In particular we can look at `the' acyclic tournament as the set of inconsistencies. This provides bounds for other acyclic digraphs. So we ask: what is the smallest size of a tournament which produces a set of n people each pair of which is ranked wrong. I have a specific conjecture about this, along with partial results and related questions in Tournaments as Feedback Arc Sets (Electronic Journal Of Combinatorics Vol 2 (1995) article R20). The partial results are obtained by viewing the problem as an integer linear programming problem. More recent results have been obtained with recent Lehigh PhD Darren Narayan. See his research page for more information.

Powers of Hamiltonian Paths

Label the vertices of a graph so as to maximize the minimum distance between non-adjacent vertices. This is in a sense dual' to the bandwidth problem, which seeks to minimize the maximum distance between adjacent vertices. This problem is also a variant on Hamitonian paths, looking for powers of Hamiltonian paths instead. Some of my papers on this are: Hamiltonian Powers in Threshold and Arborescent Comparability Graphs (with Sam Donnelly, Discrete Mathematics 202 (1999) 33-44) and Powers of Hamiltonian Paths in Interval Graphs (Journal of Graph Theory 28 (1998) 31-38).

Perfect Maps: how determine your location in n dimensions

List the string 00011101 cyclically. Each triple occurs exactly once. This is known as a perfect map or de Bruijn cycle. Many questions can be asked about higher dimensional versions of this and version with an alphabet of size k (instead of 2). In particular are the `obvious' necessary conditions sufficient? Kenny Patterson in London has answered this completely in 2-dimensions for k a prime power. Many other interesting questions arise about related structures called perfect factors and perfect multi-factors which arise in the study of these objects. For more information and references to other work see these papers my recent paper (which is partially survey and partially new unifying results and notation Constructing Higher Dimensional Perfect Factors (to appear in Aequationes Mathematicae)

Some recent work on the Prague dimension (product dimension) of graphs with a suprising connection to orthogonal latin squares can be found in Representations of graphs modulo n (with Anthony Evans and Darren Narayan, Discrete Mathematics 223 (2000) 109-123)

Garth Isaak home page