Speaker: Yubo Zou, USC.
Title: Decycling Cartesian Product of Cycles
Abstract: The decycling number ∇(G) of a graph G is the smallest number of vertices which can be removed from G so that the resultant graph contains no cycles. The family of graphs which we consider is the Cartesian product of two cycles, sometimes called a toroidal grid. In this talk, the results on the decycling number of Cartesian product of two cycles, Cm \Box Cn, for all m and n will be presented.
Speaker: Jerry Griggs, USC.
Title: Minimum Span Real Number Graph Labellings with Separation Conditions
Abstract: In 1988 Roberts described a problem posed to him by Lanfear concerning the efficient assignment of channels to a network of transmitters in the plane. To understand this problem, Griggs and Yeh introduced the theory of integer vertex λ-labellings of a graph G. To prevent interference, labels for nearby vertices must be separated by specified amounts ki depending on the distance i, 1 ≤ i ≤ p. One seeks the minimum span of such a labelling. The p=2 case with k1=2 and k2=1 has attracted the most attention, particularly the tantalizing conjecture that if G has maximum degree Δ ≥ 2, then the minimum span is at most Δ2.
In order to gain more insights for general ki, it is natural to expand the model to allow real number labels and separations, as well as infinite graphs with Δ < ∞. Griggs and Jin showed that in this case there is a labelling of minimum span in which all of the labels have the form Σi=1p ai ki, where the ai's are integers ≥ 0. Moreover, they conjectured that the minimum span as a function of the separations ki is piecewise linear with finitely many pieces.
Babilon et al. introduced λ-graphs, in which every edge has weight ki for some i, where reals k1,...,kp ≥ 0 are fixed. This is a more general model, which better describes the interference restrictions for an irregular transmitter network in the plane. Král' proved the Piecewise Linearity Conjecture in this more general setting. Networks used in practice often correspond to regular infinite lattices in the plane, and with two levels of interference, the λ-labelling model with p=2 is appropriate. Griggs and Jin determined the minimum span of such labellings for general k1, k2 for the square and hexagonal lattices. They also solved the triangular lattice for k1 ≥ k2, and Král' and Skoda recently completed the remaining cases when k1 < k2.
This lecture is intended as an overview of this labelling project, with an emphasis on directions for future research.
Speaker: Yubo Zou, USC.
Title: Decycling Fibonacci Cubes
Abstract: The decycling number ∇(G) of a graph G is the smallest number of vertices that can be deleted from G so that the resultant graph contains no cycle. In this talk, a brief review of decycling problem will be given, and results on the decycling number of Fibonacci cubes will be presented.
Speaker: Daniel Gerbner, Eotvos Lorand University, currently visiting USC.
Title: Profile vectors in the lattice of subspaces
Abstract: The profile vector f(U) in Rn+1 of a family U of subspaces of an n-dimensional vector space V over GF(q) is a vector of which the i-th coordinate is the number of subspaces of dimension i in the family U (i=0,1,...,n). In this paper, we determine the profile polytope of intersecting families (the convex hull of the profile vectors of all intersecting families of subspaces).
Joint work with Balazs Patkos.
Speaker: Gyula O. H. Katona, Alfred Renyi Institute of Mathematics, currently visiting USC.
Title: Forbidden inclusion patterns in families of subsets
Abstract: Let [n]={ 1,2,...,n} be a finite set, families F of its subsets will be investigated. An old theorem of Sperner (1928) says that if there is no inclusion (F∈F, G∈ F, F≠ G then F ⊄ G) then the largest family under this condition is the one containing all ⌊n/2⌋ -element subsets of [n]. We will consider its certain generalizations in the present lecture. They are useful in proving theorems in number theory. geometry, etc. Again, the maximum size of F is to be found under the condition that a certain configuration is excluded. The configuration here is always described by inclusions. More formally, let P be a poset. The maximum size of a family F ⊂ 2[n] which does not contain P as a (non-necessarily induced) subposet is denoted by La(n,P).
If P consist of two comparable elements, then Sperner's theorem gives the answer, the maximum is (n choose ⌊n/2⌋).
In most cases, however La(n,P) is only asymptotically determined in the sense that the main term is the size of the largest level (sets of size ⌊n/2⌋) while the second term is c/n} times the second largest level where the lower and upper estimates contain different constants c.
Let the poset N consist of 4 elements illustrated here with 4 distinct sets satisfying A⊂ B, C⊂ B, C⊂ D. We were not able to determine La(n,N) for a long time.
Recently, a new method jointly developed by J.R. Griggs, helped us to prove the following theorem.
Theorem (n choose ⌊n/2⌋) ( 1 + 1/n + Ω(1/n2)) \leq La(n,N) ≤ (n choose ⌊n/2⌋(1 + 2/n + O(1/n2)). Other examples of the application of the method (for other small posets) are also shown.
Speaker: Lincoln Lu, University of South Carolina
Title: Explicit construction of small Folkman graphs
Abstract: A Folkman graph is a K4-free graph G such that if the edges of G are 2-colored then there exists a monochromatic triangle. Erdos offered a prize on proving the existence of a Folkman graph with at most 1 million vertices. In this paper, we construct several ``small'' Folkman graphs within this limit. In particular, there exists a Folkman graph on 9697 vertices.
Speaker: Darren Narayan, University of South Carolina
Title: Maximum Minimal k-Rankings of Graphs
Abstract: A k-ranking of a graph G is a labeling of the vertices using integers 1, 2, ., k such that whenever we have two vertices with the same label, every path between these vertices contains a vertex with a higher label. A k-ranking is minimal if reducing any label violates the described ranking property. The rank number of a graph is the minimum k such that G has a minimal k-ranking. The arank number of a graph is the maximum k that can appear in a minimal k-ranking. We present new results involving the rank and arank numbers, including a surprising result linking the two.
Speaker: Josh Cooper, University of South Carolina
Title: Discrete Stochastic Differentiation
Abstract:Suppose that a random walker on a vertex-weighted graph chooses neighboring vertices at each step with probabilities in proportion to those vertices' weights. If the walker is started at a "source" vertex, and stops when she reaches a "sink" vertex, one may ask, what is the expected number of visits (i.e., occupation times) to each vertex? The answer is simple to derive from standard Markov Chain theory, but the inverse question, which we term "discrete stochastic differentiation" (DSD) is apparently wide open: given a graph with designated source and sink, for which vectors of occupation times is it possible to find a corresponding weighting of the vertices of G? How does one find it if it exists? We state a natural conjecture and several results about DSD. We also discuss a few promising applications to machine learning and educational psychology.
Speaker: Eva Czabarka, University of South Carolina
Title: Minor crossing number and crossing number of graphs
Abstract: mcr(G), the minor crossing number of a graph G, is the minimal crossing number over all graphs that contain G as a minor. There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection width method and the embedding method. We have adapted all three methods to the minor crossing number, and showed that for the string crossing number i(G), i(G) ≤ 4 mcr(G), and mcr(G) ≤ i(G)+|E(G)|-|V(G)|+t(G), where t(G) is the number of tree components of G. Our results imply for the n-dimensional hypercube Qn that mcr(Qn)= Ω (4^n/n). This is joint work with Drago Bokal, Laszlo Szekely and Imrich Vrto.