文摘
We look at colourings of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si3.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=29e9aeaa58b6408862f7dda660376369" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode">-uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si4.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=6ba3f0df561e50f0ff8dd4bcb8e513cb" title="Click to view the MathML source">Eclass="mathContainer hidden">class="mathCode"> in an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si3.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=29e9aeaa58b6408862f7dda660376369" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode">-uniform hypergraph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=5cfc4de18c40c21f0684952b644281b9" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode"> whose vertices are coloured is the partition of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si3.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=29e9aeaa58b6408862f7dda660376369" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode"> induced by the colour classes of the vertices in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si4.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=6ba3f0df561e50f0ff8dd4bcb8e513cb" title="Click to view the MathML source">Eclass="mathContainer hidden">class="mathCode">. Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode"> be a set of partitions of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si3.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=29e9aeaa58b6408862f7dda660376369" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode">. A class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">-colouring of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=5cfc4de18c40c21f0684952b644281b9" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode"> is a colouring of its vertices such that only patterns appearing in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode"> are allowed. We first show that many known hypergraph colouring problems, including Ramsey theory, can be stated in the language of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">-colourings. Then, using as our main tools the notions of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">-colourings and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">-hypergraphs, we define and prove a result on tight colourings, which is a strengthening of the notion of unique colourability. class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">-hypergraphs are a natural generalisation of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si18.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=191435a038a52eaea8ce56dee67cb590" title="Click to view the MathML source">σclass="mathContainer hidden">class="mathCode">-hypergraphs introduced by the first two authors in an earlier paper. We also show that there exist class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">-hypergraphs with arbitrarily large class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">-chromatic number and chromatic number but with bounded clique number. Dvořák et al. have characterised those class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode"> which can lead to a hypergraph with a gap in its class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">-spectrum. We give a short direct proof of the necessity of their condition on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">. We also prove a partial converse for the special case of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">-hypergraphs. Finally, we show that, for at least one family class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode"> which is known to yield hypergraphs with gaps, there exist no class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=03342d9a861e9f6de8debe7c04030e60" title="Click to view the MathML source">Σclass="mathContainer hidden">class="mathCode">-hypergraphs with gaps in their class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004057&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004057&_rdoc=1&_issn=0012365X&md5=f73088d26ec73f394d9978f89c992c91" title="Click to view the MathML source">Qclass="mathContainer hidden">class="mathCode">-spectrum.