2013 Spring Combinatorics Seminar
The regular time for the seminar is Thursday 3:30-4:30pm in LeConte 312.
If there is deviation, it will be mentioned at the talk.
- May 17, Friday, 11:00 am, Baogang Xu, Nanjing Normal
University China/Georgia Tech
On judicious bisection of graphs
Bollobás and Scott conjectured that every graph with
$m$ edges and minimum degree at least 2 has a
bisection $V_1, V_2$ of which each spans at most
$m/3$ edges. We confirm this conjecture, and characterize
the extremal graphs. This is a joint work with Dr. X. Yu.
- April 18, Travis Johnston
Hypergraph Jumps and the Lagrange Polynomial
Abstract: What can a multivariate polynomial with non-negative integers tell you about a hypergraph? If the polynomial is chosen in the right way, it can tell you a lot. In this talk we investigate the connection between the Lagrange Polynomial and the Hypergraph Jumps. In the talk, we will explain what a jump is, both for uniform and non-uniform hypergraphs and we motivate the construction of the Lagrange polynomial with examples. We generalize the classic Lagrange polynomial to non-uniform hypergraphs. By means of the Lagrange polynomial (and a Lemma originally due to Rodl) we prove that every real number in the interval [0, 2) is a jump for a {1,2}-graph. This is joint work with
Linyuan Lu.
- Apr 25, 2:15-3:15pm
William Cole Franks Graph Labeling with Distance
Conditions
An $L({2,1})$-labeling of a simple graph $G$ is a function $f:V(G) \rightarrow \mathbb{Z}$ such that if $xy \in E(G)$, then $|f(x) - f(y)| \geq 2$ and if the shortest path in $G$ connecting $x$ and $y$ has two edges then $|f(x) - f(y)| \geq 1$. The $L(2,1)$-labeling problem is an example of a Channel Assignment Problem, which aims to model the frequency assignment of transmitters which could interfere when near. The objective is generally to minimize the difference between the highest and lowest label used, called the span. The $L(2,1)$-labeling problem was posed by Jerrold Griggs and Roger Yeh in 1992, and they conjectured that any graph has a labelling with span no greater than the square of the maximum degree. The author will present his result that if the order of $G$ is at most $(\lfloor \Delta/2 \rfloor + 1 )(\Delta^2 - \Delta+ 1) - 1$, then $G$ has a labeling with span no greater than $\Delta^2$, where $\Delta = \Delta(G)$ is the maximum degree of the graph. This shows that for graphs no larger than the given order, the 1992 ``$\Delta^2$ Conjecture" of Griggs and Yeh holds. In addition, the author will show that there is a polynomial time algorithm to find $L(2,1)$-labelings with span and order satisfying the conditions above.
-
March 28, 2pm in LC 312.
Richard Anstee,
Applications of Linear Algebra to Forbidden Configurations.
Linear algebra is occasionally useful in proving combinatorial bounds.
Fisher's inequality for block designs is proven this way. We give some
proofs of important bounds for Forbidden Configurations using linear
algebra. A typical idea is to associate with an $n\times 1$ $(0,1)$-column
$(a_1,a_2,..,a_n)^T$ with a multilinear polynomial in $n$ variables
$x_1,x_2,..,x_n$ so that the polynomial is nonzero for $(0,1)$ inputs if and
only if $x_1=a_1, x_2=a_2$ etc. This idea has been applied to the basic
Sauer Bound (Smolensky) and also in determining whether a $k$-rowed
configuration $F$ has bound asymptotic to $m^k$ or $m^{k-1}$.
The latter is joint work with Balin Fleming.
- March 21, 3:45pm, Daniel Grier
(USC undergraduate and Goldwater Scholar),
The Difficulty of Finding Winning
Strategies for Poset Games
A poset game is a mathematical strategy game played over a partially
ordered set (poset) in which two players alternate choosing an element of the
poset, removing it and all elements greater than it. The first player unable to
select an element of the poset loses. Quick algorithms for finding the winner
of a poset game exist in certain restricted cases such as the popular game of
Nim. The complete solution for the game of Nim has been known since
1901, but there is still no algorithm for quickly solving the more general
poset game problem. In this talk, I will give a reduction showing that this
problem is almost assuredly computationally infeasible. More precisely, the
reduction shows that deciding the winner of an arbitrary finite poset game is
PSPACE-complete. The proof relies on the PSPACE-completeness of Node
Kayles, a game in which players vie to choose an independent set in a graph,
but otherwise requires no background in computational complexity.
- March 7, 2:00pm Stephen Fenner
Two-level poset games
We discuss the complexity of determining the winner of a game played on a
finite two-level partially ordered set. This is a natural question,
as Daniel Grier has shown recently that determining the winner of a
finite three-level poset game is PSPACE-complete. We give a simple
formula allowing one to compute the status of a type of two-level
poset game that we call, "parity-uniform." This class of posets
includes significantly more easily solvable two-level games than
was known previously. We also establish general equivalences
between various two-level games. This implies that for any $n$,
only finitely many two-level posets with $n$ minimal elements
need be considered. We have a similar result for posets with
$n$ maximal elements.
This is joint work with Rohit Gurjar (IIT Kanpur),
Arpita Korwar (IIT Kanpur), and Thomas Thierauf (U. Aalen)
- February 28, Joshua Cooper
The Spectrum of the All-Ones Hypermatrix
Spectral graph theory relates the eigenvalues of matrices
associated with graphs to properties of those graphs. Quite recently, a
few different generalizations to (uniform) hypergraphs have been
proposed. Here, we take the ''algebraic'' approach, using so-called
resultants and symmetric hyperdeterminants to define the spectrum of a
hypergraph's adjacency hypermatrix. In this talk, I will introduce the
basic framework and then discuss recent results describing the spectrum
of the all-ones hypermatrix, a surprisingly difficult task. This
description includes a complete explanation of the eigenvalues'
multiplicities, a so-far elusive aspect of the spectral theory of
tensors. We also give a general distributional picture of the spectrum
as a point-set in the complex plane and discuss possible implications
for the spectrum of the complete hypergraph, about which there are a
number of interesting questions. Joint work with Aaron Dutle of USC.
-
February 21, 2:00pm
Richard Anstee:
Forbidden Families of Configurations
We consider the problem of forbidden configurations. Define a matrix to be simple if it is a
$(0,1)$-matrix with no repeated columns. For a given $ (0,1)$-matrix $F$, we say a matrix $A$
has no configuration $F$ if there is no submatrix of $A$ which is a row and column permutation
of $F$. Given $m$ and a family of forbidden configurations, we seek a bound on the number
of columns in an $m$-rowed simple matrix which has no configuration in the family.
There is an attractive, unresolved conjecture of Anstee and Sali which predicts the asymptotics
of the bound when forbidding a single configuration $F$. We consider some interesting cases
involving forbidding a (finite) family of forbidden configurations. Some cases have bounds
predicted by the conjecture and some do not. This is joint work with Christina Koch,
Miguel Raggi and Attila Sali.
- February 7
Aaron Dutle Joint Degree Matrices
The Joint Degree Matrix of a graph $G$ is a matrix whose $(i,j)$ entry records the number of edges
connecting vertices of degree $i$ to vertices of degree $j$ in $G$. In this talk, we discuss the joint degree
matrix model. Particularly, we address the following questions: When can a matrix be realized as a joint
degree matrix of a graph? When a matrix can be realized, is there a simple way to move between
different realizations? Will there be cookies?
- January 31, 2pm:
Richard Anstee, UBC Mathematics
Forbidden Submatrices
The problem considered is an ordered version of the typical forbidden configuration problem in extremal set theory. I find it convenient to use matrices to encode sets. A matrix is called simple if it is a $(0,1)$-matrix with no repeated columns. For an $m$-rowed simple matrix $A$, we can think of $A$ as an incidence matrix where the columns of $A$ encode subsets of $\{1,2,...,m\}$.
Let $F$ be a given $k$-rowed $(0,1)$-matrix. We define $Avoids(m,F)=\{m$-rowed simple matrix $A : A$ has no submatrix $F\}$. With this definition we have an extremal problem: $fs(m,F)$ is the maximum, over all $A$ in $Avoids(m,F)$, of the number of columns in $A$. It is conjectured by A, Frankl, Füredi and Pach that for a $k$-rowed $F$, $fs(m,F)$ is $m^k$. We indicate a few results (with Ronnie Chen and Ron Estrin) and some ideas from amortized complexity.
Seminars in past semesters:
Fall 2012
Spring 2009
Fall 2008
Spring 2008
Fall 2007
Spring 2007
Fall 2006
Spring 2006
Fall 2005