|
¡à Previous Seminars(2016)
January 14 (Thu), 2016
Lyu, Hanbaek (Ohio State University)
Synchronization of finite-state pulse-coupled oscillators on various graphs
| Abstract : | The emergence of synchronization among a population of coupled oscillators is a pervasive nonlinear phenomenon in nature, and have been extensively studied in many areas with broad applications. While most traditional models such as Kuramoto's or Peskin's for oscillator synchronization assume continuous-time and continuous-space so that the study of which often uses techniques of smooth dynamics, we propose a novel generalized cellular automaton (GCA) model for discretetime pulse-coupled oscillators and study the emergence of synchrony. Our discrete model brings the study of coupled oscillators into the realm of combinatorics.
Given a finite simple graph and an integer $n_3$, each vertex is an identical oscillatorof period n with the following weak coupling along the edges: each oscillatorinhibits its phase update if it has at least one neighboring oscillator at a particular¡±blinking¡± state and if its state is ahead of this blinking state. We obtain conditionson initial configurations and on network topologies for which states of allvertices eventually synchronize. For finite graphs, we show that our GCA modelsynchronizes arbitrary initial configurations on paths, trees, and, with random perturbation,any connected graph. In particular, one main result is the following local-global principle for tree networks: for $n \in \{3,4,5,6\}$, any $n$-periodic network on a tree synchronizes arbitrary initial configuration if and only if the maximumdegree of the tree is less than the period $n$.
For infinite graphs, we study our discrete dynamics on the integer lattice ${\mathbb Z}^d$ using probabilistic methods. For $d=1$, our model is related to annihilating particle systems and random walks, and by this connection, we show that starting with uniform product measure, the probability of not having synchrony on a finite fixed interval at time $t$ decays to zero in the order of $O(t^{-1/2+o(1)})$. For $d \ge 2$, our model shows spiraling autowave behavior, and hence non-synchrony, in resemblance of the famous BelousovZhabotinsky reaction, for $n \neq 4$. While this behavior is common to similar models for excitable medium, the four-color model is critical and characteristic to our model: we seem to have clustering on ${\mathbb Z}^d$ through a complex wave process, regardless of dimension. This may be thought of as a four-state Ising spin system with deterministic dynamics, with convergence toward global ferromagnetism.
If time allows, we also discuss an asynchronous and continuous-state generalization of our GCA model. Despite being continuous model, we can prove similar synchronization theorems for trees and combining with a distributed spanning tree algorithm, we obtain a distributed self-stabilizing algorithm for clock synchronizationin a system of processors with identical local clocks on any graph with $v$ nodesand diameter $d$, which runs in $O(d+\sqrt{v} log^* v)$ time. |
February 16 (Tue), 2016
Se-jin Oh (University of Oregon)
Commutation classes of symmetric groups and combinatorial objects related to them (Lecture I,II,III)
| Abstract : | In this talk, I would like to start with the notion of commutation classes of elements in symmetric groups which also appears in the
representation theory of quantum groups. By considering "the adapted class", we can find interesting relationship between
the adapted class and the Young composition (and its tableaux). The relationship is quite easy and interesting but not well-known.
If time permits, I would like to tell some problems which looks interesting. |
-
March 10 (Thu), 11 (Fri) 2016
Sun-Young Nam (KIAS)
Combinatorics of Schur P- and Schur Q-functions
| Abstract : | The study of Schur P- and Schur Q-functions has attracted researchers in algebraic combinatorics
since they have a well established combinatorial theory of shifted tableaux parallel to that of ordinary tableaux related
with Schur functions. In this talk, we first introduce the classical theory of ordinary tableaux and Schur functions briefly.
And then we introduce the theory of shifted tableaux and Schur P-, Q-functions as a shifted analogue of the classical case.
As applications, we give combinatorial interpretations of well-known properties associated with Schur P-, Q-functions.
This talk is based on joint works with Seung-Il Choi and Young-Tak Oh. |
-
March 24 (Thu), 2016
Kang-Ju Lee (Seoul National University)
Weighted Laplacians and weighted tree-numbers of matroid complexes
| Abstract : | We prove that the spectra of the weighted Laplacians of matroid complexes are polynomials in the weights of ground set elements, generalizing the result by Kook, Reiner, and Stanton that the spectra of the combinatorial Laplacians of matroid complexes are integers. This generalization provides a simple proof for the orthogonal decomposition of the chain groups of matroid complexes which is finer than the eigenspace decomposition for the combinatorial Laplacians. Using the result for the weighted Laplacians, we give a new formula for the weighted high-dimensional tree-numbers of matroid complexes in terms of matroid invariants: the $\alpha$-invariant (the unsigned reduced Euler characteristic) and Crapo's $\beta$-invariant. To derive the formula, we develop a weighted analogue of high-dimensional Temperley's formula which gives relations among the determinants of the weighted Laplacians, the weighted tree-numbers, and the weights of the vertices. In addition, we present applications of our results to several matroid complexes. This is a joint work with Woong Kook.
|
-
April 14 (Thu), 2016
Zhi Qiao (University of Science and Technology of China)
On distance-regular graphs with valency $k$ and smallest eigenvalue relatively close to $-k$
| Abstract : | For any fixed real number $0<\alpha<1$ and fixed diameter $D\geq 3$, we show that there are only finitely many non-bipartite distance-regular graphs with diameter $D$, such that its smallest eigenvalue $\theta_D$ is not more than $-\alpha k$, where $k$ is the valency of the graph.
When the diameter $D=3$, or $D=4$ and $a_1\neq 0$, we classify such graphs with $\theta_{D}\leq -k/2$, and as a consequence, the $3$-chromatic graphs are also determined, which was started by A. Blokhuis et al.
We show that the distance-regular graphs with $\theta_D=-k/2$, $a_1=1$ and $c_2\geq 4$ are the dual polar graphs $^2A_{2D-1}(2)$.
A classification of distance-regular graphs with diameter $D=4$ and $\theta_D\leq -3k/4$ is also given.
This is a joint work with Jack Koolen and Yifan Jing.
|
-
April 28 (Thu), 2016
Hyunsuk Moon (KAIST)
Real rank geometry of Ternary forms
| Abstract : | We study real ternary forms whose real rank equals the generic complex rank and their algebraic boundaries. And also we characterize the semi-algebraic set of sum of powers representations with that rank. This talk will be mostly about ternary forms of degree 2 to 6. This is a joint work with Mateusz Michalek, Bernd Sturmfels, and Emanuele Ventura.
|
-
May 12 (Thu), 2016
Gary Greaves (Tohoku University)
On equiangular lines and regular graphs
| Abstract : | Given some dimension d, what is the maximum number of lines in Rd such that the angle between any pair of lines is constant? (Such a system of lines is called "equiangular".) This classical problem was initiated by Haantjes in 1948 in the context of elliptic geometry. In 1966, Van Lint and Seidel showed that graphs could be used to study equiangular line systems.
Recently this area has enjoyed a renewed interest due to the current attention the quantum information community is giving to its complex analogue. I will give an introduction to the area and report on some new developments in the theory of equiangular lines in Euclidean space. Among other things, I will present a relationship between large sets of equiangular lines and regular graphs with few distinct eigenvalues.
|
-
May 27 (Fri), 2016
Hana Kim (NIMS)
Enumeration of ordered trees and related Riordan matrices
| Abstract : | An ordered tree is a rooted tree where the order of the subtrees of a vertex is significant. Some structured matrices called Riordan matrices often arise in enumeration problems concerning certain classes of ordered trees. In this talk, we introduce two kinds of profiles of ordered trees and show how such enumeration and Riordan matrices are related by several examples. Some bijective arguments will also be introduced briefly.
|
-
Jun 9 (Thu), 2016
Seung Il Choi (Seoul National University)
On a bijective proof of the Aperin weight conjecture for $S_n$ when $p=2$
| Abstract : | This talk explains the Alperin's weight conjecture for the symmetric group $S_n$. The Alperin's weight conjecture states that the number of conjugacy classes of weights of $G$ and a field of prime characteristic $p$ is equal to the number of simple $FG$-modules.
In 2011, J. Cossey provided a bijection between the set of conjugacy classes of $p$-weights for $S_n$ and a certain explicit set $\Gamma_0(n)$.
On the other hand, Brauer showed that the number of simple $FG$-modules is equal to the number of $p$-regular classes in $G$. The purpose of this talk is to present a bijective proof the Alperin's weight conjecture for the symmetric group when $p=2$. More precise, it gives an explicit bijection between the set $\Gamma_0(n)$ and the set of $2$-regular partitions of $n$.
|
-
Jun 23 (Thu), 2016
Ilkyoo Choi (KAIST)
Improper colorings of graphs on surfaces
| Abstract : | A graph is $(d_1, ... , d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, ... , V_r$ where the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i$ in ${1, ... , r}$.
Given $r$ and $d_1, ... , d_r$, determining if a (sparse) graph is $(d_1, ... , d_r)$-colorable has attracted much interest.
For example, the Four Color Theorem states that all planar graphs are $4$-colorable, and therefore $(0, 0, 0, 0)$-colorable.
The question is also well studied for partitioning planar graphs into three parts.
For two parts, it is known that for given $d_1$ and $d_2$, there exists a planar graph that is not $(d_1, d_2)$-colorable.
Therefore, it is natural to study the question for planar graphs with girth conditions.
Namely, given $d_1$ and $d_2$, determine the minimum $g=g(d_1, d_2)$ such that planar graphs with girth at least $g$ are $(d_1, d_2)$-colorable.
We continue the study and ask the same question for graphs that are embeddable on a fixed surface.
Given integers $k, y, g$ we completely characterize the smallest $k$-tuple $(d_1, ... , d_k)$ in lexicographical order such that each graph of girth at least $g \ge 7$ that is embeddable on a surface of Euler genus $y$ is $(d_1, ... , d_k)$-colorable.
All of our results are tight, up to a constant multiplicative factor for the degrees $d_i$ depending on $g$.
In particular, we show that a graph embeddable on a surface of Euler genus $y$ is $(0, 0, 0, K_1(y))$-colorable and $(2, 2, K_2(y))$-colorable, where $K_1(y)$ and $K_2(y)$ are linear functions in $y$.
This talk is based on results and discussions with H. Choi, F. Dross, L. Esperet, J. Jeong, M. Montassier, P. Ochem, A. Raspaud, and G. Suh.
|
-
Jul 14 (Thu), 2016
Hyonju Yu (POSTECH)
On Hoffman graphs
| Abstract : | In this talk, we consider (regular) graphs with smallest eigenvalue less than $-2$. We are going to give infinitely many examples of (non-isomorphic) connected $k$-regular graphs with smallest eigenvalue in half open interval $[-1-\sqrt2, -2)$ and also infinitely many examples of (non-isomorphic) connected $k$-regular graphs with smallest eigenvalue in half open interval $[\alpha_1, -1-\sqrt2)$ where $\alpha_1$ is the smallest root$(\approx -2.4812)$ of the polynomial $x^3+2x^2-2x-2$. From these results, we can determine the largest and second largest limit points of smallest eigenvalues of regular graphs less than $-2$.
|
-
Aug 11 (Thu), 2016
Kyoung-Tark Kim (Shanghai Jiao Tong University)
Harmonic Index Designs in the Binary Hamming Schemes
| Abstract : | This talk is an introduction of our recent (ongoing) research on harmonic index designs in
the binary Hamming schemes.
(Joint work with Ei. Bannai, Et. Bannai, T. Ikuta, Y. Zhu)
This work is based on the addition formula of commutative association schemes.
I first introduce some addition formulae arising from different fields and then observe that
we can also establish an "addition formula" in any commutative association schemes.
Our study is parallel to our previous research on harmonic index designs on the unit spheres.
Thus I will talk how to use this "addition formula" for studying harmonic index designs in the binary Hamming schemes.
This talk requires no preparatory knowledge for addition formula or association schemes.
(Especially, I will provide a full proof of classical addition formula for Gegenbauer polynomials.)
|
-
Aug 18 (Thu), 2016
Jaehoon Kim (University of Birmingham)
Packing bounded degree graphs
| Abstract : |
We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs.
For instance, our results imply the following. Let $G$ be a quasi-random $n$-vertex graph and suppose $H_1,\dots,H_s$ are bounded
degree $n$-vertex graphs with $\sum_{i=1}^{s} e(H_i) \leq (1-o(1)) e(G)$. Then $H_1,\dots,H_s$ can be packed edge-disjointly into $G$.
We provide a more general version of the above approximate decomposition
result which can be applied to super-regular graphs and thus can be combined with Szemeredi's regularity lemma. In particular our result can be viewed as an extension of the classical blow-up lemma of Komlos, Sarkozy and Szemeredi to the setting of approximate decompositions.
By using this method, we prove the tree packing conjecture of Gyarfas and Lehel for bounded degree trees.
This talk is based on results with Felix Joos, Daniela Kuhn, Deryk Osthus and Mykhaylo Tyomkyn.
|
-
Sep 8 (Thu), 2016
Byung Hee An (Institute for Basic Science)
$f$-vectors of Gelfand-Cetlin polytopes
| Abstract : | We provide the differential equations on the generating functions for $f$-vectors of Gelfand-Cetlin polytopes.
|
-
Sep 22 (Thu), 2016
Younjin Kim (Ewha Womans University)
Problems in Extremal Combinatorics
| Abstract : | Extremal Combinatorics aims to determine or estimate the maximum or minimum possible cardinality of a collection of finite objects (sets, graphs, numbers, vectors, etc.) that satisfy certain requirements. In this talk, I will prove Erdos-Shelah's Conjecture (1972) by using the probabilistic method.
|
-
Oct 14 (Fri), 2016
Ji-Hwan Jung (Sungkyunkwan University)
$d$-orthogonal polynomials of Sheffer type
| Abstract : |
Let $\mathcal{P}$ be a vector space of polynomials over the complex
field $\mathbb{C}$ and let $\mathcal{P}^*$ be its algebraic dual
i.e., the set of all linear functionals
$u:\mathcal{P}\rightarrow\mathbb{C}$. We denote $u(y)$ for
$y\in\mathcal{P}$ by $<u,y>$. Let $\{P_n\}_{n\ge0}$ be a
sequence of monic polynomials $P_n\in\mathcal{P}$ of degree $n$. For
a positive integer $d$, the sequence
$\{P_n\}_{n\ge0}\subset\mathcal{P}$ is $d$-orthogonal
if there exists a $d$-dimensional vector of linear functionals, $\mathcal{U}%
=(u_0,\ldots,u_{d-1})^T$, such that
\begin{align*}
<u_k,P_rP_n>=0 \;\;\;\;\;\;\;\;\; \mathrm{if}\;\; r>nd+k,\;\;n\in\mathbb{N}=\{0,1,2,\ldots\} \\
<u_k,P_nP_{nd+k}>\neq0 \;\; \mathrm{if} \;\;n\in\mathbb{N} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;
\end{align*}
for each integer $k\in\{0,1,\ldots,d-1\}$. A $d$-orthogonal
polynomial sequence $\{P_n\}_{n\ge0}$ is called of Sheffer type for
$(g,f)$ if there exist a pair of functions $g(z)$ and $f(z)$ where
$g(0)\neq0$, $f(0) = 0$ and $f^{\prime}(0)\neq0$ such that
\begin{align*}
g(t)e^{xf(t)}=\sum_{n\ge0}S_{n} (x){\frac{z^{n}}{n!}}.
\end{align*}
In this talk, we consider $d$-orthogonal polynomial sequences
$\{P_n(x)\}_{n\ge0}$ of Sheffer type. Specifically, we discuss that
(i) a necessary and sufficient condition to be a Sheffer type;
(ii) the zeros of $\{P_n(x)\}_{n\ge0}$;
(iii) the equivalence relation on the set of Sheffer polynomial sequences.
|
-
Oct 27 (Thu), 2016
Suil O (Sungkyunkwan University)
Interlacing families and the Hermitian spectral norm of digraphs
| Abstract : |
Recently, Marcus, Spielman, and Srivastava proved the existence of infinite families
of bipartite Ramanujan graphs of every degree at least $3$ by using the method of interlacing families
of polynomials. In this talk, we apply their method to prove that for any connected graph $G$,
there exists an orientation of $G$ such that the spectral radius of the corresponding Hermitian adjacency
matrix is at most that of the universal cover of $G$.
|
-
Nov 17 (Thu), 2016
Thomas J. Perrett (Technical University of Denmark)
Graph Polynomials and the Density of their Roots
| Abstract : |
Over 100 years ago, the chromatic polynomial was introduced with the aim of showing that planar graphs are $4$-colourable. Indeed, the four-colour theorem is equivalent to the statement that the number $4$ is never a root of a chromatic polynomial of a planar graph. Whilst the four-colour theorem has been proved, our knowledge about the roots of the chromatic polynomials of planar graphs remains incomplete. In this talk we discuss recent results showing that the set of such roots contains a dense subset of the interval $(3,4)$, except possibly for a small region around $\tau +2$, where $\tau$ is the golden ratio. The significance of $\tau + 2$ arises due to a beautiful theorem of Tutte, to which our result can be seen as a partial converse. We also discuss density results for other classes of graphs, and other graph polynomials.
|
-
Dec 8 (Thu), 2016
Alexander Gavrilyuk (University of Science and Technology of China)
On a characterization of the Grassmann graphs
| Abstract : |
The Grassmann graph $J_q(n,d)$, $n\geq 2d$, is a graph (of diameter $d$) defined on the set of
$d$-dimensional subspaces of an $n$-dimensional vector space over the finite field $\mathbb{F}_q$,
with two subspaces being adjacent if their intersection has dimension $d-1$.
In 1995, Metsch showed that a distance-regular graph with the same intersection array
as $J_q(n,d)$ is isomorphic to $J_q(n,d)$ unless $n=2d$, $n=2d+1$, ($n=2d+2$ if $q\in \{2,3\}$),
or ($n=2d+3$ if $q=2$).
In 2005, Van Dam and Koolen constructed the twisted Grassmann graphs,
a family of distance-regular graphs with the same intersection array as $J_q(2d+1,d)$,
but not isomorphic to them, for all prime powers $q$ and $d\ge 2$.
In this talk, we will discuss a characterization of the Grassmann graphs in some of the open cases.
This is joint work with Jack Koolen.
|
-
Dec 15 (Thu), 2016
Meesue Yoo (Sungkyunkwan University)
Elliptic combinatorics
| Abstract : |
In this talk, we introduce elliptic analogues of numbers and factorial of numbers
by utilizing certain elliptic weight functions. As applications, we construct
elliptic analogues of the rook numbers and file numbers by attaching elliptic weights to the cells in a board.
We show that our elliptic rook and file numbers satisfy elliptic extensions of corresponding factorization theorems
which in the classical case was established by Goldman, Joichi and White and by Garsia and Remmel
in the file number case. This factorization theorem can be used to define elliptic analogues of various
kinds of Stirling numbers of the first and second kind, and Abel numbers. We also give analogous
results for matchings of graphs, elliptically extending the result of Haglund and Remmel.
|
-
Dec 23 (Fri), 2016
Hong Liu (Univ. of Warwick)
Komlos' conjecture on Hamiltonian subsets
| Abstract : |
I will present embedding strategies using a novel combination of blow-up method and sparse robust expander. As application, it leads to recent resolution of a conjecture of Komlos in 1981 on Hamiltonian subsets.
|
-
Mar 24 (Fri), 2017
Song, Joungmin (GIST)
Characteristic polynomials of hyperplane arrangements through graph theory
| Abstract : |
We use graph theoretical method to compute the characteristic polynomial of hyperplane arrangement $\mathcal J_n$ consisting of affine planes of the form
$x_i+x_j = 1, x_k=0, x_l = 1$ for $1\leq i,j,k,l \leq n.$
|
¡Ø Note : You can check an abstract by click on the title of talk.
|