A class of graphs admits an adjacency labeling scheme of size $f(n)$, if the vertices of any $n$-vertex graph $G$ in the class can be assigned binary strings (aka labels) of length $f(n)$ so that the adjacency between each pair of vertices in $G$ can be determined only from their labels. The Implicit Graph Conjecture (IGC) claimed that any graph class which is hereditary (i.e. closed under taking induced subgraphs) and factorial (i.e. containing $2^{\Theta(n \log n)}$ graphs on $n$ vertices) admits an adjacency labeling scheme of order optimal size $O(\log n)$. After thirty years open, the IGC was recently disproved [Hatami and Hatami, FOCS 2022]. In this work we show that the IGC does not hold even for monotone graph classes, i.e. classes closed under taking subgraphs. More specifically, we show that there are monotone factorial graph classes for which the size of any adjacency labeling scheme is $\Omega(\log^2 n)$. Moreover, this is best possible, as any monotone factorial class admits an adjacency labeling scheme of size $O(\log^2 n)$. This is a consequence of our general result that establishes tight bounds on the size of adjacency labeling schemes for monotone graph classes: for any function $f: \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ with $\log x \leq f(x) \leq x^{1-\delta}$ for some constant $\delta > 0$, that satisfies some natural conditions, there exist monotone graph classes, in which the number of $n$-vertex graphs grows as $2^{O(nf(n))}$ and that do not admit adjacency labels of size at most $f(n) \log n$. On the other hand any such class admits adjacency labels of size $O(f(n)\log n)$, which is a factor of $\log n$ away from the order optimal bound $O(f(n))$. This is the first example of tight bounds on adjacency labels for graph classes that do not admit order optimal adjacency labeling schemes.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【ACL2020】多模态信息抽取,365页ppt
专知会员服务
143+阅读 · 2020年7月6日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
4+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Arxiv
0+阅读 · 2023年12月17日
Arxiv
0+阅读 · 2023年12月16日
Arxiv
0+阅读 · 2023年12月15日
Arxiv
0+阅读 · 2023年12月14日
Arxiv
0+阅读 · 2023年12月14日
Arxiv
0+阅读 · 2023年12月13日
VIP会员
相关VIP内容
【ACL2020】多模态信息抽取,365页ppt
专知会员服务
143+阅读 · 2020年7月6日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
4+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员