Counting Cliques in Graphs with Forbidden Subdivision

来源 :第八届工业与应用数学国际大会 | 被引量 : 0次 | 上传用户：sujie0888

【摘要】

：

　　We prove that for all positive integers t,every n-vertex graph with no Kt-subdivision has at most 294tn cliques.We also prove that asymptotically,such graph

【作者】

：

Oum Sang-il

【机构】

：

KAIST

【出处】

：

第八届工业与应用数学国际大会

【发表日期】

：

2015年8期

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

　　We prove that for all positive integers t,every n-vertex graph with no Kt-subdivision has at most 294tn cliques.We also prove that asymptotically,such graphs contain at most 2(5+o(1))tn cliques,where o(1)tends to zero as t tends to infinity.This strongly answers a question of D.Wood asking if the number of cliques in n-vertex graphs with no Kt-minor is at most 2ctn for some constant c.

其他文献

A Variational Approach to Thin Film Hydrodynamics of Binary Mixtures

　　In order to model the dynamics of thin films of mixtures,solutions,and suspensions,a thermodynamically consistent formulation is needed such that various co

会议

Wellposedness of Compressible Elastodynamics

　　This talk is devoted to the study on the wellposedness issue of compressible elastodynamics.

会议

Decoupled Energy Stable Schemes for Vesicle Membrane Phase Field Model

　　We present numerical approximations of phase-field vesicle membrane models.We first reformulate the model derived from an energetic variational formulation

会议

Global Regularity to the Navier-Stokes Equations for A Class of Large Initial Data

　　We prove that for initial data of the form u∈0(x)=(vh 0(x∈),∈-1v3 0(x∈)T,x∈=(xh,∈x3)T,the Cauchy problem of the incompressible Navier-Stokes equations

会议

Evolution of interfaces driven by anisotropic laws

　　The minisymposium presents the state of art of rigorous analysis and numerical simulations of interfacial motions.We have in mind problems,where diffusion o

会议

Measure Valued Solutions to the Boltzmann Equation

　　Some recent results on the existence,regularity and large time behavior for the Boltzmann equation with measure valued initial data will be presented.

会议

Continuous Coupling of Kinetic and Aeroacoustic Models

　　We investigate the simulation of the acoustic near and far field of a turbulent flow through a thin porous medium.Within the porous medium and the turbulenc

会议

Nonlinear Acoustic Wave Propagation in A Rarefied Gas:Numerical Analysis Based on Kinetic and Fluid

　　Nonlinear acoustic waves caused by an infinitely wide plate oscillating in its normal direction and propagating into a semi-infinite expanse of a rarefied g

会议

A Hierarchy of Hybrid Numerical Methods for the Boltzmann Equation

　　In this work in collaboration with F.Filbet,we construct a hierarchy of hybrid numerical methods for the Boltzmann equation,based on moment realizability.We

会议

Decomposition of Sparse Graphs into Foreststhe Nine Dragon Tree Conjecture for k ≤ 2

　　The fractional arboricity Arb(G)is the maximum of |E(H)|/|V(H)|-1 over all subgraphs H with at least two vertices.Generalizing the Nash-Williams Arboricity

会议

Counting Cliques in Graphs with Forbidden Subdivision

其他学术论文