GICW 2020

  • Date: November 27, 2020

  • Venue: online (zoom link provided via email)

  • Host: Hankuk University of Foreign Studies (HUFS)

  • Organizers:

  • Support: National Research Foundation of Korea (NRF)

  • Contact: ilkyoo [at] hufs [dot] ac [dot] kr


  • Fee: Free!

  • Deadline: November 25, 2020

  • Registration form: link

Plenary speaker:

  • Ringi Kim (Inha Univ.)

Invited speakers:

  • Eun-Kyung Cho (HUFS)

  • JiSun Huh (Ajou Univ.)

  • Minho Song (Sungkyunkwan Univ.)

  • Sang-Hoon Yu (Seoul National Univ.)


  • 1:15 - 1:30 Opening address and setup check

  • 1:30 - 2:20 Plenary talk

      • Ringi Kim, "On the strong clique number of a graph"

The strong clique number of a graph is the maximum size of a set of edges of which every pair has distance at most two. As a weakening of the renowned strong edge coloring conjecture, Faudree et al. proposed the conjecture that every graph $G$ has strong clique number at most $5/4\Delta(G)^2$. There have been a lot of work on this conjecture, but it still remains open. The best known upper bound is $4/3\Delta(G)^2$ by Faron et al. In this talk, we will discuss on variations of this conjecture (e.g. the Ore-degree version of the conjecture and the upper bound of the strong clique number of graphs with forbidden cycles), and then I will present our recent results. This is joint work with Eun-Kyung Cho, Ilkyoo Choi, and Boram Park.

    • 2:20 - 2:40 Coffee Break

    • 2:40 - 3:40 Invited talks

      • JiSun Huh, "Results on simultaneous bar-core related partitions"

In this talk, we study the relationship between bar-core partitions, core shifted Young diagrams, doubled distinct partitions, and self-conjugate core partitions. In particular, we give lattice path interpretations for these $(s,t)$ and $(s,s+d,s+2d)$ bar-core related partitions. We also deduce the number, the largest size, and the average size of some simultaneous bar-core related partitions. This talk is based on a joint work with Hyunsoo Cho, Hayan Nam, and Jaebum Sohn.

      • Minho Song, "Riordan group theory and connected bipartite non-crossing graphs"

A Riordan matrix $(g(z),f(z))$ is an infinite lower triangular array determined by a pair of formal power series $g,f\in{\mathbb{R}}[[z]]$ in which its $k$th column has the generating function $g(z)f(z)^k$ where $k\in \mathbb{N}_0$, $g(0)\ne0$, $f(0)=0$ and $f^\prime (0)\ne0$. A geometric graph on a finite set $\cS\subset\R^2$ of points is a graph with vertex set $\cS$ whose edges are straight-line segments with endpoints in $\cS$. In this talk, we introduce a way of counting the number of connected bipartite non-crossing graphs via Riordan group theory. With a simple observation, we derive the production matrix of connected bipartite non-crossing graphs, which was an open problem. This allow us to have the asymptotic growth of the number of graphs.

  • 3:40 - 4:00 Group Photo

    • 4:00 - 5:00 Invited talks

      • Sang-Hoon Yu, "Rotor-routing action on spanning trees and harmonic cycle"

In this talk, we investigate the relation between the harmonic cycles of a two dimensional complex and the critical group of its underlying graph. The harmonic space of a cell complex is defined to be the kernel of the combinatorial Laplacian and is naturally isomorphic to the homology group by combinatorial Hodge theory. The critical group of a graph is a finite abelian group which is related to the chip-firing game and has the cardinality equal to the number of spanning trees. For two-dimensional cell complexes obtained by adding an additional edge to an acyclization of a graph, Kim and Kook found a combinatorial formula for the generator of one-dimensional harmonic space over real coefficients, using spanning trees of the given graph. We introduce the refined version of the formula for an integral generator, by tracking the trace of a chip in the action of the critical group on spanning trees.

      • Eun-Kyung Cho, "Improvements on Hippchen's Conjecture"

Let $G$ be a $k$-connected graph on $n$ vertices. Hippchen's Conjecture states that two longest paths in $G$ share at least $k$ vertices. Guti\'errez recently proved the conjecture when $k\leq 4$ or $k\geq \frac{n-2}{3}$. We improve upon both results; namely, we show that two longest paths in $G$ share at least $k$ vertices when $k=5$ or $k\geq \frac{n+2}{5}$. This completely resolves two conjectures of Guti\'errez in the affirmative. This talk is based on joint work with Ilkyoo Choi and Boram Park.