Department of Mathematics & Statistics Georgia State University
Please email comments or suggestions to Yi Zhao at matyxz@langate.gsu.edu
Friday, March 28,
A Family of
4-Critical Graphs with Diameter Three
Lucas van der Merwe,
Let $\gamma_t(G)$ denote the total domination number of the graph $G$. $G$ is said to be total domination edge critical, or simply $\gamma_t$-critical, if $\gamma_t(G+e)<\gamma_t(G)$ for each edge $e\in E(\overline{G}) $. In this paper we study a family $\cal H$ of $4$-critical graphs with diameter three, in which every vertex is a diametrical vertex, and every diametrical pair dominates the graph. We also generalize the self-complementary graphs, and show that these graphs provide a special case of the family $\cal H$.
Joint work with Marc Loizeaux and Francesco Barioli.
March 21, Friday, 2:30-3:30, Room 796 (colloquium)
The Furedi-Hajnal
and Stanley-Wilf Conjectures
Adam Marcus, Georgia Institute of Technology
Almost (perhaps over) 20 years ago, the following question started to appear
(in numerous forms) in the literature: given a fixed permutation $\pi$ of
length $k$, how many permutations of length $n$ avoid $\pi$? By
"avoid" we
mean that there is no order preserving mapping f s.t.
$f(\pi(i)) \leq
f(\pi(j))$ whenever $\pi(i) \leq
\pi(j)$ for all $i,j \in \pi$.
In the late 90's, a rather bold conjecture surfaced, independently from Richard
Stanley and Herb Wilf, that the correct answer is $c^n$ for some $c = c(\pi)$.
Since then, a number of attempts had been made, and the conjecture was proved
for certain subsets of permutations, but by the turn of the century, progress
had stalled. Conferences began to be organized and books written in an
attempt
to focus efforts on this now notorious problem.
In this talk, I will give a proof of this conjecture, by way of the
F\"uredi-Hajnal conjecture, a question about
pattern avoidance in
{0,1}-matrices. The proofs are surprisingly (or
perhaps "refreshingly",
depending on who you ask) simple - they use nothing more than basic counting,
pigeonhole, and induction. The talk will be accessible to anyone (including
undergraduates and even advanced high-schoolers) with
even a basic knowledge of
combinatorics. For this reason, I would like to
extend a special invitation to
anyone who is interested in the field of combinatorics
(or mathematics in
general) but who wouldn't normally attend a research seminar for fear that the
material would be too advanced. On the other hand, I hope to see advanced
students and faculty there as well, as this will serve as a gentle reminder
that hard problems don't necessarily require hard solutions.
Monday, March 10,
Long cycles in 3-connected graphs
Guantao Chen, GSU
The study of the longest cycles of
sparse graphs evolved from development of the Four Color Theorem. In 1931,
Whitney proved that every 4-connected planar triangulation contains a
The length of the longest cycle in
G, denoted by $c(G)$, is called the circumference of
G. When studying paths in polytopes, Moon and Moser
in 1963 conjectured that {\it $c(G) \geq \alpha n^{\log_32}$ for all 3-connected planar graph of
order $n$, where $\alpha >0$ is a universal constant.} They also showed the
bound $n^{\log_32}$ is best possible. Ten years later,
Gr\"{u}nbaum
and Walther made the same conjecture for 3-connected {\bf cubic} planar graphs.
Recently,
working on graph minors, Thomas
made the following conjecture: There exist two functions $\alpha(t)$ and
$\beta(t)>0$ such that, for any integer $t \ge 3$
and for any $3$-connected graph $G$ with no $K_{3,t}$-minor, $c(G)\ge \alpha(t) n^{\beta (t)}$. Furthermore, Seymour and
Thomas conjectured that $\beta(t)$ in the Thomas
conjecture can be a constant independently from $t$. In this talk, we will
report the solutions of these conjectures and the progress thus far for the
following conjecture of Jackson and Wormald: there
exists a function $\alpha(d)>0$ such that $c(G) \geq \alpha(d)n^{\log_{d-1}2}$ for any positive integer $d\ge 4$ and any 3-connected graph $G$ with maximum degree at
most $d$
Spectrally arbitrary tree sign pattern matrices
A sign pattern (matrix) is a
matrix whose entries are from the set {+, -, 0}. A sign pattern matrix A is a
spectrally arbitrary pattern (SAP) if for every monic
real
polynomial p(x) of degree n there exists a real matrix B whose entries agree in
sign with A such that the characteristic polynomial of B is p(x). All 3 by 3 SAP's, as well as tree sign patterns with star graphs that
are SAP's, have already been characterized. We
investigate tridiagonal sign patterns of order 4. All
irreducible tridiagonal SAP's
are identified. Necessary and sufficient conditions for an irreducible tridiagonal pattern to be an SAP are found. Some new
techniques, such as innovative applications of Grobner
bases for demonstrating that a sign pattern is not potentially nilpotent, are
introduced. Some properties of sign patterns that allow every
possible inertia are established.
This is joint work with M. Arav, F. Hall and K. Kaphle.
Some Connections between Boolean and
Nonnegative Sign pattern Matrices
Frank Hall, GSU
A nonnegative sign pattern matrix is a matrix whose entries come from the set
{+, 0}. A nonnegative sign pattern matrix can also be viewed as a Boolean
matrix, by replacing each + entry with 1. In this talk, some interesting
connections between nonnegative sign pattern matrices and Boolean matrices are
investigated. In particular, the relations between the minimum rank and
the Boolean row (or column) rank are explored; the idempotent Boolean matrices
that allow idempotence are identified; and the
nonnegative sign pattern matrices that allow various types of nonnegative (or
positive) generalized inverses are characterized.
Link to Discrete Math Seminars in fall 2007
organized by Guantao
Chen.