We introduce and study conflict-free colourings of $t$-subsets in hypergraphs. In such colourings, one assigns colours to all subsets of vertices of cardinality $t$ such that in any hyperedge of cardinality at least $t$ there is a uniquely coloured $t$-subset. The case $t=1$, i.e., vertex conflict-free colouring, is a well-studied notion. Already the case $t=2$ (i.e., colouring pairs) seems to present a new challenge. Many of the tools used for conflict-free colouring of geometric hypergraphs rely on hereditary properties of the underlying hypergraphs. When dealing with subsets of vertices, the properties do not pass to subfamilies of subsets. Therefore, we develop new tools, which might be of independent interest. (i) For any fixed $t$, we show that the $\binom n t$ $t$-subsets in any set $P$ of $n$ points in the plane can be coloured with $O(t^2 \log^2 n)$ colours so that any axis-parallel rectangle that contains at least $t$ points of $P$ also contains a uniquely coloured $t$-subset. (ii) For a wide class of "well behaved" geometrically defined hypergraphs, we provide near tight upper bounds on their $t$-subset conflict-free chromatic number. For $t=2$ we show that for each of those "well -behaved" hypergraphs $H$, the hypergraph $H'$ obtained by taking union of two hyperedges from $H$, admits a $2$-subset conflict-free colouring with roughly the same number of colours as $H$. For example, we show that the $\binom n 2$ pairs of points in any set $P$ of $n$ points in the plane can be coloured with $O(\log n)$ colours such that for any two discs $d_1,d_2$ in the plane with $|(d_1\cup d_2)\cap P|\geq 2$ there is a uniquely (in $d_1 \cup d_2$) coloured pair. (iii) We also show that there is no general bound on the $t$-subset conflict-free chromatic number as a function of the standard conflict-free chromatic number already for $t=2$.


翻译:我们在高音中引入并研究无冲突的颜色。 在这样的颜色中, 人们将颜色指定给所有最基本值的顶端 $1 美元 。 在这种颜色中, 将颜色指定给所有最基本值的顶端 $t 美元, 这样在任何最基本值的顶端中, 至少有一个独特的颜色 $t $t 美元, 也就是说, 无冲突颜色, 是一个很好研究的概念。 案件 $t = 2美元 (比如, 彩色配对) 似乎带来了新的挑战。 许多用于不发生冲突的顶端点 $_ 美元 美元 $t 美元 美元 美元 。 当处理最基本值的顶端点时, 属性不会超过子端点的亚值 。 因此, 我们开发的新工具, 可能是独立的。 对于任何固定值 美元, 我们显示在任何固定值的底值中, $2 美元 美元 美元 美元 美元 美元 的底值 美元 。

0
下载
关闭预览

相关内容

这个新版本的工具会议系列恢复了从1989年到2012年的50个会议的传统。工具最初是“面向对象语言和系统的技术”,后来发展到包括软件技术的所有创新方面。今天许多最重要的软件概念都是在这里首次引入的。2019年TOOLS 50+1在俄罗斯喀山附近举行,以同样的创新精神、对所有与软件相关的事物的热情、科学稳健性和行业适用性的结合以及欢迎该领域所有趋势和社区的开放态度,延续了该系列。 官网链接:http://tools2019.innopolis.ru/
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
专知会员服务
25+阅读 · 2021年4月2日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
123+阅读 · 2020年9月8日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年8月20日
Arxiv
0+阅读 · 2022年8月19日
Arxiv
27+阅读 · 2020年6月19日
VIP会员
相关VIP内容
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
专知会员服务
25+阅读 · 2021年4月2日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
123+阅读 · 2020年9月8日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员