Sparse 0-1-matrices and forbidden hypergraphs
References
[1]
M. Ajtai, J. Koml6s, J. Pintz, J. Spencer and E. Szemer@di, Extremal Uncrowded Hypergraphs, Journal of Combinatorial Theory Ser. A 32, 1982, 321-335.
[2]
M. Ajtai, J. Koml5s and E. Szemer@di, A Dense infinite Sidon Sequence, European Journal of Combinatorics 2, 1981, 2-11.
[3]
N. Alon, J. Bruck, J. Naor, M. Naor and R. Roth, Construction of Asymptotically Good Low-Rate Error Correcting Codes Through Pseudo-Random Graphs, IEEE Transactions on Information Theory 38, 1992, 509-516.
[4]
N. Alon, H. Lefmann and V. RSdl, On an Anti-Ramsey Type Result, Colloquia Mathematica Societatis Jinos Bolyai, 60. Sets, Graphs and Numbers, 1991, 9-22.
[5]
N. Alon and J. Spencer, The Probabilistic Method, Wiley & Sons, New York, 1992.
[6]
C. Bertram-Kretzberg and H. Lefmann, The Algorithmic Aspects of Uncrowded Hypergraphs, Proc. 8th ACM-SIAM Symposium on Discrete Algorithms SO- DA, 1997, 296-304.
[7]
R. A. Duke, H. Lefmann and V. RSdl, On Uncrowded Hypergraphs, Random Structures & Algorithms 6, 1995, 209-212.
[8]
P. Frankl and Z. Fiiredi, Union-Free Families o.f Sets and Equations over Fields, Journal of Number Theory 23, 1986, 210-218.
[9]
A. Fundia, Derandomizing Chebychev's Inequality to find Independent Sets in Uncrowded Hypergraphs, Random Structures & Algorithms 8, 1996, 131-147.
[10]
Z. Fiiredi, Turdn Type Problems, Surveys in Combinatorics, London Math. Soc., LNS 166, Cambridge University Press, 1991, 253-300.
[11]
Y. Kohayakawa, B. Kreuter and A. Steger, An Extremal Problem }or Random Graphs and the Number of Graphs with Large Even-Girth, preprint, 1995.
[12]
F. Lazebnik, V. A. Ustimenko and A. J. Woldar, A New Series) of the American Mathematical Society 32, 1995, 73-79.
[13]
H. Lefmann, P. Pudl~k and P. Savick)~, On Sparse Parity Check Matrices, Designs, Codes and Cryptography 12, 1997, 107-130.
[14]
R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge University Press, 1994.
[15]
A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan Graphs, Combinatorica 8, 1988, 261-277.
[16]
G. A. Maxgulis, Explicit Group Theoretical Construction of Combinatorial Schemes and Their Application to the Design of Expanders and Concentrators, J. Probl. Inform. Transmission 24, 1988, 39-46.
[17]
P. Pudlak and V. RSdl, Modified Ranks of Tensors and the Size of Circuits, Proc. 25th ACM Symposium on the Theory of Computing STOC, 1993, 523-531.
[18]
M. Sipser and D. A. Spielman, Expander Codes, Proc. 35th IEEE Symposium on Foundations of Computer Science FOCS, 1994, 566-576.
[19]
V. RSdl and E. Sifiajov~, Note on Independent S~ts in Steiner Systems, Random Structures & Algorithms 5, 1994, 183-190.
[20]
D. A. Spielman, Linear-time Encodable and Decodable Error-correcting Codes, Proc. 27th ACM Symposium on the Theory of Computing STOC, 1995, 388-397.
[21]
D. A. Spielman, Computationally E~cient Error-correcting Codes and Holographic Proofs, PhD thesis, MIT, 1995.
Index Terms
- Sparse 0-1-matrices and forbidden hypergraphs
Recommendations
Forbidden Subgraphs and Weak Locally Connected Graphs
A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called $$N^i$$Ni-locally connected if $$G[\{ x\in V(G): 1\le d_G(w, x)\le i\}]$$G[{x?V(G):1≤dG(w,x)≤i}] is connected and $$N_2$$N2-locally connected if $$G[\{uv: \{uw, vw\...
Planar graphs without 5-cycles and intersecting triangles are ( 1 , 1 , 0 ) -colorable
A ( c 1 , c 2 , , c k ) -coloring of G is a mapping : V ( G ) { 1 , 2 , , k } such that for every i , 1 i k , G V i has maximum degree at most c i , where G V i denotes the subgraph induced by the vertices colored i . Borodin and Raspaud conjecture that ...
(k,1)-coloring of sparse graphs
A graph G is (k,1)-colorable if the vertex set of G can be partitioned into subsets V"1 and V"2 such that the graph G[V"1] induced by the vertices of V"1 has maximum degree at most k and the graph G[V"2] induced by the vertices of V"2 has maximum degree ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- SIAM: Society for Industrial and Applied Mathematics
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 1998
Check for updates
Qualifiers
- Article
Conference
SODA98
Sponsor:
- SIGACT
- SIAM
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 202Total Downloads
- Downloads (Last 12 months)25
- Downloads (Last 6 weeks)4
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in