# 20130126 の変更点

Top / 20130126

* Hakata Workshop 2013 [#z008da3b]
''～ Combinatrics and its Applications～''

#br
This is a satellite seminar of [[the 11th Japan-Korea Workshop on Algebra and Combinatorics :http://comb.math.kyushu-u.ac.jp/?20130124]].
Our purpose of this meeting is giving an opportunity to make a speech and
to commuticate with reserchers who study verious fields not only Combinatorics.

Further information is available from the organizers below.

**Organizers [#xb11a6e1]

-[[Yoshihiro Mizoguchi:http://imi.kyushu-u.ac.jp/~ym/]] (Kyushu University),~
-Hayato Waki (Kyushu University),~
-Mitsugu Hirasaka (Pusan National University),~
-[[Tetsuji Taniguchi:http://researchmap.jp/tetsuzit-14/]] (Matsue College of Technology),~
-Osamu Shimabukuro (Sojo University)
-[[Laboratory of Advanced Software in Mathematics, Institute of Mathematics for Industry, Kyushu University:http://www.imi.kyushu-u.ac.jp/eng/academic_staffs/department/34]]

**Supported by [#l7bc435b]

-[[Global COE Program "Education and Research Hub for Mathematics-for-Industry":http://gcoe-mi.jp/]]

**Date [#i35500dd]
-January 26, 2013. 9:30-18:00

-Seminar Room I (2F) in Reference Eki Higashi Building.
1-16-14 Hakata-Eki-Higashi, Hakata-Ku, Fukuoka City, 812-0013

**Program [#h6d29d6d]
***January 26 (Saturday) at Room I in Reference Eki Higashi Building. [#s883cdcb]
-9:25--9:30 Opening (Tetsuji Taniguchi)
-9:30--10:05 [[Akihiro Munemasa (Tohoku University)>#pa19cf13]]
--Complex Hadamard matrices contained in a Bose-Mesner algebra
-10:20--10:55 [[Michael Dobbins (GAIA, Postech)>#ze9edc62]]
--Reducing combinatorial to projective equivalence in realizability problems for polytopes.
-11:10--11:45 [[Aleksandar Jurišić (University of Ljubljana)>#q728cf69]]
--TOWER GRAPHS AND EXTENDED GENERALIZED QUADRANGLES
-12:00--13:00 break
-13:00--15:00  Poster Session
--[[List of Speakers>#cfb76d77]]
-15:15--16:15 [[Xiao-Dong Zhang (Shanghai Jiao Tong University)>#wec50930]]
--The algebraic connectivity of graphs
-16:30--17:05 [[Katsuhiro Ota (Keio University)>#mb37f86c]]
--Clique minors, chromatic numbers for degree sequences
-17:10--17:45 [[Yota Otachi (JAIST)>#h17d65f1]]
--The path-distance-width of hypercubes
-17:45--18:00 Closing (Yoshihiro Mizoguchi)
-18:00-- Post-meeting party

**List of Poster session speakers [#cfb76d77]
*** 「[[数学ソフトウェア紹介:http://imi.kyushu-u.ac.jp/~waki/lams/]]」([[Introduction to Mathematical Software:http://imi.kyushu-u.ac.jp/~waki/lams/]]) [#pee66f42]
+久保 浩平(九州大学理学部物理学科), プログラム名: 正規圧縮距離を用いたクラスタリング
+島袋 修(崇城大学 工学部), プログラム名: フュージョンスキームの探索
+野崎 寛(愛知教育大学), プログラム名: Magmaによる極大2距離集合の分類(Classification of maximal 2-distance sets by  Magma)
+松下昂平(九州大学大学院数理学府), プログラム名: アフィン写像を用いた補間による2次元アニメーション作成ソフトウェア
+鹿間 章宏(大阪大学大学院 情報科学研究科), プログラム名: トーリックイデアルの二次生成判定法
+照本 直敏(九州大学数理学府), プログラム名: Q-det
+喜友名 朝也(九州大学大学院数理学府), プログラム名: PARI/GPによるE_8 lattice の部分集合の生成
+谷口哲至(松江高専数理科学科), プログラム名: スターコンプリメントテクニックと最小固有値が－２以上のグラフの生成
+ダハン グザヴィエ(ＧＣＯＥ-ＭＩ), プログラム名: MAGMAによるRamanujan graphチェッカー
+古川 貴司(九州大学大学院数理学府), プログラム名: SSD Problem
+高妻倫太郎(立命館アジア太平洋大学), プログラム名: Truffe（トリュフ）
+秦攀(九州大学 マス・フォア・インダストリ研究所), プログラム名: 非線形時系列に対するモデル推定と選択のソフト

**Abstract [#sb7c7865]

***Akihiro Munemasa (Tohoku University) [#pa19cf13]
-Title:Complex Hadamard matrices contained in a Bose-Mesner algebra
-Abstract:

A complex Hadamard matrix &mimetex(H); is an n by n matrix with complex entries
with absolute value 1, such that rows are pairwise orthogonal
with respect to the hermitian inner product. Recently,
the adjacency matrix of the line graph of the Petersen graph.
We found another such matrix, and then generalized
it to an infinite family. In this talk, we focus on how to
set up a system of polynomial equations for solving this kind
of problem more efficiently than the naive approach. This is
achieved by determining the ideal of the 3-dimensional
algebraic variety consisting of the points of the form
&mimetex("(x+1/x,y+1/y,z+1/z,x/y+y/x,y/z+z/y,z/x+x/z)");
in the 6-dimensional space.
This is a joint work with Takuya Ikuta.

***Michael Dobbins (GAIA, Postech) [#ze9edc62]
-Title:Reducing combinatorial to projective equivalence in realizability problems for polytopes.
-Abstract:

Determining if there is a polytope of any combinatorial type that
satisfies some given property is made difficult by the fact that there
are polytopes with realization spaces that are homotopic to any
primary semialgebraic set. I will show how, for certain properties,
this can be reduced to finding such realizations among projective
equivalence classes of polytopes, which are much nicer spaces. An
application of this answers a question posed by Bernt Lindström in
1971, that there does exist a polytope without an antiprism.

***Aleksandar Jurišić (University of Ljubljana) [#q728cf69]
-Title:TOWER GRAPHS AND EXTENDED GENERALIZED QUADRANGLES
-Abstract:

Let &mimetex(\Gamma); be a complete multipartite graph with at least two parts
and each part of size at least &mimetex(2);. For example, &mimetex("K_{t\times n}");,i.e., the complement of &mimetex(t); copies of &mimetex(K_n);, and &mimetex("t,n \ge 2");. Then the local graphs and the &mimetex(\mu);-graphs (that is the graphs induced on the common neighbours of two vertices at distance &mimetex(2);) are again complete multipartite. They are actually the same graphs, in our example &mimetex("K_{(t-1)\times n}");. If &mimetex("t\ge 3");, then the geodesic closure ofany &mimetex(\mu);-graph is the graph we started with.
Let now &mimetex(\Gamma); be the point graph of a generalized quadrangle GQ&mimetex("(s,t)");. Then &mimetex(\Gamma); is strongly regular like the complete multipartite graph (its valency is &mimetex(s(t+1));, while the number of triangles on an edge in (a) &mimetex(\Gamma); is &mimetex(s-1);, and (b) the complement of &mimetex(\Gamma); is &mimetex(t+1);). Its &mimetex(\mu);-graphs are &mimetex("K_{1\times (t+1)}"); and when the generalized quadrangle is regular, the convex closures of &mimetex(\mu);-graphs are &mimetex("K_{2\times (t+1)}");.
We study a family of graphs, denoted by &mimetex({\cal F});, with the following
properties

(i) their &mimetex(\mu);-graphs are complete multipartite,

(ii) there exist adjacent vertices &mimetex(x);, &mimetex(y); and a vertex &mimetex(z); at distance &mimetex(2); from both &mimetex(x);, &mimetex(y); in &mimetex(\Gamma);, and the number &mimetex("\alpha_\G=\alpha(x,y,z)");of common neighbours of these vertices does not depend on a choice of such a triple.

This is a generalization of the study of extended generalized quadrangles
in it is intimately connected with even more general study of locally
strongly regular graphs.
We report on our progress of the classification of the family &mimetex({\cal F});.

***Xiao-Dong Zhang (Shanghai Jiao Tong University) [#wec50930]
-Title:[[The algebraic connectivity of graphs:http://comb.math.kyushu-u.ac.jp/?plugin=attach&pcmd=open&file=Xiao-Dong_Zhang.pdf&refer=20130126]]
-Abstract:

Let &mimetex(G); be a simple graph of order &mimetex(n); and
&mimetex( L(G)=D(G)-A(G) ); be its Laplacian matrix, where &mimetex( D(G)); and &mimetex( A(G) ); are the degree diagonal  and adjacency matrices, respectively.
The the second smallest  eigenvalue of &mimetex( L(G) ); is called the algebraic connectivity of &mimetex(G.);
In this talk, we survey some new results and progress on the algebraic connectivity.
In particular, we present some relationships between the algebraic
connectivity and the graph parameters, such as the   clique number,
the matching number, the independence number, the isoperimetric
number, etc.

***Katsuhiro Ota (Keio University) [#mb37f86c]
-Title:Clique minors, chromatic numbers for degree sequences
-Title:[[Clique minors, chromatic numbers for degree sequences:http://comb.math.kyushu-u.ac.jp/?plugin=attach&pcmd=open&file=Ota.pdf&refer=20130126]]
-Abstract:

For a given graph &mimetex(G);, let &mimetex(\chi(G)); and &mimetex(h(G)); denote
the chromatic number, and the maximum size of clique minors of &mimetex(G);,
respectively.
The well-known Hadwiger's conjecture (1943) states that
&mimetex(\chi(G)\le h(G)); holds for every graph &mimetex(G);, which is wide open
for the graphs with &mimetex(\chi(G)\ge 7);.
In 2005, Robertson posed the "Hadwiger's conjecture for degree sequences."
For a graphical degree sequence &mimetex(D);, let &mimetex(\chi(D)); and &mimetex(h(D));
denote the maximum &mimetex(\chi(G)); and &mimetex(h(G));, respectively,
among the graphs &mimetex(G); having degree sequence &mimetex(D);.
Robertson's conjecture states that &mimetex(\chi(D)\le h(D)); for any degree
sequence &mimetex(D);.
This conjecture was recently confirmed by Dvo&#x159;&aacute;k and Mohar
by showing strongly that &mimetex(\chi(D)\le h'(D));, where
&mimetex(h'(D)); is the maximum size of topological clique minors of graphs
having degree sequence &mimetex(D);.
In this talk, we give an alternative and very short proof of
Robertson's conjecture.
Also, we shall discuss the values of &mimetex(\chi(D));, &mimetex(h(D)); and &mimetex(h'(D));
for some &mimetex(D);.
These results are based on a joint work with Guantao Chen and Ryo Hazama.

***Yota Otachi (JAIST) [#h17d65f1]
-Title: The path-distance-width of hypercubes
-Title: [[The path-distance-width of hypercubes:http://comb.math.kyushu-u.ac.jp/?plugin=attach&pcmd=open&file=Otachi.pdf&refer=20130126]]
-Abstract:

The path-distance-width of a connected graph &mimetex(G); is the minimum
integer &mimetex(w); satisfying
that there is a nonempty subset of &mimetex(S \subseteq V(G)); such that the
number of the vertices
with distance &mimetex(i); from &mimetex(S); is at most &mimetex(w); for any nonnegative integer &mimetex(i);.
We present a general lower bound on the path-distance-width of graph,
and determine the path-distance-width of hypercubes by using the lower bound.
We also discuss the applicability of the lower bound to other graphs.