기초과학연구원 이산수학그룹
A graph or graph property is $\ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $\ell$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each $\ell\in\mathbb N$, there is an integer $n=n(\ell)$ such that every graph with at least $n$ vertices is $\ell$-reconstructible. We show that for …
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\H{o}s in 1973 conjectured that …
For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $p\geq e(H)$, denoted by $t_H(W)$. One may then define corresponding functionals $\|W\|_{H}:=|t_H(W)|^{1/e(H)}$ and $\|W\|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $\|.\|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $\|.\|_{r(H)}$ is …
Given a cardinal $\lambda$, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$, and a $\lambda$-covering of $G$ is a family of spanning trees covering $E(G)$.We show that if a graph admits a $\lambda$-packing and a $\lambda$-covering then the graph also admits a decomposition into $\lambda$ many spanning …
On page 335 in his lost notebook, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities under three different interpretations for the double series, and showed that they are intimately connected with the classical circle and divisor problems in number theory. …
It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is …
Let $F$ be a graph. We say that a hypergraph $\mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $\mathcal H$ such that for all $xy \in E(F)$, $f(xy) \cap V(F) = \{x,y\}$. In this talk, we show asymptotics for the maximum number of …
Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb {R}$. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for …
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of …
Given any integers $s,t\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of …