기초과학연구원 이산수학그룹
On April 25, 2022, Boram Park (박보람) from Ajou University gave a talk at the Discrete Math Seminar on the odd coloring of graphs, which is a proper coloring of a graph such that every non-isolated vertex has a color having an odd number of neighbors having that color. The title of her talk was “Odd coloring of sparse graphs“.
We introduce an odd coloring of a graph, which was introduced very recently, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to be odd if for each non-isolated vertex $x \in V (G)$ there exists a color $c$ such that $c$ is used an odd number of times in the neighborhood of $x$. The recent work on this topic will be presented, and the work is based on Eun-Kyung Cho, Ilkyoo Choi, and Hyemin Kown.
The 2nd East Asia Workshop on Extremal and Structural Graph Theory is a workshop to bring active researchers in the field of extremal and structural graph theory, especially in the East Asia such as China, Japan, and Korea.
Oct 31, 2019 (Arrival Day) – Nov 4, 2019 (Departure Day)
1st floor Diamond Hall
UTOP UBLESS Hotel, Jeju, Korea (유탑유블레스호텔제주) Address: 502 Johamhaean-ro, Jocheon-eup, Jeju, Korea (제주특별자치도 제주시 조천읍 조함해안로 502) We plan to support the accommodation for invited participants.
More speakers to be announced as soon as confirmed. Last update: September 10.
IBS Discrete Mathematics Group, Korea.
Let $S_{k,\ell}$ denote the oriented star with $k+\ell$ edges, where the center has out-degree $k$ and in-degree $\ell$. For all $k,\ell$ with $k+\ell$ large, we determine n-vertex digraphs $G$ which maximize the number of induced $S_{k,\ell}$. This extends a result of Huang (2014) for all $S_{k,0}$, and a result of Hladký, Král’ and Norin for $S_{1,1}$. Joint work with Jie Ma, Sergey Norin, and Hehui Wu.
Recently, Liu, Pach, and Sándor [arXiv:1811.05200] proved that for a polynomial $p(z)\in \mathbb{Z}[z]$, any $2$-coloring of $\mathbb{N}$ has infinitely many monochromatic solutions of the equatoin $x+y=p(z)$ if and only if $2\mid p(0)p(1)$. We improve their result in a quantitative way. We prove that if $p(z)$ has degree $d \neq 3$ and $2\mid p(0)p(1)$, then any $2$-coloring of $[n]=\{1,\dots, n\}$ contains at least $n^{2/d^2 -o(1)}$ monochromatic solutions. This is sharp as there exists a coloring of $[n]$ with $O(n^{2/d^2})$ monochromatic solutions. Our method also gives some bound for the case when $d=3$, but it is not sharp. We also prove that if $2\mid p(0)p(1)$, then the interval $[n, p(\lceil \frac{p(n)}{2} \rceil)]$ contains at least one monochromatic solution of $x+y=p(z)$. This is sharp up to multiplicative constant at most two as one can color $[n, \frac{1}{2}p(\lceil \frac{p(n)}{2} \rceil)-1]$ with no monochromatic solutions. Joint work with Hong Liu and Péter Pál Pach.
A graph family $\mathcal{F}$ is said to have the Erdős-Pósa property if there is a function $f$ such that for every graph $G$ and an integer $k$, either $G$ contains $k$ disjoint copies of graphs in $\mathcal{F}$, or it has a vertex set of size at most $f(k)$ that hits all copies of graphs in $\mathcal{F}$. This name is motivated from the Erdős-Pósa theorem (1965) which says that the set of cycles has the Erdős-Pósa property. In this talk, we survey on progress of finding various graph families that have the Erdős-Pósa property, and would like to pose interesting open problems.
We answer two extremal questions about odd cycles that naturally arise in the study of sparse pseudorandom graphs. Let $\Gamma$ be an $(n,d,\lambda)$-graph, i.e., $n$-vertex, $d$-regular graphs with all nontrivial eigenvalues in the interval $[-\lambda,\lambda]$. Krivelevich, Lee, and Sudakov conjectured that, whenever $\lambda^{2k-1}\ll d^{2k}/n$, every subgraph $G$ of $\Gamma$ with $(1/2+o(1))e(\Gamma)$ edges contains an odd cycle $C_{2k+1}$. Aigner-Horev, Hàn, and the third author proved a weaker statment by allowing an extra polylogarithmic factor in the assumption $\lambda^{2k-1}\ll d^{2k}/n$, but we completely remove it and hence settle the conjecture. This also generalises Sudakov, Szabo, and Vu’s Turán-type theorem for triangles. Secondly, we obtain a Ramsey multiplicity result for odd cycles. Namely, in the same range of parameters, we prove that every 2-edge-colouring of $\Gamma$ contains at least $(1-o(1))2^{-2k}d^{2k+1}$ monochromatic copies of $C_{2k+1}$. Both results are asymptotically best possible by Alon and Kahale’s construction of $C_{2k+1}$-free pseudorandom graphs. Joint work with Sören Berger, Mathias Schacht.
A closed curve in the Freudenthal compactification $|G|$ of an infinite locally finite graph $G$ is called a Hamiltonian curve if it meets every vertex of $G$ exactly once (and hence it meets every end at least once). We prove that $|G|$ has a Hamiltonian curve if and only if every finite vertex set of $G$ is contained in a cycle of $G$. We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette’s conjecture (that every finite planar cubic 3-connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3-connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3-connected bipartite graph with a nowhere-zero 3-flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7-ended planar cubic 3-connected bipartite graphs that do not have a Hamiltonian curve. Joint work with André Kündgen and Carsten Thomassen.
We study degree conditions for the existence of large matchings and fractional perfect matching in uniform hypergraphs. Firstly, we give some sufficient conditions for $k$-graphs to have fractional perfect matching in terms of minimum degree. Secondly, we prove that for integers $k,l,n$ with $k\ge 3$, $k/2<l<k$, and $n$ large, if $H$ is a $k$-uniform hypergraph on $n$ vertices and $\delta_{l}(H)>{n-l\choose k-l}-{(n-l)-(\lceil n/k \rceil-2)\choose 2}$, then $H$ has a matching covering all but a constant number of vertices. When $l=k-2$ and $k\ge 5$, such a matching is near perfect and our bound on $\delta_l(H)$ is best possible. When $k=3$, with the help of an absorbing lemma of Hàn, Person, and Schacht, our proof also implies that $H$ has a perfect matching, a result proved by Kühn, Osthus, and Treglown and, independently, of Kahn. Joint work with Xingxing Yu and Xiaofan Yuan.
Let $t$ be an integer such that $t\geq 2$. Let $K_{2,t}^{(3)}$ denote the triple system consisting of the $2t$ triples $\{a,x_i,y_i\}$, $\{b,x_i,y_i\}$ for $ 1 \le i \le t$, where the elements $a, b, x_1, x_2, \ldots, x_t,$ $y_1, y_2, \ldots, y_t$ are all distinct. Let $ex(n,K_{2,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2,t}^{(3)}$. This function was studied by Mubayi and Verstraëte, where the special case $t=2$ was a problem of Erdős that was studied by various authors. Mubayi and Verstraëte proved that $ex(n,K_{2,t}^{(3)})<t^4\binom{n}{2}$ and that for infinitely many $n$, $ex(n,K_{2,t}^{(3)})\geq \frac{2t-1}{3} \binom{n}{2}$. These bounds together with a standard argument show that $g(t):=\lim_{n\to \infty} ex(n,K_{2,t}^{(3)})/\binom{n}{2}$ exists and that \[\frac{2t-1}{3}\leq g(t)\leq t^4.\] Addressing a 15 year old question of Mubayi and Verstraëte on the growth rate of $g(t)$, we prove that as $t \to \infty$, \[g(t) = \Theta(t^{1+o(1)}).\] Joint work with Beka Ergemlidze and Tao Jiang.
Let $P$ be a point set on the plane with $|P| \geq 4$ in a general position (i.e., no three points lie on the same straight line). A geometric quadrangulation $Q$ on $P$ is a geometric plane graph (i.e., every edge is a straight segment) such that the outer cycle of $Q$ coincides with the boundary of the convex hull ${\rm Conv}(P)$ of $P$ and that each finite face of $Q$ is quadrilateral. We say that $P$ is quadrangulatable if $P$ admits a geometric quadrangulation. It is easy to see that if $P$ has an even number of points on the boundary of ${\rm Conv}(P)$, then $P$ is quadrangulatable. Suppose that $P$ is $k$-colored for $k \geq 2$, and that no two consecutive points on the boundary of ${\rm Conv}(P)$ have the same color. Let us consider whether $P$ is quadrangulatable with no edge joining two points with the same color. Then we see that $P$ is not necessarily quadrangulatable. Hence, introducing Steiner points $S$ for $P$, which are ones put in the interior of ${\rm Conv}(P)$ as we like, we consider whether $P \cup S$ is quadrangulatable. Intuitively, for any $k$-colored $P$, adding sufficiently large Steiner points $S$, we wonder if $P \cup S$ is quadrangulatable. However, we surprisingly see that it is impossible when $k=3$ (Alvarez et al., 2007). In my talk, we summarize these researches on quadrangulatability of point sets with Steiner points, and describe a relation with coloring of topological quadrangulations (Alvarez and Nakamoto, 2012 and Kato et al., 2014). Moreover, we describe a recent progress on a similar topic on quadrangulatability of a polygon with Steiner points.
A triangulation (resp., a quadrangulation) on a surface $S$ is a map of a graph (possibly with multiple edges and loops) on $S$ with each face bounded by a closed walk of length $3$ (resp., $4$). In this talk, we focus on the relationship between triangulations and quadrangulations on a surface. (I) An extension of a graph $G$ is the construction of a new graph by adding edges to some pairs of vertices in $G$. It is easy to see that every quadrangulation $G$ on any surface can be extended to a triangulation by adding a diagonal to each face of $G$. If we require the resulting triangulation to have more properties, the problem might be difficult and interesting. Our two main results are as follows. Every quadrangulation on any surface can be extended to an even (i.e. Eulerian) triangulation. Furthermore, we give the explicit formula for the number of distinct even triangulations extended from a given quadrangulation on a surface. These completely solves the problem raised by Zhang and He (2005). (II) It is easy to see that every loopless triangulation $G$ on any surface has a quadrangulation as a spanning subgraph of $G$. As well as (I), if we require the resulting quadrangulation to have more properties, the problem might be difficult and interesting. Kündgen and Thomassen (2017) proved that every loopless even triangulation $G$ on the torus has a spanning nonbipartite quadrangulation, and that if $G$ has sufficiently large face width, then $G$ also has a bipartite one. We prove that a loopless even triangulation $G$ on the torus has a spanning bipartite quadrangulation if and only if $G$ does not have $K_7$ as a subgraph. This talk is based on the papers (2015, 2019, 2019). Joint work with Atsuhiro Nakamoto and Kenta Ozeki.
An orientation of an (undirected) graph $G$ is an assignment of directions to each edge of $G$. An orientation with certain properties has much attracted because of its applications, such as a list-coloring, and Tutte’s $3$-flow conjecture. In this talk, we consider an orientation such that the out-degree of each vertex is contained in a given list. For an orientation $O$ of $G$ and a vertex $v$, we denote by $d_O^+(v)$ the out-degree of $v$ in the digraph $G$ with respect to the orientation $O$. Recall that the number of outgoing edges is the out-degree. We denote by $\mathbb{N}$ the set of natural numbers (including $0$). For a graph $G$ and a mapping $L: V(G)\rightarrow 2^{\mathbb{N}}$, an orientation $O$ of $G$ such that \[d_O^+(v) \in L(v)\] for each vertex $v$ is called an $L$-orientation. In this talk, we pose the following conjecture. Conjecture. Let $G$ be a graph and let $L: V(G) \rightarrow 2^{\mathbb{N}}$ be a mapping. If \[|L(v)| \ \geq \ \frac{1}{2}\Big(d_G(v) +3\Big)\]for each vertex $v$, then $G$ has an $L$-orientation. I will explain some results related to Conjecture; the best possibility if it is true, and partial solutions for bipartite graphs. However, it is open even for complete graphs. This talk is based on the paper https://doi.org/10.1002/jgt.22498. Joint work with S. Akbari, M. Dalirrooyfard, K.Ehsani, and R. Sherkati.
A star $k$-coloring of a graph $G$ is a proper (vertex) $k$-coloring of $G$ such that the vertices on a path of length three receive at least three colors. Given a graph $G$, its star chromatic number, denoted $\chi_s(G)$, is the minimum integer $k$ for which $G$ admits a star $k$-coloring. Studying star coloring of sparse graphs is an active area of research, especially in terms of the maximum average degree $\mathrm{mad}(G)$ of a graph $G$. It is known that for a graph $G$, if $\mathrm{mad}(G)<\frac{8}{3}$, then $\chi_s(G)\leq 6$ (Kündgen and Timmons, 2010), and if $\mathrm{mad}(G)< \frac{18}{7}$ and its girth is at least 6, then $\chi_s(G)\le 5$ (Bu et al., 2009). We improve both results by showing that for a graph $G$ with $\mathrm{mad}(G)\le \frac{8}{3}$, then $\chi_s(G)\le 5$. As an immediate corollary, we obtain that a planar graph with girth at least 8 has a star 5-coloring, improving the best known girth condition for a planar graph to have a star 5-coloring (Kündgen and Timmons, 2010 and Timmons, 2008). Joint work with Ilkyoo Choi.
Given a positive integer $n$ and an $r$-uniform hypergraph $H$, the Turán number $ex(n, H)$ is the maximum number of edges in an $H$-free $r$-uniform hypergraph on $n$ vertices. The Turán density of $H$ is defined as \[\pi(H)=\lim_{n\rightarrow\infty} { ex(n,H) \over {n \choose r } }.\] The Lagrangian density of an $r$-uniform graph $H$ is \[\pi_{\lambda}(H)=\sup \{r! \lambda(G):G\;\text{is}\;H\text{-free}\},\] where $\lambda(G)$ is the Lagrangian of $G$. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. The Lagrangian density of an $r$-uniform hypergraph $H$ is the same as the Turán density of the extension of $H$. Therefore, these two densities of $H$ equal if every pair of vertices of $H$ is contained in an edge. For example, to determine the Lagrangian density of $K_4^{3}$ is equivalent to determine the Turán density of $K_4^{3}$. For an $r$-uniform graph $H$ on $t$ vertices, it is clear that $\pi_{\lambda}(H)\ge r!\lambda{(K_{t-1}^r)}$, where $K_{t-1}^r$ is the complete $r$-uniform graph on $t-1$ vertices. We say that an $r$-uniform hypergraph $H$ on $t$ vertices is $\lambda$-perfect if $\pi_{\lambda}(H)= r!\lambda{(K_{t-1}^r)}$. A result of Motzkin and Straus implies that all graphs are $\lambda$-perfect. It is interesting to explore what kind of hypergraphs are $\lambda$-perfect. We present some open problems and recent results.
For a graph $H$ and an integer $k\ge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4 $ vertices. For odd cycles, Bondy and Erdős in 1973 conjectured that for all $k\ge1$ and $n\ge2$, $R_k(C_{2n+1})=n\cdot 2^k+1$. Recently, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson (2017). Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings. Joint work with Yaojun Chen and Fangfang Zhang.
Chvátal conjectured in 1973 that all graphs with sufficiently high toughness are Hamiltonian. The conjecture remains open, but it is known to be true for various classes of graphs, including chordal graphs, claw-free graphs or planar graphs. We will discuss the case of chordal graphs and outline our proof that 10-tough chordal graphs are Hamiltonian, relying on a hypergraph version of Hall’s Theorem as our main tool. This improves a previous result due to Chen et al. (1998) where the constant $10$ is replaced by $18$. Joint work with Adam Kabela.
Let $\textrm{conn}(G)$ and $\textrm{tough}(G)$ denote the connectivity and the toughness of $G$. We know that low connectivity implies low toughness; if $\textrm{conn}(G)\leq k$, then $\textrm{tough}(G) \leq k/2$. On the other hand, we also know the converse is not true. We can construct a graph with high connectivity and low toughness. About this, we have next proposition. Proposition 1. Let $G$ be a graph, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. If $G$ is $k$-connected and $K_{1,\lfloor r \rfloor +1}$-free, then $\textrm{tough}(G)\geq k/r$. It means high connectivity implies high toughness under the star-free condition. Our purpose is to prove assertions which can be regarded as a converse of this statement; that is say, we ask what we can say about $\mathcal H$ if high connectivity implies high toughness in the family of $\mathcal H$-free graphs. About this question, Ota and Sueiro (2013) proved the following theorem. Theorem 1 (Ota and Sueiro). Let $H$ be a connected graph and $\tau$ be a real number with $0<\tau\leq 1/2$. Almost all $H$-free connected graphs $G$ satisfy $\textrm{tough}(G)\geq \tau$ if and only if $K_{1,\lfloor 1/\tau \rfloor +1}$ contains $H$ as an induced subgraph. Our main result is high connectivity versions of this theorem. We proved the following theorems. Theorem 2. Let $H$ be a connected graph, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. Almost all $H$-free $k$-connected graphs $G$ satisfy $\textrm{tough}(G)\geq k/r$ if and only if $K_{1,\lfloor 1/\tau \rfloor +1}$ contains $H$ as an induced subgraph. Theorem 3. Let $\mathcal H=\{H_1,H_2\}$ be a family of connected graphs, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. Almost all $\mathcal H$-free $k$-connected graphs $G$ satisfy $\textrm{tough}(G)\geq k/r$ if and only if $K_{1,\lfloor 1/\tau \rfloor +1}$ contains one of $H$ as an induced subgraph.
A $d$-defective colouring of a graph $G$ is a colouring of the vertices of $G$ such that each vertex $v$ has at most $d$ neighbours coloured the same colour as $v$. We say $G$ is $d$-defective $k$-choosable if for any $k$-assignment $L$ of $G$, there exists a $d$-defective $L$-colouring, i.e., a $d$-defective colouring $f$ with $f(v) \in L(v)$ for each vertex $v$. It was proved by Eaton and Hull (1999) and Škrekovski (1999) that every planar graph is $2$-defective $3$-choosable, and proved by Cushing and Kierstead (2010) that every planar graph is $1$-defective $4$-choosable. In other words, for a planar graph $G$, for any $3$-assigment $L$ of $G$, there is a subgraph $H$ with $\Delta(H) \le 2$ such that $G-E(H)$ is $L$-colourable; and for any $4$-list assignment $L$ of $G$, there is a subgraph $H$ with $\Delta(H) \le 1$ such that $G-E(H)$ is $L$-colourable. An interesting problem is whether there is a subgraph $H$ with $\Delta(H) \le 2$ such that $G-E(H)$ is $3$-choosable, and whether there is a subgraph $H$ with $\Delta(H) \le 1$ such that $G-E(H)$ is $4$-choosable. It turns out that the answer to the first question is negative and the answer to the second question is positive. Kim, Kim and I proved that there is a planar graph $G$ such that for any subgraph $H$ with $\Delta(H)=3$, $G-E(H)$ is not $3$-choosable. Grytczuk and I proved that every planar graph $G$ has a matching $M$ such that $G-M$ has Alon-Tarsi number at most $4$, and hence is $4$-choosable. The late result also implies that every planar graph is $1$-defective $4$-paintable. For a subset $X$ of $V(G)$, let $f_X$ be the function defined as $f_X(v)=4$ for $v \in X$ and $f_X(v)=5$ for $v \in V(G)-X$. Our proof also shows that every planar graph $G$ has a subset $X$ of size $|X| \ge |V(G)|/2$ such that $G$ is $f_X$-AT, which implies that $G$ is $f_X$-choosable and also $f_X$-paintable. In this talk, we shall present the proof and discuss possible strengthening of this result.
DIMAG had its first workshop “2019-1 IBS Workshop on Graph Theory” on February 11 and 12, 2019. There were 6 invited talks — Jeong Han Kim (KIAS), Cory T. Palmer (Univ. of Montana), Martin Balko (Charles Univ.), Dong Yeap Kang (KAIST), Boram Park (Ajou Univ.), and Dániel Gerbner (Alfréd Rényi Institute of Mathematics). We would like to thank all speakers and participants.
The talks are recorded but due to technical problems, only four talks are available online.
1:30pm-2:20pm Jeong Han Kim: Entropy and sorting
2:20pm-3:10pm Cory T. Palmer: Generalized Turán problems – Berge hypergraphs
Coffee Break
4:00pm-4:50pm Martin Balko: Ramsey numbers of edge-ordered graphs
4:50pm-5:40pm Dong Yeap Kang: On the rational Turán exponents conjecture
Banquet
9:30am-10:20am Boram Park: Sum-free set problem on integers
Coffee Break
11:00am-11:50am Dániel Gerbner: Generalized Turán problems – counting subgraphs
Lunch
We plan to provide meals to all participants and provide a room at a near-by hotel for invited speakers and selected participants. Please register in the following form below by January 28, Monday; please register early if you want to receive the support for the accommodation.
We reconsider the old problem of sorting under partial information, and give polynomial time algorithms for the following tasks: (1) Given a partial order P, find (adaptively) a sequence of comparisons (questions of the form, “is x < y?”) which sorts ( i.e., finds an unknown linear extension of) P using O(log(e(P))) comparisons in worst case (where e(P) is the number of linear extensions of P). (2) Compute (on line) answers to any comparison algorithm for sorting a partial order P which force the algorithm to use Ω(log(e(P))) comparisons. (3) Given a partial order P of size n, estimate e(P) to within a factor exponential in n. (We give upper and lower bounds which differ by the factor $n^n /n!$.) Our approach, based on entropy of the comparability graph of P and convex minimization via the ellipsoid method, is completely different from earlier attempts to deal with these questions.
Joint work with J. Kahn.
Let $F$ be a graph. We say that a hypergraph $H$ is a Berge-$F$ if there is a bijection $f : E(F) \rightarrow E(H )$ such that $e \subseteq f(e)$ for every $e \in E(F)$. Note that Berge-$F$ actually denotes a class of hypergraphs. The maximum number of edges in an $n$-vertex $r$-graph with no subhypergraph isomorphic to any Berge-$F$ is denoted $\operatorname{ex}_r(n,\textrm{Berge-}F)$. Observe that when $r=2$, then a Berge-$F$ is simply the graph $F$ and thus again we! are investigating the Tur\’an function $\operatorname{ex}(n,F)$.
In this talk we will survey results on the function $\operatorname{ex}_r(n,\textrm{Berge-}F)$ for various graphs $F$. We will also describe several interesting open problems.
An edge-ordered graph is a graph with linearly ordered set of edges. We introduce and study Ramsey numbers of edge-ordered graphs, called edge-ordered Ramsey numbers. We prove some basic properties of these numbers for general edge! -ordered graphs and we provide some stronger estimates for special classes of edge-ordered graphs. We also pose some new open problems and compare edge-ordered Ramsey numbers with the standard Ramsey numbers of graphs and with ordered Ramsey numbers, which are Ramsey numbers for graphs with linearly ordered vertex sets.
Joint work with Mate Vizer.
The extremal number ${\rm ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1,2]$ is realisable if there exists a graph $F$ with ${\rm ex}(n , F) = \Theta(n^r)$. Several decades ago, Erdős and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $1,\frac{7}{5},2$, and the numbers of the form $1+\frac{1}{m}$, $2-\frac{1}{m}$, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2.
We discuss some recent progress on the conjecture of Erdős and Simonovits. First, we show that $2 – \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence.
Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.
This is joint work with Jaehoon Kim and Hong Liu.
For an abelian group $G$, a set $A \subset G$ is sum-free if there are no $x, y, z \in A$ such that $x + y = z$. Sum-free sets was initiated by Schur (1916) by an attempt to prove the famous Fermat’s Last Theorem. Since then, there have been intensive and fruitful research in the field of additive combinatorics. One of great interest in the study of sum-free sets is to consider sum-free subsets of a set of integers, which has attracted a significant attention in the literature over the years.
In this talk, some recent results on sum-free sets of integers are discussed. Then we present a result on $k$-sum $\bf{n}$-free set, where $\bf{n}$ is an $n$-dimensional integer vector. The work is based on joint work with Ilkyoo Choi and Ringi Kim.
Given two graphs $H$ and $F$, our goal is to determine the maximum number of copies of $H$ in an $F$-free graph on $n$ vertices. The systematic research of these problems was initiated (after several sporadic results) by Alon and Shikhelman. I describe several results of mine in this area, with different sets of co-authors.
Joint work with Ervin Győri, Abhishek Methuku, Cory Palmer and Mate Vizer.