Vi anser att utrymmeseffektiva algoritmer för tvåfärgade n-uniforma hypergrafer H = (V, E) i den strömmande modellen, när hyperkanterna anländer en i taget. Det är känt att varje sådan hypergraf med högst 0,7 n ln n 2 n hyperedges har en två-färg [4], som kan hittas deterministiskt i polynom tid, om tillåtet full tillgång till inmatningen. • Låt s D (v, q, n) vara det minsta utrymme som används av en deterministisk (one-pass) streaming algoritm som vid mottagande av en n-uniform hypergraph H på v hörn och q hyperedges (q ≤ 0,7 n ln n 2 n ), producerar en korrekt två-färgning av H. Vi visar att s D (n 2, q, n) =  på (q/n). • Låt s R (v, q, n) vara det minsta utrymme som används av en randomiserad (one-pass) strömmande algoritm som vid mottagande av en n-uniform hypergraph H på v hörn och q hyperedges med hög sannolikhet producerar en korrekt två-färgning av H (eller förklarar misslyckande). Vi visar att • Vi visar att för alla 4 ≤ t ≤ detta visar att varje n-uniform hypergraf med högst n 2 t hörn och 2 n- 1 exp( t 8 ) hyperkanter är tvåfärgade. Ovanstående resultat är inspirerade av studien av antalet q(n), det minsta möjliga antalet hyperkanter i en n-uniform hypergraph som inte är tvåfärgade. Det är känt att q(n) = (n ln n 2 n ) och q(n) = O(n 2 2 n ). Den nedre gränsen (på grund av Radhakrishnan och srinivasan [4]) har en motsvarande algoritm för att deterministiskt producera den tvåfärgade; den övre gränsen på grund av Erdős erhålls genom att plocka ca n 2 2 n hyperedges slumpmässigt från en vertex uppsättning av n 2 hörn. Vårt första resultat visar att ingen effektiv deterministisk strömningsalgoritm kan matcha algoritmens prestanda i [4]; det andra resultatet visar att det dock finns en effektiv randomiserad algoritm för uppgiften; det tredje resultatet visar att om antalet hörn är betydligt mindre än n 2, då varje icke-tvåfärgade hypergraf har betydligt mer än n 2 2 n hyperedges.
Ett annat nytt arbete på färgning i streaming modellen är Radhakrishnan et al. REF, som studerar problemet med 2-färgning en n-uniform hypergraph.
Hypergraph Two-Coloring in the Streaming Model
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}