@article{Delsarte76, title = {Association schemes and t-designs in regular semilattices}, journal = {Journal of Combinatorial Theory, Series A}, volume = {20}, number = {2}, pages = {230-243}, year = {1976}, doi = {https://doi.org/10.1016/0097-3165(76)90017-0}, author = {Philippe Delsarte}, abstract = {A concept of regularity is introduced for finite semilattices with a length function. It is shown that the upper fiber of a regular semilattice carries an association scheme, when points are associated according to the length of their meet. In this framework, a natural definition of t-design is also proposed. The theory applies to triangular- and hypercubic-type association schemes, and to their q-analogs.} } @article{LarsenST22, title={Products of derangements in simple permutation groups}, volume={10}, DOI={10.1017/fms.2022.69}, journal={Forum of Mathematics, Sigma}, publisher={Cambridge University Press}, author={Larsen, M. and Shalev, A. and Tiep, P. H.}, year={2022}, pages={e83}} @book{Zelevinsky81, title={Representations of Finite Classical Groups: A Hopf Algebra Approach}, author={Zelevinsky, A.V.}, lccn={81009193}, series={Lecture notes in mathematics}, year={1981}, publisher={Springer-Verlag} } @article{MartinS06, author = {Martin, William J. and Sagan, Bruce E.}, title = {A New Notion of Transitivity for Groups and Sets of Permutations}, journal = {Journal of the London Mathematical Society}, volume = {73}, number = {1}, pages = {1-13}, doi = {https://doi.org/10.1112/S0024610705022441}, year = {2006} } @article{Smith17, title = {A formula for the Möbius function of the permutation poset based on a topological decomposition}, journal = {Advances in Applied Mathematics}, volume = {91}, pages = {98-114}, year = {2017}, doi = {https://doi.org/10.1016/j.aam.2017.06.002}, author = {Jason P. Smith} } @article{CameronD79, author = {Cameron, P. J. and Deza, M.}, title = {On Permutation Geometries}, journal = {Journal of the London Mathematical Society}, volume = {s2-20}, number = {3}, pages = {373-386}, doi = {https://doi.org/10.1112/jlms/s2-20.3.373}, year = {1979} } @article{Stanley88, author = {Stanley, Richard P.}, title = {Differential Posets}, journal = {Journal of the American Mathematical Society}, volume = {1}, number = {4}, pages = {919-61}, doi = {https://doi.org/10.2307/1990995}, year = {1988} } @misc{Godsil18, title={An Introduction to the Moebius Function}, author={Chris Godsil}, year={2018}, eprint={1803.06664}, EPRINTTYPE = {arxiv} } @misc{Lindzey23, title={Jack Derangements}, author={Nathan Lindzey}, year={2023}, eprint={2304.06629}, EPRINTTYPE = {arxiv} } @inproceedings{Lindzey23b, author = {Lindzey, Nathan}, title = {Disjointness Graphs (Extended Abstract)}, booktitle = {Proceedings of the 36th International Conference on``Formal Power Series and Algebraic Combinatorics"}, series = {FPSAC '24}, year = {2024} } @InProceedings{Terwilliger90, author="Terwilliger, Paul", title="The Incidence Algebra of a Uniform Poset", booktitle="Coding Theory and Design Theory", year="1990", publisher="Springer New York", address="New York, NY", pages="193--212", } @article{Stanton85, title = {Harmonics on posets}, journal = {Journal of Combinatorial Theory, Series A}, volume = {40}, number = {1}, pages = {136-149}, year = {1985}, doi = {https://doi.org/10.1016/0097-3165(85)90052-4}, author = {Dennis Stanton}, abstract = {Given a finite ranked poset P, for each rank of P a space of complex valued functions on P called harmonics is defined. If the automorphism group G of P is sufficiently rich, these harmonic spaces yield irreducible representations of G. A decomposition theorem, which is analogous to the decomposition theorem for spherical harmonics, is stated. It is also shown that P can always be decomposed into posets whose principal harmonics are orthogonal polynomials. Classical examples are given.} } @inproceedings{DafniFLLV21, author = {Neta Dafni and Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals}, editor = {James R. Lee}, title = {Complexity Measures on the Symmetric Group and Beyond (Extended Abstract)}, booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS} 2021, January 6-8, 2021, Virtual Conference}, series = {LIPIcs}, volume = {185}, pages = {87:1--87:5}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2021}, url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.87}, doi = {10.4230/LIPIcs.ITCS.2021.87}, timestamp = {Thu, 11 Feb 2021 11:55:06 +0100}, biburl = {https://dblp.org/rec/conf/innovations/DafniFLLV21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @misc{DafniFLLV21F, title={Complexity Measures on the Symmetric Group and Beyond (Submitted)}, author={Neta Dafni and Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals}, year={2021}, eprint={2010.07405}, archivePrefix={arXiv}, primaryClass={math.CO} } @article{DolegaS19, author = {Do\l{}ega, Maciej and Śniady, Piotr}, year = {2019}, month = {06}, pages = {}, title = {Gaussian fluctuations of Jack-deformed random Young diagrams}, volume = {174}, journal = {Probability Theory and Related Fields}, doi = {10.1007/s00440-018-0854-9} } @misc{CuencaDM23, title={Universality of global asymptotics of {J}ack-deformed random {Y}oung diagrams at varying temperatures}, author={Cesar Cuenca and Maciej Do\l{}ega and Alexander Moll}, journal={arXiv: Probability}, year = {2023}, copyright = {arXiv.org perpetual, non-exclusive license} } @article{James92, author = { Gordon James }, title = {Immanants}, journal = {Linear and Multilinear Algebra}, volume = {32}, number = {3-4}, pages = {197-210}, year = {1992}, publisher = {Taylor & Francis}, doi = {10.1080/03081089208818163} } @article{LiuZ22, doi = {10.37236/8569}, url = {https://doi.org/10.37236%2F8569}, year = 2022, month = {apr}, publisher = {The Electronic Journal of Combinatorics}, volume = {29}, number = {2}, author = {Xiaogang Liu and Sanming Zhou}, title = {Eigenvalues of {C}ayley Graphs}, journal = {The Electronic Journal of Combinatorics} } @article{GrinbergR14, title={Hopf Algebras in Combinatorics}, author={Darij Grinberg and Victor Reiner}, journal={arXiv: Combinatorics}, year={2014} } @article{NeumannP98, author = {Neumann, Peter and Praeger, Cheryl}, year = {1998}, month = {12}, pages = {564-586}, title = {Derangements and Eigenvalue-Free Elements in Finite Classical Groups}, volume = {58}, journal = {Journal of The London Mathematical Society}, doi = {10.1112/S0024610798006772} } @article{MoralesPP18, title = {Hook formulas for skew shapes I. q-analogues and bijections}, journal = {Journal of Combinatorial Theory, Series A}, volume = {154}, pages = {350-405}, year = {2018}, issn = {0097-3165}, doi = {https://doi.org/10.1016/j.jcta.2017.09.002}, url = {https://www.sciencedirect.com/science/article/pii/S0097316517301267}, author = {Alejandro H. Morales and Igor Pak and Greta Panova}, keywords = {Hook-length formula, Excited tableau, Standard Young tableau, Flagged tableau, Reverse plane partition, Hillman–Grassl correspondence, Robinson–Schensted–Knuth correspondence, Greene's theorem, Grassmannian permutation, Factorial Schur function}, abstract = {The celebrated hook-length formula gives a product formula for the number of standard Young tableaux of a straight shape. In 2014, Naruse announced a more general formula for the number of standard Young tableaux of skew shapes as a positive sum over excited diagrams of products of hook-lengths. We give an algebraic and a combinatorial proof of Naruse's formula, by using factorial Schur functions and a generalization of the Hillman–Grassl correspondence, respectively. The main new results are two different q-analogues of Naruse's formula: for the skew Schur functions, and for counting reverse plane partitions of skew shapes. We establish explicit bijections between these objects and families of integer arrays with certain nonzero entries, which also proves the second formula.} } @article{AhmadiM14, title = {A new proof for the {E}rdős--{K}o--{R}ado theorem for the alternating group}, journal = {Discrete Mathematics}, volume = {324}, pages = {28-40}, year = {2014}, issn = {0012-365X}, doi = {https://doi.org/10.1016/j.disc.2014.01.013}, url = {https://www.sciencedirect.com/science/article/pii/S0012365X14000259}, author = {Bahman Ahmadi and Karen Meagher}, keywords = {Derangement graph, Independent sets, Alternating group, Erdős–Ko–Rado theorem}, abstract = {A subset S of the alternating group on n points is intersecting if for any pair of permutations π,σ in S, there is an element i∈{1,…,n} such that π(i)=σ(i). We prove if n≥5 and S is intersecting, then |S|≤(n−1)!2. Also, we prove that provided that n≥5, then the only sets S that meet this bound are the cosets of the stabilizer of a point of {1,…,n}. These two results were first proven by Ku and Wong (2007), the proof given in this paper uses an algebraic method that is very different from the original proof.} } @article{GouldenJ92, ISSN = {00029939, 10886826}, URL = {http://www.jstor.org/stable/2159206}, abstract = {The relationship between the immanant and the Schur symmetric function is examined. Two expressions for the immanant are given in terms of the determinant. Generalisations include Foata and Zeilberger's β-extension of the MacMahon Master theorem. The relationships to some little known results of Littlewood and to idempotents constructed by Young are given.}, author = {I. P. Goulden and D. M. Jackson}, journal = {Proceedings of the American Mathematical Society}, number = {3}, pages = {605--612}, publisher = {American Mathematical Society}, title = {Immanants, {S}chur Functions, and the {M}acmahon Master Theorem}, urldate = {2022-10-17}, volume = {115}, year = {1992} } @book{Stanley2011, author = {Stanley, Richard P.}, title = {Enumerative Combinatorics: Volume 1}, year = {2011}, publisher = {Cambridge University Press}, address = {USA}, edition = {2nd}, abstract = {Richard Stanley's two-volume basic introduction to enumerative combinatorics has become the standard guide to the topic for students and experts alike. This thoroughly revised second edition of Volume 1 includes ten new sections and more than 300 new exercises, most with solutions, reflecting numerous new developments since the publication of the first edition in 1986. The material in Volume 1 was chosen to cover those parts of enumerative combinatorics of greatest applicability and with the most important connections with other areas of mathematics. The four chapters are devoted to an introduction to enumeration (suitable for advanced undergraduates), sieve methods, partially ordered sets, and rational generating functions. Much of the material is related to generating functions, a fundamental tool in enumerative combinatorics. In this new edition, the author brings the coverage up to date and includes a wide variety of additional applications and examples, as well as updated and expanded chapter bibliographies. Many of the less difficult new exercises have no solutions so that they can more easily be assigned to students. The material on P-partitions has been rearranged and generalized; the treatment of permutation statistics has been greatly enlarged; and there are also new sections on q-analogues of permutations, hyperplane arrangements, the cd-index, promotion and evacuation, and differential posets.} } @Article{OkunkovO97, Author = {Okun'kov, A. Yu. and Ol'shanskij, G.}, Title = {Shifted {Schur} functions}, FJournal = {St. Petersburg Mathematical Journal}, Journal = {St. Petersbg. Math. J.}, Volume = {9}, Number = {2}, Pages = {1}, Year = {1997}, Language = {English}, Keywords = {05E10,20C30,33-XX}, zbMATH = {1117961}, Zbl = {0894.05053} } @article{DengZ11, author = {Deng, Yun-Ping and Zhang, Xiao-Dong}, year = {2011}, month = {07}, pages = {}, title = {A Note on Eigenvalues of the Derangement Graph}, volume = {101}, journal = {Ars Combinatoria} } @article{AlexanderssonF17, title = {Shifted symmetric functions and multirectangular coordinates of {Y}oung diagrams}, journal = {Journal of Algebra}, volume = {483}, pages = {262-305}, year = {2017}, doi = {https://doi.org/10.1016/j.jalgebra.2017.03.036}, author = {Per Alexandersson and Valentin Féray}, keywords = {Shifted symmetric functions, Jack polynomials, Multirectangular coordinates, Zonal spherical functions, Characters of symmetric groups}, abstract = {In this paper, we study shifted Schur functions Sμ⋆, as well as a new family of shifted symmetric functions Kμ linked to Kostka numbers. We prove that both are polynomials in multi-rectangular coordinates, with nonnegative coefficients when written in terms of falling factorials. We then propose a conjectural generalization to the Jack setting. This conjecture is a lifting of Knop and Sahi's positivity result for usual Jack polynomials and resembles recent conjectures of Lassalle. We prove our conjecture for one-part partitions.} } @InProceedings{BjorklundW19, author = {Andreas Bj{\"o}rklund and Ryan Williams}, title = {{Computing Permanents and Counting {H}amiltonian Cycles by Listing Dissimilar Vectors}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {25:1--25:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10601}, URN = {urn:nbn:de:0030-drops-106018}, doi = {10.4230/LIPIcs.ICALP.2019.25}, annote = {Keywords: permanent, Hamiltonian cycle, orthogonal vectors} } @article{Naruse14, author = {Hiroshi Naruse}, year = {2014}, title = {Schubert calculus and hook formula}, journal = {73rd S\'eminaire Lotharingien de Combinatoire} } @article{ekll23, author = {Shai Evra and Guy Kindler and Nathan Lindzey and Noam Lifshitz}, year = {2023}, title = {Global Hypercontractivity for Finite Groups of {L}ie Type}, journal = {(In preperation)} } @article{kls23, author = {Esty Kelman and Nathan Lindzey and Ohad Sheinfeld}, year = {2023}, title = {Forbidden Intersection Theorems for Matrix Spaces}, journal = {(In preperation)} } @article{BjorklundH13, author = {Björklund, Andreas and Husfeldt, Thore}, year = {2013}, month = {01}, pages = {}, title = {The Parity of Directed {H}amiltonian Cycles}, journal = {Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS}, doi = {10.1109/FOCS.2013.83} } @article{Weintraub90, title = {Some observations on plethysms}, journal = {Journal of Algebra}, volume = {129}, number = {1}, pages = {103-114}, year = {1990}, issn = {0021-8693}, doi = {https://doi.org/10.1016/0021-8693(90)90241-F}, url = {https://www.sciencedirect.com/science/article/pii/002186939090241F}, author = {Steven H Weintraub} } @article{Huang87, title = {An analogue of the {E}rd{\H{o}}s--{K}o--{R}ado theorem for the distance-regular graphs of bilinear forms}, journal = {Discrete Mathematics}, volume = {64}, number = {2}, pages = {191-198}, year = {1987}, issn = {0012-365X}, doi = {https://doi.org/10.1016/0012-365X(87)90188-9}, url = {https://www.sciencedirect.com/science/article/pii/0012365X87901889}, author = {Tayuan Huang}, abstract = {An analogue of the Erdös-Ko-Rado theorem is proved for the distance-regular graphs Hq(k, n) with k × n matrices over GF(q) as vertex set and two matrices A and B adjacent if the rank of A − B is 1, where n ⩾ k + 1 and (n, q) ≠ (k + 1, 2). As an easy corollary, we prove that Hq(k, n) has no perfect e-codes, e ⩾ 1.} } @article{BlokhuisBCFMPS10, author = {Aart Blokhuis and Andries E. Brouwer and Ameera Chowdhury and Peter Frankl and T. Mussche and Bal{\'{a}}zs Patk{\'{o}}s and Tam{\'{a}}s Sz{\"{o}}nyi}, title = {A Hilton-Milner Theorem for Vector Spaces}, journal = {Electron. J. Comb.}, volume = {17}, number = {1}, year = {2010}, url = {http://www.combinatorics.org/Volume\_17/Abstracts/v17i1r71.html}, timestamp = {Thu, 09 Jul 2020 22:42:29 +0200}, biburl = {https://dblp.org/rec/journals/combinatorics/BlokhuisBCFMPS10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{GongLW17, abstract = {Let V be an (n+l)-dimensional vector space over the finite field Fq with l≥n>0, and W be a fixed l-dimensional subspace of V. Suppose F is a non-trivial intersecting family of n-dimensional subspaces U of V with U∩W=0. In this paper, we give the tight upper bound for the size of F, and describe the structure of F which reaches the upper bound.}, affiliation = {Sch. Math. Sci. & Lab. Math. Com. Sys., Beijing Normal University, Beijing, 100875, China}, author = {Gong, Chao and Lv, Benjian and Wang, Kaishun}, doi = {10.1016/j.laa.2016.11.016}, journal = {Linear Algebra and its Applications}, keywords = {Intersecting family; Hilton–Milner theorem; Bilinear forms graph; Covering number}, language = {English}, number = {C}, pages = {130-144}, title = {The {H}ilton–{M}ilner theorem for the distance-regular graphs of bilinear forms}, volume = {515}, year = {2017}, } @article{Delsarte78, title = {Bilinear forms over a finite field, with applications to coding theory}, journal = {Journal of Combinatorial Theory, Series A}, volume = {25}, number = {3}, pages = {226-241}, year = {1978}, issn = {0097-3165}, doi = {https://doi.org/10.1016/0097-3165(78)90015-8}, url = {https://www.sciencedirect.com/science/article/pii/0097316578900158}, author = {Ph Delsarte}, abstract = {Let Ω be the set of bilinear forms on a pair of finite-dimensional vector spaces over GF(q). If two bilinear forms are associated according to their q-distance (i.e., the rank of their difference), then Ω becomes an association scheme. The characters of the adjacency algebra of Ω, which yield the MacWilliams transform on q-distance enumerators, are expressed in terms of generalized Krawtchouk polynomials. The main emphasis is put on subsets of Ω and their q-distance structure. Certain q-ary codes are attached to a given X ⊂ Ω; the Hamming distance enumerators of these codes depend only on the q-distance enumerator of X. Interesting examples are provided by Singleton systems X ⊂ Ω, which are defined as t-designs of index 1 in a suitable semilattice (for a given integer t). The q-distance enumerator of a Singleton system is explicitly determined from the parameters. Finally, a construction of Singleton systems is given for all values of the parameters.} } @article{Spiga19, title = {The {E}rd{\H{o}}s--{K}o--{R}ado theorem for the derangement graph of the projective general linear group acting on the projective space}, journal = {Journal of Combinatorial Theory, Series A}, volume = {166}, pages = {59-90}, year = {2019}, issn = {0097-3165}, doi = {https://doi.org/10.1016/j.jcta.2019.02.015}, url = {https://www.sciencedirect.com/science/article/pii/S0097316519300305}, author = {Pablo Spiga}, keywords = {Derangement graph, Independent set, Erdős-Ko-Rado theorem, Projective general linear group}, abstract = {In this paper we prove an Erdős-Ko-Rado-type theorem for intersecting sets of permutations. We show that an intersecting set of maximal size in the projective general linear group PGLn+1(q), in its natural action on the points of the n-dimensional projective space, is either a coset of the stabiliser of a point or a coset of the stabiliser of a hyperplane. This gives a positive solution to [15, Conjecture 2].} } @article{CalabroIKP03, title = {The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs}, journal = {Journal of Computer and System Sciences}, volume = {74}, number = {3}, pages = {386-393}, year = {2008}, note = {Computational Complexity 2003}, issn = {0022-0000}, doi = {https://doi.org/10.1016/j.jcss.2007.06.015}, url = {https://www.sciencedirect.com/science/article/pii/S0022000007000827}, author = {Chris Calabro and Russell Impagliazzo and Valentine Kabanets and Ramamohan Paturi}, keywords = {Satisfiability, Unique satisfiability, -SAT, Subexponential time reduction, Isolation Lemma}, } @book{CyganFKLMPPS15, author = {Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D{\'{a}}niel Marx and Marcin Pilipczuk and Michal Pilipczuk and Saket Saurabh}, title = {Parameterized Algorithms}, publisher = {Springer}, year = {2015}, url = {https://doi.org/10.1007/978-3-319-21275-3}, doi = {10.1007/978-3-319-21275-3}, isbn = {978-3-319-21274-6}, timestamp = {Sun, 25 Oct 2020 22:32:21 +0100}, biburl = {https://dblp.org/rec/books/sp/CyganFKLMPPS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{ImpagliazzoP99, author = {Impagliazzo, Russell and Paturi, Ramamohan}, title = {The Complexity of $k$-{S}{A}{T}}, year = {1999}, isbn = {0769500757}, publisher = {IEEE Computer Society}, address = {USA}, abstract = {The problem of k-SAT is to determine if the given k-CNF has a satisfying solution. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k geq 3.Define s_k (for kgeq 3) to be the infimum of {delta: mbox{there exists an O(2^{delta n})} mbox{ algorithm for solving k-SAT} }. Define {bf ETH} (Exponential-Time Hypothesis) for k-SAT as follows: for kgeq 3, s_k >0. In other words, for k geq 3, k-SAT does not have a subexponential-time algorithm.In this paper, we show that s_k is an increasing sequence assuming eth for k-SAT. Let s_infty be the limit of s_k. We will in fact show that s_k leq (1-d/(ek))s_infty for some constant d >0.}, booktitle = {Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity}, pages = {237}, keywords = {NP-completeness, Reductions, Satisfiability, Complexity Theory}, series = {COCO '99} } @article{EllisFP11, author = {D. Ellis and E. Friedgut and H. Pilpel}, title = {Intersecting families of permutations}, journal = {J. Amer. Math. Soc.}, volume = {24}, year = {2011}, pages = {649-682} } @book{ODonnell14, title={Analysis of Boolean Functions}, author={Ryan O'Donnell}, year={2014}, publisher={Cambridge University Press} } @article{EllisFF17, title={LOW-DEGREE {B}OOLEAN FUNCTIONS ON ${S}_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY}, volume={5}, DOI={10.1017/fms.2017.24}, journal={Forum of Mathematics, Sigma}, publisher={Cambridge University Press}, author={Ellis, David and Filmus, Yuval and Friedgut, Ehud}, year={2017}, pages={e23}} @article{Strahov07, title = "Generalized characters of the symmetric group", journal = "Advances in Mathematics", volume = "212", number = "1", pages = "109 - 142", year = "2007", issn = "0001-8708", doi = "https://doi.org/10.1016/j.aim.2006.09.017", url = "http://www.sciencedirect.com/science/article/pii/S0001870806003355", author = "Eugene Strahov", keywords = "Symmetric group, Gelfand pairs, Characters, Symmetric functions", abstract = "Normalized irreducible characters of the symmetric group S(n) can be understood as zonal spherical functions of the Gelfand pair (S(n)�S(n),diagS(n)). They form an orthogonal basis in the space of the functions on the group S(n) invariant with respect to conjugations by S(n). In this paper we consider a different Gelfand pair connected with the symmetric group, that is an ?unbalanced? Gelfand pair (S(n)�S(n?1),diagS(n?1)). Zonal spherical functions of this Gelfand pair form an orthogonal basis in a larger space of functions on S(n), namely in the space of functions invariant with respect to conjugations by S(n?1). We refer to these zonal spherical functions as normalized generalized characters of S(n). The main discovery of the present paper is that these generalized characters can be computed on the same level as the irreducible characters of the symmetric group. The paper gives a Murnaghan?Nakayama type rule, a Frobenius type formula, and an analogue of the determinantal formula for the generalized characters of S(n)." } @techreport{Greenhalgh, title={Random Walks on Groups with Subgroup Invariance Properties}, author={A.S. Greenhalgh}, year = {1989}, institution = {Stanford University, Department of Statistics}, month = {04}, } @book {GodsilRoyle, AUTHOR = {Godsil, Chris and Royle, Gordon}, TITLE = {Algebraic {G}raph {T}heory}, SERIES = {Graduate Texts in Mathematics}, VOLUME = {207}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York}, YEAR = {2001}, PAGES = {xx+439}, } @book{JamesKerber, title={The Representation Theory of the Symmetric Group}, author={James, G.D. and Kerber, A.}, isbn={9780521302364}, lccn={gb85036945}, series={Encyclopedia of Mathematics and its Applications}, url={https://books.google.ca/books?id=yWa\_RaqkLUsC}, year={1984}, publisher={Cambridge University Press} } @InProceedings{Mid04, author="Midrij{\={a}}nis, Gatis", title="A Polynomial Quantum Query Lower Bound for the Set Equality Problem", booktitle="Automata, Languages and Programming", year="2004", publisher="Springer Berlin Heidelberg", address="Berlin, Heidelberg", pages="996--1005", isbn="978-3-540-27836-8" } @book{Sagan, title={The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions}, author={Sagan, B.}, isbn={9780387950679}, lccn={00400422}, series={Graduate Texts in Mathematics}, url={https://books.google.ca/books?id=Jm-HBaMdt8sC}, year={2001}, publisher={Springer New York} } @book{BannaiI84, title={Algebraic {C}ombinatorics I: {A}ssociation {S}chemes}, author={Bannai, E. and Ito, T.}, isbn={9780805304909}, lccn={83021355}, series={Mathematics lecture note series}, url={http://books.google.com/books?id=bgDvAAAAMAAJ}, year={1984}, publisher={Benjamin/Cummings Pub. Co.} } @inproceedings{LMRSS11, author = {Lee, Troy and Mittal, Rajat and Reichardt, Ben W. and \v{S}palek, Robert and Szegedy, Mario}, title = {Quantum Query Complexity of State Conversion}, booktitle = {Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science}, series = {FOCS '11}, year = {2011}, isbn = {978-0-7695-4571-4}, pages = {344--353}, numpages = {10}, url = {http://dx.doi.org/10.1109/FOCS.2011.75}, doi = {10.1109/FOCS.2011.75}, acmid = {2082971}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, } @book{Diaconis88, added-at = {2010-02-04T21:40:41.000+0100}, address = {Hayward, CA}, author = {Diaconis, Persi}, biburl = {http://www.bibsonomy.org/bibtex/2933838b3e918380eb835383259944baf/peter.ralph}, description = {MR: Publications results for "MR Number=(964069)"}, interhash = {f8e3d552ac7a2a48d97ec0820620e592}, intrahash = {933838b3e918380eb835383259944baf}, isbn = {0-940600-14-5}, keywords = {discrete_fourier_transform reference representation_theory}, mrclass = {60-02 (20C99 62-02)}, mrnumber = {MR964069 (90a:60001)}, mrreviewer = {Philippe Bougerol}, pages = {vi+198}, publisher = {Institute of Mathematical Statistics}, series = {Institute of Mathematical Statistics Lecture Notes---Monograph Series, 11}, timestamp = {2010-02-04T21:40:41.000+0100}, title = {Group {R}epresentations in {P}robability and {S}tatistics}, url = {http://projecteuclid.org/euclid.lnms/1215467407}, year = 1988 } @article{Wilson14, title = {FIW-modules and stability criteria for representations of classical Weyl groups}, journal = {Journal of Algebra}, volume = {420}, pages = {269-332}, year = {2014}, doi = {https://doi.org/10.1016/j.jalgebra.2014.08.010}, author = {Jennifer C.H. Wilson}, keywords = {FI-modules, Representation stability, Classical Weyl groups, Representation theory of classical Weyl groups, Homological stability, Diagonal coinvariant algebras} } @article{ChenR92, title = {q-Analogs of the inclusion- exclusion principle and permutations with restricted position}, journal = {Discrete Mathematics}, volume = {104}, number = {1}, pages = {7-22}, year = {1992}, issn = {0012-365X}, doi = {https://doi.org/10.1016/0012-365X(92)90622-M}, url = {https://www.sciencedirect.com/science/article/pii/0012365X9290622M}, author = {William Y.C. Chen and Gian-Carlo Rota}, abstract = {We derive a q-analog of the principle of inclusion-exclusion, and use it to derive a q-analog of the Kaplansky–Riordan theory of permutations with restricted position. Some analogies with the theory of Mahonian statistics are pointed out at the end, leading to a conjectured relationship between the two.} } @book{StanleyV201, title={Enumerative Combinatorics: Volume 2}, author={Stanley, R.P.}, series={Cambridge Studies in Advanced Mathematics}, year={2001}, publisher={Cambridge University Press} } @book{CST, title={Harmonic Analysis on Finite Groups: Representation Theory, Gelfand Pairs and Markov Chains}, author={Ceccherini-Silberstein, T. and Scarabotti, F. and Tolli, F.}, isbn={9781139470803}, series={Cambridge Studies in Advanced Mathematics}, url={https://books.google.ca/books?id=3trud4weQ3AC}, year={2008}, publisher={Cambridge University Press} } @book{GodsilMeagher, title={Erd{\H{o}}s--Ko--Rado Theorems: Algebraic Approaches}, author={Godsil, C. and Meagher, K.}, series={Cambridge Studies in Advanced Mathematics}, year={2015}, publisher={Cambridge University Press} } @inproceedings{Shi02, author = {Shi, Yaoyun}, title = {Quantum Lower Bounds for the Collision and the Element Distinctness Problems}, booktitle = {Proceedings of the 43rd Symposium on Foundations of Computer Science}, series = {FOCS '02}, year = {2002}, isbn = {0-7695-1822-2}, pages = {513--519}, numpages = {7}, url = {http://dl.acm.org/citation.cfm?id=645413.652132}, acmid = {652132}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, } @article{Zha15, author = {Zhandry, Mark}, title = {A Note on the Quantum Collision and Set Equality Problems}, journal = {Quantum Info. Comput.}, issue_date = {May 2015}, volume = {15}, number = {7-8}, month = may, year = {2015}, issn = {1533-7146}, pages = {557--567}, numpages = {11}, url = {http://dl.acm.org/citation.cfm?id=2871411.2871413}, acmid = {2871413}, publisher = {Rinton Press, Incorporated}, address = {Paramus, NJ}, keywords = {quantum collision problem, random functions}, } @article{BR18, title={Adversary lower bounds for the collision and the set equality problems}, author={Aleksandrs Belovs and Ansis Rosmanis}, journal={Quantum Information \& Computation}, year={2018}, volume={18}, pages={200-224} } @misc{RB13, title={On Adversary Lower Bounds for the Collision and the Set Equality Problems}, author={Ansis Rosmanis and Aleksandrs Belovs}, note={Available at arXiv:1310.5185v1 [quant-ph]}, year={2013} } @article{Montanaro15, author = {Montanaro, Ashley}, year = {2015}, month = {11}, pages = {}, title = {Quantum algorithms: An overview}, volume = {2}, journal = {npj Quantum Information}, doi = {10.1038/npjqi.2015.23} } @misc{GodsilAssoc, author={Chris Godsil}, title={Notes on Association Schemes}, year={2010} } @article{Ros14, author={Ansis Rosmanis}, title={Quantum Adversary Lower Bound for Element Distinctness with Small Range}, journal={Chicago Journal of Theoretical Computer Science}, volume={2014}, number={4}, month={July}, year={2014} } @inproceedings{Ambainis2018, author={Andris Ambainis}, title={Understanding quantum algorithms via query complexity}, booktitle={Proceedings of the 2018 International Congress of Mathematicians}, volume={3}, pages={3249--3270}, year={2018} } @book{nielsen2000quantum, title={Quantum Computation and Quantum Information}, author={Nielsen, M.A. and Chuang, I.L.}, isbn={9780521635035}, lccn={98022029}, series={Cambridge Series on Information and the Natural Sciences}, url={https://books.google.com.sg/books?id=65FqEKQOfP8C}, year={2000}, publisher={Cambridge University Press} } @inproceedings{HLS07, author = {H\o{}yer, Peter and Lee, Troy and {\v S}palek, Robert}, title = {Negative Weights Make Adversaries Stronger}, booktitle = {Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing}, series = {STOC '07}, year = {2007}, isbn = {978-1-59593-631-8}, location = {San Diego, California, USA}, pages = {526--535}, numpages = {10}, url = {http://doi.acm.org/10.1145/1250790.1250867}, doi = {10.1145/1250790.1250867}, acmid = {1250867}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {adversary method, certificate complexity barrier, formula size, lower bounds, quantum computing, quantum query complexity}, } @article{ArratiaD14, title={Completely Effective Error Bounds for Stirling Numbers of the First and Second Kinds via Poisson Approximation}, author={R. Arratia and S. Desalvo}, journal={Annals of Combinatorics}, year={2014}, volume={21}, pages={1-24} } @article{Peel71, title={Hook representations of the symmetric groups}, volume={12}, DOI={10.1017/S0017089500001245}, number={2}, journal={Glasgow Mathematical Journal}, publisher={Cambridge University Press}, author={Peel, M. H.}, year={1971}, pages={136–149}} @article{FrumkinY90, title={Rank of inclusion matrices and modular representation theory}, author={A. Frumkin and Arieh Yakir}, journal={Israel Journal of Mathematics}, year={1990}, volume={71}, pages={309-320} } @article{Sin13, title={Smith normal forms of incidence matrices}, author={Peter Sin}, journal={Science China Mathematics}, year={2013}, volume={56} } @book{DummitFoote, place={New York}, edition={3rd ed}, title={Abstract algebra}, publisher={Wiley}, author={Dummit, David S. and Foote, Richard M.}, year={2004} } @misc{Jolliffe20, title={A Short Proof of the Rank Formula for Inclusion Matrices using the Representation Theory of the Symmetric Group}, author={Liam Jolliffe}, year={2020}, eprint={2009.05202}, archivePrefix={arXiv}, primaryClass={math.CO} } @inproceedings{GabowT83, author = {Harold N. Gabow and Robert Endre Tarjan}, title = {A Linear-Time Algorithm for a Special Case of Disjoint Set Union}, booktitle = {STOC}, year = {1983}, pages = {246-251}, ee = {http://doi.acm.org/10.1145/800061.808753}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{LinialR81, author = {Linial, Nathan and Rothschild, Bruce L.}, title = {Incidence Matrices of Subsets—A Rank Formula}, journal = {SIAM Journal on Algebraic Discrete Methods}, volume = {2}, number = {3}, pages = {333-340}, year = {1981}, doi = {10.1137/0602037}, URL = { https://doi.org/10.1137/0602037 }, eprint = { https://doi.org/10.1137/0602037 } } @InProceedings{LindzeyR20, author = {Nathan Lindzey and Ansis Rosmanis}, title = {{A Tight Lower Bound For Non-Coherent Index Erasure}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {59:1--59:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Thomas Vidick} } @article{CanfieldW81, author = { E.R. Canfield and S.G. Williamson }, title = {Hook length products and {C}ayley operators of classical invariant theory}, journal = {Linear and Multilinear Algebra}, volume = {9}, number = {4}, pages = {289-297}, year = {1981}, publisher = {Taylor & Francis}, doi = {10.1080/03081088108817380} } @book{Jukna, author = {Jukna, Stasys}, title = {Extremal Combinatorics: With Applications in Computer Science}, year = {2010}, isbn = {3642085598}, publisher = {Springer Publishing Company, Incorporated}, edition = {1st} } @article{Lindzey20, title = "Stability for 1-intersecting families of perfect matchings", journal = "European Journal of Combinatorics", volume = "86", pages = "103091", year = "2020", doi = "https://doi.org/10.1016/j.ejc.2020.103091", author = "Nathan Lindzey" } @ARTICLE{DukesIL20, author={P. J. {Dukes} and F. {Ihringer} and N. {Lindzey}}, journal={IEEE Transactions on Information Theory}, title={On the Algebraic Combinatorics of Injections and its Applications to Injection Codes}, year={2020}, volume={}, number={}, pages={1-1},} @INPROCEEDINGS{KhotMS18, author={K. {Subhash} and D. {Minzer} and M. {Safra}}, booktitle={2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)}, title={Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion}, year={2018}, volume={}, number={}, pages={592-601},} @article{Wilson90, title = "A Diagonal Form for the Incidence Matrices of t-Subsets vs.k-Subsets", journal = "European Journal of Combinatorics", volume = "11", number = "6", pages = "609 - 615", year = "1990", issn = "0195-6698", doi = "https://doi.org/10.1016/S0195-6698(13)80046-7", url = "http://www.sciencedirect.com/science/article/pii/S0195669813800467", author = "Richard M. Wilson" } @article{LovaszS93, title = "Communication complexity and combinatorial lattice theory", journal = "Journal of Computer and System Sciences", volume = "47", number = "2", pages = "322 - 349", year = "1993", issn = "0022-0000", doi = "https://doi.org/10.1016/0022-0000(93)90035-U", url = "http://www.sciencedirect.com/science/article/pii/002200009390035U", author = "László Lovăsz and Michael Saks", abstract = "In a recent paper, Hajnal, Maass, and Turán analyzed the communication complexity of graph connectivity. Building on this work, we develop a general framework for the study of a broad class of communication problems which has several interesting special cases including the graph connectivity problem. The approach is based on the combinatorial theory of alignments and lattices." } @article{DBLP:journals/jcss/CalabroIKP08, author = {Chris Calabro and Russell Impagliazzo and Valentine Kabanets and Ramamohan Paturi}, title = {The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs}, journal = {J. Comput. Syst. Sci.}, volume = {74}, number = {3}, pages = {386--393}, year = {2008}, url = {https://doi.org/10.1016/j.jcss.2007.06.015}, doi = {10.1016/j.jcss.2007.06.015}, timestamp = {Wed, 14 Nov 2018 10:33:57 +0100}, biburl = {https://dblp.org/rec/bib/journals/jcss/CalabroIKP08}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{ImpagliazzoP01, author = {Russell Impagliazzo and Ramamohan Paturi}, title = {On the Complexity of k-SAT}, journal = {J. Comput. Syst. Sci.}, volume = {62}, number = {2}, pages = {367--375}, year = {2001}, url = {https://doi.org/10.1006/jcss.2000.1727}, doi = {10.1006/jcss.2000.1727}, timestamp = {Wed, 14 Nov 2018 10:33:59 +0100}, biburl = {https://dblp.org/rec/bib/journals/jcss/ImpagliazzoP01}, bibsource = {dblp computer science bibliography, https://dblp.org} } @Article{Wlodarczyk19, author="W{\l}odarczyk, Micha{\l}", title="Clifford Algebras Meet Tree Decompositions", journal="Algorithmica", year="2019", month="Feb", day="01", volume="81", number="2", pages="497--518", abstract="We introduce the non-commutative subset convolution---a convolution of functions useful when working with determinant-based algorithms. In order to compute it efficiently, we take advantage of Clifford algebras, a generalization of quaternions used mainly in the quantum field theory. We apply this tool to speed up algorithms counting subgraphs parameterized by the treewidth of a graph. We present an {\$}{\$}O^*((2^{\backslash}omega + 1)^{\{}tw{\}}){\$}{\$}O∗((2$\omega$+1)tw)-time algorithm for counting Steiner trees and an {\$}{\$}O^*((2^{\backslash}omega + 2)^{\{}tw{\}}){\$}{\$}O∗((2$\omega$+2)tw)-time algorithm for counting Hamiltonian cycles, both of which improve the previously known upper bounds. These constitute also the best known running times of deterministic algorithms for decision versions of these problems and they match the best obtained running times for pathwidth parameterization under assumption {\$}{\$}{\backslash}omega = 2{\$}{\$}$\omega$=2.", issn="1432-0541", doi="10.1007/s00453-018-0489-3", url="https://doi.org/10.1007/s00453-018-0489-3" } @inproceedings{BjorklundKK17, author = {Andreas Bj{\"{o}}rklund and Petteri Kaski and Ioannis Koutis}, title = {Directed Hamiltonicity and Out-Branchings via Generalized Laplacians}, booktitle = {44th International Colloquium on Automata, Languages, and Programming, {ICALP} 2017, July 10-14, 2017, Warsaw, Poland}, pages = {91:1--91:14}, year = {2017}, crossref = {DBLP:conf/icalp/2017}, url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.91}, doi = {10.4230/LIPIcs.ICALP.2017.91}, timestamp = {Thu, 02 May 2019 17:40:19 +0200}, biburl = {https://dblp.org/rec/bib/conf/icalp/BjorklundKK17}, bibsource = {dblp computer science bibliography, https://dblp.org} } @ARTICLE{GopalanHJY14, author={P. {Gopalan} and C. {Huang} and B. {Jenkins} and S. {Yekhanin}}, journal={IEEE Transactions on Information Theory}, title={Explicit Maximally Recoverable Codes With Locality}, year={2014}, volume={60}, number={9}, pages={5245-5256}, keywords={error correction codes;forward error correction;linear codes;explicit maximally recoverable codes;systematic linear code;parity symbols;data symbols;erasure coding;data storage;single symbol;heavy parity;erasure patterns;information theoretically correctable;alphabet size;local parity;Parity check codes;Topology;Linear codes;Systematics;Equations;Reliability;Memory;Codes with locality;maximally recoverable codes}, doi={10.1109/TIT.2014.2332338}, ISSN={0018-9448}, month={Sep.},} @inproceedings{GopalanHKSWY17, author = {Gopalan, Parikshit and Hu, Guangda and Kopparty, Swastik and Saraf, Shubhangi and Wang, Carol and Yekhanin, Sergey}, title = {Maximally Recoverable Codes for Grid-like Topologies}, booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms}, series = {SODA '17}, year = {2017}, location = {Barcelona, Spain}, pages = {2092--2108}, numpages = {17}, url = {http://dl.acm.org/citation.cfm?id=3039686.3039822}, acmid = {3039822}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, } @article {Jack70, AUTHOR = {Jack, Henry}, TITLE = {A class of symmetric polynomials with a parameter}, JOURNAL = {Proc. Roy. Soc. Edinburgh Sect. A}, FJOURNAL = {Proceedings of the Royal Society of Edinburgh. Section A. Mathematics}, VOLUME = {69}, YEAR = {1970/1971}, PAGES = {1--18}, ISSN = {0308-2105}, MRCLASS = {12.30 (10.00)}, MRNUMBER = {0289462}, MRREVIEWER = {H. Gupta}, } @article{Lovasz79, author = {Lov\'asz, L.}, title = {On the {S}hannon Capacity of a Graph}, journal = {IEEE Trans. Inf. Theor.}, issue_date = {January 1979}, volume = {25}, number = {1}, month = jan, year = {1979}, issn = {0018-9448}, pages = {1--7}, numpages = {7}, url = {https://doi.org/10.1109/TIT.1979.1055985}, doi = {10.1109/TIT.1979.1055985}, acmid = {2269451}, publisher = {IEEE Press}, address = {Piscataway, NJ, USA}, } @Article{Schrijver81, title = {Association schemes and the {S}hannon capacity: {E}berlein-polynomials and the {E}rd{\"o}s-{K}o-{R}ado Theorem}, author = {Schrijver, Alexander}, journal = {Algebraic Methods in Graph Theory (L. Lov\'asz and V.T. Sos, eds.)}, pages = {671--688}, year = 1981, month = jan } @inproceedings{Muzychuk94, title={On Association Schemes of the Symmetric Group ${S}_{2n}$ Acting on Partitions of Type $2^n$}, author ={Mikhail Muzychuk}, booktitle={Bayreuther Mathematische Schriften}, year={1994} } @inproceedings{BjorklundKK17, author = {Andreas Bj{\"{o}}rklund and Petteri Kaski and Ioannis Koutis}, title = {Directed {H}amiltonicity and Out-Branchings via Generalized {L}aplacians}, booktitle = {44th International Colloquium on Automata, Languages, and Programming, {ICALP} 2017, July 10-14, 2017, Warsaw, Poland}, pages = {91:1--91:14}, year = {2017}, crossref = {DBLP:conf/icalp/2017}, url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.91}, doi = {10.4230/LIPIcs.ICALP.2017.91}, timestamp = {Thu, 23 Aug 2018 15:56:42 +0200}, biburl = {https://dblp.org/rec/bib/conf/icalp/BjorklundKK17}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{BjorklundH13, author = {Bj\"{o}rklund, Andreas and Husfeldt, Thore}, title = {The Parity of Directed {H}amiltonian Cycles}, booktitle = {Proceedings of the IEEE 54th Annual Symposium on Foundations of Computer Science}, series = {FOCS '13}, year = {2013}, isbn = {978-0-7695-5135-7}, pages = {727--735}, numpages = {9}, url = {http://dx.doi.org/10.1109/FOCS.2013.83}, doi = {10.1109/FOCS.2013.83}, acmid = {2570656}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, } @book{KnuthVol4c, author = {Knuth, Donald E.}, title = {The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions}, year = {2005}, isbn = {0201853949}, publisher = {Addison-Wesley Professional}, } @book{Diestel, title={Graph Theory}, author={Diestel, R.}, isbn={9783540261834}, lccn={99057468}, series={Electronic library of mathematics}, url={https://books.google.ca/books?id=aR2TMYQr2CMC}, year={2006}, publisher={Springer} } @Article{KerovV85, author="Vershik, A. M. and Kerov, S. V.", title="Asymptotic of the largest and the typical dimensions of irreducible representations of a symmetric group", journal="Functional Analysis and Its Applications", year="1985", month="Jan", day="01", volume="19", number="1", pages="21--31", issn="1573-8485", doi="10.1007/BF01086021", url="https://doi.org/10.1007/BF01086021" } @inproceedings{DafniFLLV21, author = {Neta Dafni and Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals}, editor = {James R. Lee}, title = {Complexity {M}easures on the {S}ymmetric {G}roup and {B}eyond (Extended Abstract)}, booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS} 2021, January 6-8, 2021, Virtual Conference}, series = {LIPIcs}, volume = {185}, pages = {87:1--87:5}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2021}, url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.87}, doi = {10.4230/LIPIcs.ITCS.2021.87}, timestamp = {Thu, 11 Feb 2021 11:55:06 +0100}, biburl = {https://dblp.org/rec/conf/innovations/DafniFLLV21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{ChurchF13, title = {Representation theory and homological stability}, journal = {Advances in Mathematics}, volume = {245}, pages = {250-314}, year = {2013}, issn = {0001-8708}, doi = {https://doi.org/10.1016/j.aim.2013.06.016}, url = {https://www.sciencedirect.com/science/article/pii/S0001870813002259}, author = {Thomas Church and Benson Farb}, keywords = {Representation theory, Homological stability, Braid groups}, abstract = {We introduce the idea of representation stability (and several variations) for a sequence of representations Vn of groups Gn. A central application of the new viewpoint we introduce here is the importation of representation theory into the study of homological stability. This makes it possible to extend classical theorems of homological stability to a much broader variety of examples. Representation stability also provides a framework in which to find and to predict patterns, from classical representation theory (Littlewood–Richardson and Murnaghan rules, stability of Schur functors), to cohomology of groups (pure braid, Torelli and congruence groups), to Lie algebras and their homology, to the (equivariant) cohomology of flag and Schubert varieties, to combinatorics (the (n+1)n−1 conjecture). The majority of this paper is devoted to exposing this phenomenon through examples. In doing this we obtain applications, theorems and conjectures. Beyond the discovery of new phenomena, the viewpoint of representation stability can be useful in solving problems outside the theory. In addition to the applications given in this paper, it is applied by Church–Ellenberg–Farb (in preparation) [20] to counting problems in number theory and finite group theory. Representation stability is also used by Church (2012) [19] to give broad generalizations and new proofs of classical homological stability theorems for configuration spaces on oriented manifolds.} } @unpublished{LovaszWelsh, author = {L\'aszl\'o Lov\'asz}, title = {Connection Matrices}, note = {\url{http://web.cs.elte.hu/~lovasz/welsh.pdf}}, } @unpublished{GCT22, author = {GCT2022}, title = {School and Conference on Geometric Complexity Theory}, note = {\url{https://gct2022.sciencesconf.org/}}, } @article{Pittel97, author = {Pittel, Boris}, year = {1997}, month = {05}, pages = {432-488}, title = {On a Likely Shape of the Random {F}errers Diagram}, volume = {18}, journal = {Advances in Applied Mathematics} } @inproceedings{CurticapeanLN18, author = {Curticapean, Radu and Lindzey, Nathan and Nederlof, Jesper}, title = {A Tight Lower Bound for Counting {H}amiltonian Cycles via Matrix Rank}, booktitle = {Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms}, series = {SODA '18}, year = {2018}, isbn = {978-1-6119-7503-1}, location = {New Orleans, Louisiana}, pages = {1080--1099}, numpages = {20}, url = {http://dl.acm.org/citation.cfm?id=3174304.3175340}, acmid = {3175340}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, } @inproceedings{Tao07, author = {Terence Tao}, title = {Structure and Randomness in Combinatorics}, booktitle = {48th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS} 2007), October 20-23, 2007, Providence, RI, USA, Proceedings}, pages = {3--15}, publisher = {{IEEE} Computer Society}, year = {2007}, url = {https://doi.org/10.1109/FOCS.2007.68}, doi = {10.1109/FOCS.2007.68}, timestamp = {Wed, 16 Oct 2019 14:14:54 +0200}, biburl = {https://dblp.org/rec/conf/focs/Tao07.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @misc{AlweissLWZ19, title={Improved bounds for the sunflower lemma}, author={Ryan Alweiss and Shachar Lovett and Kewen Wu and Jiapeng Zhang}, year={2019}, eprint={1908.08483}, archivePrefix={arXiv}, primaryClass={math.CO} } @book{Lovett17, author = {Lovett, Shachar}, title = {Additive Combinatorics and its Applications in Theoretical Computer Science}, year = {2017}, pages = {1--55}, doi = {10.4086/toc.gs.2017.008}, publisher = {Theory of Computing Library}, number = {8}, series = {Graduate Surveys}, URL = {http://www.theoryofcomputing.org/library.html}, } @article{AlspachGSV03, author = {Brian Alspach and Heather Gavlas and Mateja Sajna and Helen Verrall}, title = {Cycle decompositions {IV:} complete directed graphs and fixed length directed cycles}, journal = {J. Comb. Theory, Ser. {A}}, volume = {103}, number = {1}, pages = {165--208}, year = {2003}, url = {https://doi.org/10.1016/S0097-3165(03)00098-0}, doi = {10.1016/S0097-3165(03)00098-0}, timestamp = {Sat, 27 May 2017 14:24:23 +0200}, biburl = {https://dblp.org/rec/bib/journals/jct/AlspachGSV03}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{Borg10, title = "Cross-intersecting families of permutations", journal = "Journal of Combinatorial Theory, Series A", volume = "117", number = "4", pages = "483 - 487", year = "2010", issn = "0097-3165", doi = "https://doi.org/10.1016/j.jcta.2009.07.003", url = "http://www.sciencedirect.com/science/article/pii/S0097316509001101", author = "Peter Borg", keywords = "Cross-intersecting families, Intersecting families, Permutations" } @article{EllisKL16, title={Stability versions of {E}rd{\H{o}}s–{K}o–{R}ado type theorems via isoperimetry}, author={David Ellis and Nathan Keller and Noam Lifshitz}, journal={Journal of the European Mathematical Society}, year={2019} } @Article{KuW17, author="Ku, Cheng Yeaw and Wong, Kok Bin", title="Eigenvalues of the matching derangement graph", journal="Journal of Algebraic Combinatorics", year="2017", month="Dec", day="14", abstract="In this paper, we derive a formula for the eigenvalues of the matching derangement graph. The formula gives an insight regarding the alternating sign conjecture for the eigenvalues of the matching derangement graph. In particular, we show that the alternating sign property holds for certain partitions.", issn="1572-9192", doi="10.1007/s10801-017-0809-8", url="https://doi.org/10.1007/s10801-017-0809-8" } @article{Lassalle98, title = {Some combinatorial conjectures for {J}ack polynomials}, journal = {Annals of Combinatorics}, volume = {2}, pages = {61-83}, year = {1998}, author = {Michel Lassalle} } @article{Lassalle09, title = {Jack polynomials and free cumulants}, journal = {Advances in Mathematics}, volume = {222}, number = {6}, pages = {2227-2269}, year = {2009}, issn = {0001-8708}, doi = {https://doi.org/10.1016/j.aim.2009.07.007}, url = {https://www.sciencedirect.com/science/article/pii/S0001870809002175}, author = {Michel Lassalle}, keywords = {Jack polynomials, Kerov polynomials, Free probability}, abstract = {We study the coefficients in the expansion of Jack polynomials in terms of power sums. We express them as polynomials in the free cumulants of the transition measure of an anisotropic Young diagram. We conjecture that such polynomials have nonnegative integer coefficients. This extends recent results about normalized characters of the symmetric group.} } @article{Stanley89, title = "Some combinatorial properties of {J}ack symmetric functions", journal = "Advances in Mathematics", volume = "77", number = "1", pages = "76 - 115", year = "1989", issn = "0001-8708", doi = "https://doi.org/10.1016/0001-8708(89)90015-7", url = "http://www.sciencedirect.com/science/article/pii/0001870889900157", author = "Richard P. Stanley" } @article{GodsilM15, author = {Chris Godsil and Karen Meagher}, title = {An algebraic proof of the {E}rd{\"o}s-{K}o-{R}ado theorem for intersecting families of perfect matchings}, journal = {ARS MATHEMATICA CONTEMPORANEA}, volume = {12}, number = {2}, year = {2016}, keywords = {Perfect matching derangement graph, independent sets, Erd?s-Ko-Rado theorem}, abstract = {In this paper we give a proof that the largest set of perfect matchings, in which any two contain a common edge, is the set of all perfect matchings that contain a fixed edge. This is a version of the famous Erd?s-Ko-Rado theorem for perfect matchings. The proof given in this paper is algebraic, we first determine the least eigenvalue of the perfect matching derangement graph and then use properties of the perfect matching polytope to prove the result.}, pages = {205--217} } @article{TanimotoIR78, author = {Tanimoto, Steven L. and Itai, Alon and Rodeh, Michael}, title = {Some Matching Problems for Bipartite Graphs}, journal = {J. ACM}, issue_date = {Oct. 1978}, volume = {25}, number = {4}, month = oct, year = {1978}, issn = {0004-5411}, pages = {517--525}, numpages = {9}, url = {http://doi.acm.org/10.1145/322092.322093}, doi = {10.1145/322092.322093}, acmid = {322093}, publisher = {ACM}, address = {New York, NY, USA}, } @article{KuW13, title = "An analogue of the {H}ilton-{M}ilner theorem for set partitions", journal = "Journal of Combinatorial Theory, Series A", volume = "120", number = "7", pages = "1508 - 1520", year = "2013", note = "", issn = "0097-3165", doi = "http://dx.doi.org/10.1016/j.jcta.2013.05.001", url = "http://www.sciencedirect.com/science/article/pii/S0097316513000824", author = "Cheng Yeaw Ku and Kok Bin Wong" } @article{Rothvoss17, author = {Rothvoss, Thomas}, title = {The Matching Polytope Has Exponential Extension Complexity}, journal = {J. ACM}, issue_date = {November 2017}, volume = {64}, number = {6}, month = sep, year = {2017}, issn = {0004-5411}, pages = {41:1--41:19}, articleno = {41}, numpages = {19}, url = {http://doi.acm.org/10.1145/3127497}, doi = {10.1145/3127497}, acmid = {3127497}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {Extension complexity, linear programming, matching}, } @article{Babai81, title={On the Order of Uniprimitive Permutation Groups}, author={L{\'a}szl{\'o} Babai}, journal={Annals of Mathematics}, year={1981}, volume={113}, pages={553} } @misc{MeagherPartial, title={An Extension of the {E}rd{\H{o}}s-{K}o-{R}ado Theorem to uniform set partitions (arXiv pre-print)}, author={Karen Meagher and Mahsa N. Shirazi and Brett Stevens}, year={2021}, url = {https://arxiv.org/abs/2108.07692}, eprint={2108.07692}, archivePrefix={arXiv}, primaryClass={math.CO} } @article{Moon82, author = {Aeryung Moon}, title = {An Analogue of the {E}rd{\H{o}}s--{K}o--{R}ado Theorem for the {H}amming Schemes ${H}(n, q)$}, journal = {J. Comb. Theory, Ser. {A}}, volume = {32}, number = {3}, pages = {386--390}, year = {1982}, url = {https://doi.org/10.1016/0097-3165(82)90054-1}, doi = {10.1016/0097-3165(82)90054-1}, timestamp = {Tue, 16 Feb 2021 14:07:30 +0100}, biburl = {https://dblp.org/rec/journals/jct/Moon82.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{HellK83, author = {Kirkpatrick, D. G. and Hell, P.}, title = {On the Complexity of General Graph Factor Problems}, journal = {SIAM Journal on Computing}, volume = {12}, number = {3}, pages = {601-609}, year = {1983}, doi = {10.1137/0212040}, URL = { https://doi.org/10.1137/0212040 }, eprint = { https://doi.org/10.1137/0212040 } } @article{Ellis11, title = "{S}tability for $t$-intersecting families of permutations", journal = "Journal of Combinatorial Theory, Series A", volume = "118", number = "1", pages = "208 - 227", year = "2011", issn = "0097-3165", doi = "https://doi.org/10.1016/j.jcta.2010.04.005", url = "http://www.sciencedirect.com/science/article/pii/S0097316510000749", author = "David Ellis", keywords = "Permutations, Intersecting, Stability" } @article{Filmus17, title={A comment on Intersecting Families of Permutations}, author={Yuval Filmus}, journal={CoRR}, year={2017}, volume={arXiv:1706.10146} } @ARTICLE{Lindzey18, author = {Nathan Lindzey}, title = "{Stability for intersecting families of perfect matchings (submitted)}", journal = {{A}r{X}iv e-prints}, archivePrefix = "arXiv", eprint = {1808.03453}, primaryClass = "math.CO", keywords = {Mathematics - Combinatorics}, year = 2018, month = aug, adsurl = {http://adsabs.harvard.edu/abs/2018arXiv180803453L}, adsnote = {Provided by the SAO/NASA Astrophysics Data System} } @Article{KuW17, author="Ku, Cheng Yeaw and Wong, Kok Bin", title="Eigenvalues of the matching derangement graph", journal="Journal of Algebraic Combinatorics", year="2017", month="Dec", day="14", abstract="In this paper, we derive a formula for the eigenvalues of the matching derangement graph. The formula gives an insight regarding the alternating sign conjecture for the eigenvalues of the matching derangement graph. In particular, we show that the alternating sign property holds for certain partitions.", issn="1572-9192", doi="10.1007/s10801-017-0809-8", url="https://doi.org/10.1007/s10801-017-0809-8" } @article{EllisFF15, title={LOW-DEGREE {B}OOLEAN FUNCTIONS ON ${S}_{n}$, WITH AN APPLICATION TO ISOPERIMETRY}, volume={5}, DOI={10.1017/fms.2017.24}, journal={Forum of Mathematics, Sigma}, publisher={Cambridge University Press}, author={Ellis, David and Filmus, Yuval and Friedgut, Ehud}, year={2017}, pages={e23}} @article{Mulmuley07, title={Geometric Complexity Theory VII: Nonstandard quantum group for the plethysm problem}, author={Ketan Mulmuley}, journal={CoRR}, year={2007}, volume={abs/0709.0749} } @article{CurticapeanLN17, author = {Radu Curticapean and Nathan Lindzey and Jesper Nederlof}, title = {A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank}, journal={CoRR}, year = {2017}, volume = {abs/1709.02311}, } @article {ScarabottiT10, author = {Scarabotti, Fabio and Tolli, Filippo}, title = {Harmonic analysis on a finite homogeneous space}, journal = {Proceedings of the London Mathematical Society}, volume = {100}, number = {2}, publisher = {Oxford University Press}, issn = {1460-244X}, url = {http://dx.doi.org/10.1112/plms/pdp027}, doi = {10.1112/plms/pdp027}, pages = {348--376}, year = {2010}, } @inproceedings{LokshtanovMS11, author = {Lokshtanov, Daniel and Marx, D\'{a}niel and Saurabh, Saket}, title = {Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal}, booktitle = {Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms}, series = {SODA '11}, year = {2011}, location = {San Francisco, California}, pages = {777--789}, numpages = {13}, url = {http://dl.acm.org/citation.cfm?id=2133036.2133097}, acmid = {2133097}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, } @inproceedings{Munemasa01, author = {Akihiro Munemasa}, title = {The injection scheme of permutations (unpublished)}, year = {2001} } @article{KuW18, author = {Ku, Cheng Yeaw and Wong, Kok Bin}, title = {Eigenvalues of the Matching Derangement Graph}, year = {2018}, issue_date = {December 2018}, publisher = {Kluwer Academic Publishers}, address = {USA}, volume = {48}, number = {4}, doi = {10.1007/s10801-017-0809-8}, abstract = {In this paper, we derive a formula for the eigenvalues of the matching derangement graph. The formula gives an insight regarding the alternating sign conjecture for the eigenvalues of the matching derangement graph. In particular, we show that the alternating sign property holds for certain partitions.}, journal = {Journal of Algebraic Combinatorics}, pages = {627–646}, numpages = {20}, keywords = {05C50, 05D99, Erd?s-Ko-Rado, 05E30, Perfect matchings, Association scheme} } @article{NovelliPS97, title={A direct bijective proof of the hook-length formula}, author={Jean-Christophe Novelli and Igor Pak and Alexander V. Stoyanovskii}, journal={Discret. Math. Theor. Comput. Sci.}, year={1997}, volume={1}, pages={53-67} } @article{Renteln21, author = {Renteln, Paul}, title = {On the Spectrum of the Perfect Matching Derangement Graph}, year = {2022}, issue_date = {Aug 2022}, publisher = {Kluwer Academic Publishers}, address = {USA}, volume = {56}, number = {1}, doi = {10.1007/s10801-021-01105-y}, abstract = {We prove the alternating sign conjecture for the perfect matching derangement graph.}, journal = {Journal of Algebraic Combinatorics}, pages = {215–228}, numpages = {14}, keywords = {05E05, Alternating sign conjecture, 05C50, Erd\H{o}s–Ko–Rado, Perfect matching, Derangement graph, 05C25, 05E10, Shifted zonal polynomials} } @inproceedings{workshop21, author = {Open Problems in Algebraic Combinatorics}, title = {University of {W}aterloo}, note = {\url{http://www.math.uwaterloo.ca/~cgodsil/quagmire/may21workshop/}}, year = {2021} } @misc{BafnaHKL20, doi = {10.48550/ARXIV.2011.04658}, url = {https://arxiv.org/abs/2011.04658}, author = {Bafna, Mitali and Hopkins, Max and Kaufman, Tali and Lovett, Shachar}, keywords = {Computational Complexity (cs.CC), Combinatorics (math.CO), FOS: Computer and information sciences, FOS: Computer and information sciences, FOS: Mathematics, FOS: Mathematics, F.2}, title = {High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games}, publisher = {arXiv}, year = {2020}, copyright = {arXiv.org perpetual, non-exclusive license} } @misc{BafnaHKL21, doi = {10.48550/ARXIV.2111.09444}, url = {https://arxiv.org/abs/2111.09444}, author = {Bafna, Mitali and Hopkins, Max and Kaufman, Tali and Lovett, Shachar}, keywords = {Discrete Mathematics (cs.DM), Computational Complexity (cs.CC), Combinatorics (math.CO), FOS: Computer and information sciences, FOS: Computer and information sciences, FOS: Mathematics, FOS: Mathematics, G.2}, title = {Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments}, publisher = {arXiv}, year = {2021}, copyright = {Creative Commons Attribution 4.0 International} } @inproceedings{DukesIL20a, author = {Dukes, Peter and Ihringer, Ferdinand and Lindzey, Nathan}, title = {On the Algebraic Combinatorics of Injections (Extended Abstract)}, booktitle = {Proceedings of the 32nd International Conference on``Formal Power Series and Algebraic Combinatorics"}, series = {FPSAC '20}, year = {2020} } @inproceedings{FilmusL22a, author = {Filmus, Yuval and Lindzey, Nathan}, title = {Harmonic Polynomials on Perfect Matchings (Extended Abstract)}, booktitle = {Proceedings of the 34th International Conference on``Formal Power Series and Algebraic Combinatorics"}, series = {FPSAC '22}, year = {2022} } @inproceedings{AMRR11, author = {Ambainis, Andris and Magnin, Lo\"{\i}ck and Roetteler, Martin and Roland, Jeremie}, title = {Symmetry-Assisted Adversaries for Quantum State Generation}, booktitle = {Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity}, series = {CCC '11}, year = {2011}, isbn = {978-0-7695-4411-3}, pages = {167--177}, numpages = {11}, url = {http://dx.doi.org/10.1109/CCC.2011.24}, doi = {10.1109/CCC.2011.24}, acmid = {2014022}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, keywords = {quantum query complexity, adversary method, strong direct product theorem, index-erasure}, } @article{Huang19, ISSN = {0003486X, 19398980}, URL = {https://www.jstor.org/stable/10.4007/annals.2019.190.3.6}, abstract = {In this paper, we show that every (2n-1 + 1)-vertex induced subgraph of the n-dimensional cube graph has maximum degree at least n. This is the best possible result, and it improves a logarithmic lower bound shown by Chung, Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.}, author = {Hao Huang}, journal = {Annals of Mathematics}, number = {3}, pages = {949--955}, publisher = {[Annals of Mathematics, Trustees of Princeton University on Behalf of the Annals of Mathematics, Mathematics Department, Princeton University]}, title = {Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture}, volume = {190}, year = {2019} } @misc{Lindzey18a, title={Intersecting Families of Perfect Matchings (ar{X}iv: 1811.06160)}, author={Nathan Lindzey}, eprint={1811.06160}, archivePrefix={arXiv}, primaryClass={math.CO} } @book{Schrijver, added-at = {2007-07-05T16:17:35.000+0200}, author = {Schrijver, A.}, biburl = {https://www.bibsonomy.org/bibtex/2496d0012f9b295acbef270a129061375/jleny}, description = {bandit problems}, interhash = {dfbeb3a87380195540f44a10e9995230}, intrahash = {496d0012f9b295acbef270a129061375}, keywords = {imported}, publisher = {Springer}, timestamp = {2007-07-05T16:17:37.000+0200}, title = {Combinatorial Optimization - Polyhedra and Efficiency}, year = 2003 } @article{AuT16, author = {Yu Hin Au and Levent Tun{\c{c}}el}, title = {A Comprehensive Analysis of Polyhedral Lift-and-Project Methods}, journal = {{SIAM} J. Discrete Math.}, volume = {30}, number = {1}, pages = {411--451}, year = {2016}, url = {https://doi.org/10.1137/130950173}, doi = {10.1137/130950173}, timestamp = {Fri, 26 May 2017 22:54:48 +0200}, biburl = {http://dblp.dagstuhl.de/rec/bib/journals/siamdm/AuT16}, bibsource = {dblp computer science bibliography, http://dblp.org} } @article{Lindzey17, title = "Erd{\"o}s--{K}o--{R}ado for Perfect Matchings", journal = "European Journal of Combinatorics", volume = "65", number = "", pages = "130 - 142", year = "2017", note = "", issn = "0195-6698", doi = "http://dx.doi.org/10.1016/j.ejc.2017.05.005", url = "http://www.sciencedirect.com/science/article/pii/S019566981730063X", author = "Nathan Lindzey", } @book{HiltonM67, title={Some Intersection Theorems for Systems of Finite Sets}, author={Hilton, A.J.W. and Milner, E.C.}, series={Research paper}, url={https://books.google.ca/books?id=e\_KaGwAACAAJ}, year={1967}, publisher={University of Calgary, Department of Mathematics} } @inbook{McDiarmid89, place={Cambridge}, series={London Mathematical Society Lecture Note Series}, title={On the method of bounded differences}, DOI={10.1017/CBO9781107359949.008}, booktitle={Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference}, publisher={Cambridge University Press}, author={McDiarmid, Colin}, editor={Siemons, J.Editor}, year={1989}, pages={148-188}, collection={London Mathematical Society Lecture Note Series}} @book{CST, title={Harmonic Analysis on Finite Groups: Representation Theory, Gelfand Pairs and Markov Chains}, author={Ceccherini-Silberstein, T. and Scarabotti, F. and Tolli, F.}, isbn={9781139470803}, series={Cambridge Studies in Advanced Mathematics}, url={https://books.google.ca/books?id=3trud4weQ3AC}, year={2008}, publisher={Cambridge University Press} } @article{DeCorteLV14, author = {Evan DeCorte and David de Laat and Frank Vallentin}, title = {Fourier Analysis on Finite Groups and the {L}ov\`asz ϑ-Number of {C}ayley Graphs}, journal = {Experimental Mathematics}, volume = {23}, number = {2}, pages = {146-152}, year = {2014}, doi = {10.1080/10586458.2014.882170}, URL = { http://dx.doi.org/10.1080/10586458.2014.882170 }, eprint = { http://dx.doi.org/10.1080/10586458.2014.882170 } } @inproceedings{CyganKN13, author = {Marek Cygan and Stefan Kratsch and Jesper Nederlof}, title = {Fast {H}amiltonicity checking via bases of perfect matchings}, booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013}, pages = {301--310}, year = {2013}, crossref = {DBLP:conf/stoc/2013}, url = {http://doi.acm.org/10.1145/2488608.2488646}, doi = {10.1145/2488608.2488646}, timestamp = {Sun, 26 May 2013 10:49:33 +0200}, biburl = {http://dblp.uni-trier.de/rec/bib/conf/stoc/CyganKN13}, bibsource = {dblp computer science bibliography, http://dblp.org} } @article{RazS95, author = {Ran Raz and Boris Spieker}, title = {On the ``Log Rank"-Conjecture in Communication Complexity}, journal = {Combinatorica}, volume = {15}, number = {4}, pages = {567--588}, year = {1995}, url = {http://dx.doi.org/10.1007/BF01192528}, doi = {10.1007/BF01192528}, timestamp = {Fri, 20 May 2011 01:00:00 +0200}, biburl = {http://dblp.uni-trier.de/rec/bib/journals/combinatorica/RazS95}, bibsource = {dblp computer science bibliography, http://dblp.org} } @article{WolkowiczS80, title = "Bounds for eigenvalues using traces", journal = "Linear Algebra and its Applications", volume = "29", number = "", pages = "471 - 506", year = "1980", note = "", issn = "0024-3795", doi = "http://dx.doi.org/10.1016/0024-3795(80)90258-X", url = "http://www.sciencedirect.com/science/article/pii/002437958090258X", author = "Henry Wolkowicz and George P.H. Styan", } @article{Vallentin09, title = "Symmetry in semidefinite programs ", journal = "Linear Algebra and its Applications ", volume = "430", number = "1", pages = "360 - 369", year = "2009", note = "", issn = "0024-3795", doi = "http://dx.doi.org/10.1016/j.laa.2008.07.025", url = "//www.sciencedirect.com/science/article/pii/S0024379508003753", author = "Frank Vallentin", keywords = "Semidefinite programming", keywords = "Block diagonalization", keywords = "Terwilliger algebra", keywords = "Binary Hamming scheme", keywords = "Hahn polynomials " } @book{JamesKerber, title={The Representation Theory of the Symmetric Group}, author={James, G.D. and Kerber, A.}, isbn={9780521302364}, lccn={gb85036945}, series={Encyclopedia of Mathematics and its Applications}, url={https://books.google.ca/books?id=yWa\_RaqkLUsC}, year={1984}, publisher={Cambridge University Press} } @manual{sage, Key = {Sage}, Author = {W.\thinspace{}A. Stein and others}, Organization = {The Sage Development Team}, Title = {{S}age {M}athematics {S}oftware ({V}ersion 10.0)}, note = {{\tt http://www.sagemath.org}}, Year = {2023}, } @inproceedings{MulmuleyVV87, author = {Mulmuley, Ketan and Vazirani, Umesh V. and Vazirani, Vijay V.}, title = {Matching is As Easy As Matrix Inversion}, booktitle = {Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing}, series = {STOC '87}, year = {1987}, isbn = {0-89791-221-7}, location = {New York, New York, USA}, pages = {345--354}, numpages = {10}, url = {http://doi.acm.org/10.1145/28395.383347}, doi = {10.1145/28395.383347}, acmid = {383347}, publisher = {ACM}, address = {New York, NY, USA}, } @book{GareyJohnson, author = {Garey, Michael R. and Johnson, David S.}, title = {Computers and Intractability: A Guide to the Theory of NP-Completeness}, year = {1979}, isbn = {0716710447}, publisher = {W. H. Freeman \& Co.}, address = {New York, NY, USA}, } @inproceedings{ValiantV85, author = {Valiant, L G and Vazirani, V V}, title = {NP is As Easy As Detecting Unique Solutions}, booktitle = {Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing}, series = {STOC '85}, year = {1985}, isbn = {0-89791-151-2}, location = {Providence, Rhode Island, USA}, pages = {458--463}, numpages = {6}, url = {http://doi.acm.org/10.1145/22145.22196}, doi = {10.1145/22145.22196}, acmid = {22196}, publisher = {ACM}, address = {New York, NY, USA}, } @INPROCEEDINGS{ArvindM08, author = {V. Arvind and Partha Mukhopadhyay}, title = {Derandomizing the isolation lemma and lower bounds for circuit size}, booktitle = {in Proc. of APPROX/RANDOM 2008, ser. LNCS}, year = {}, pages = {276--289} } @incollection{BjorklundH14, year={2014}, isbn={978-3-662-43947-0}, booktitle={Automata, Languages, and Programming}, volume={8572}, series={Lecture Notes in Computer Science}, editor={Esparza, Javier and Fraigniaud, Pierre and Husfeldt, Thore and Koutsoupias, Elias}, doi={10.1007/978-3-662-43948-7_18}, title={Shortest Two Disjoint Paths in Polynomial Time}, url={http://dx.doi.org/10.1007/978-3-662-43948-7_18}, publisher={Springer Berlin Heidelberg}, author={Björklund, Andreas and Husfeldt, Thore}, pages={211-222}, language={English} } @article{VerdiereS11, author = {Verdi\`{e}re, \'{E}ric Colin De and Schrijver, Alexander}, title = {Shortest Vertex-disjoint Two-face Paths in Planar Graphs}, journal = {ACM Trans. Algorithms}, issue_date = {March 2011}, volume = {7}, number = {2}, month = mar, year = {2011}, issn = {1549-6325}, pages = {19:1--19:12}, articleno = {19}, numpages = {12}, url = {http://doi.acm.org/10.1145/1921659.1921665}, doi = {10.1145/1921659.1921665}, acmid = {1921665}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {Algorithm, disjoint paths, planar graph, shortest path}, } @article{KawarabayashiKR12, title = "The disjoint paths problem in quadratic time ", journal = "Journal of Combinatorial Theory, Series B ", volume = "102", number = "2", pages = "424 - 435", year = "2012", note = "", issn = "0095-8956", doi = "http://dx.doi.org/10.1016/j.jctb.2011.07.004", url = "http://www.sciencedirect.com/science/article/pii/S0095895611000712", author = "Ken-ichi Kawarabayashi and Yusuke Kobayashi and Bruce Reed", keywords = "Disjoint paths", keywords = "Quadratic time", keywords = "Graph minor", keywords = "Tree-width " } @article{KobayashiS10, author = {Kobayashi, Yusuke and Sommer, Christian}, title = {On Shortest Disjoint Paths in Planar Graphs}, journal = {Discret. Optim.}, issue_date = {November, 2010}, volume = {7}, number = {4}, month = nov, year = {2010}, issn = {1572-5286}, pages = {234--245}, numpages = {12}, url = {http://dx.doi.org/10.1016/j.disopt.2010.05.002}, doi = {10.1016/j.disopt.2010.05.002}, acmid = {2296847}, publisher = {Elsevier Science Publishers B. V.}, address = {Amsterdam, The Netherlands, The Netherlands}, keywords = {05C85, 68R10, 90C27, 90C35, Disjoint paths, Minimum cost flow, Objective function, Planar graph, Shortest path}, } @inproceedings{LindzeyM13, author = {Nathan Lindzey and Ross M. McConnell}, title = {On Lekkerkerker Boland Subgraphs and Tucker Submatrices}, booktitle = {WG13: 39th International Workshop on Graph-Theoretic Concepts in Computer Science}, year = {2013} } @inproceedings{Lindzey14, author = {Nathan Lindzey}, title = {Faster Graph Algorithms via Switching Classes}, booktitle = {IWOCA14: 25th International Workshop on Combinatorial Algorithms}, year = {2014} } @inproceedings{KralovicK05, author = {Kr\'{a}lovi\v{c}, Rastislav and Kr\'{a}lovi\v{c}, Richard}, title = {On Semi-perfect 1-factorizations}, booktitle = {Proceedings of the 12th International Conference on Structural Information and Communication Complexity}, series = {SIROCCO'05}, year = {2005}, isbn = {3-540-26052-8, 978-3-540-26052-3}, location = {Mont Saint-Michel, France}, pages = {216--230}, numpages = {15}, url = {http://dx.doi.org/10.1007/11429647_18}, doi = {10.1007/11429647_18}, acmid = {2156006}, publisher = {Springer-Verlag}, address = {Berlin, Heidelberg}, } @inproceedings{McConnell97, author = {Ross M. McConnell}, title = {Complement-Equivalence Classes on Graphs}, booktitle = {Structures in Logic and Computer Science}, year = {1997}, pages = {174-191}, ee = {http://dx.doi.org/10.1007/3-540-63246-8_11}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{GolumbicWL14, author = {Martin Charles Golumbic and Nirit Lefel Weingarten and Vincent Limouzy}, title = {Co-TT graphs and a characterization of split co-TT graphs}, journal = {Discrete Applied Mathematics}, volume = {165}, pages = {168--174}, year = {2014}, url = {http://dx.doi.org/10.1016/j.dam.2012.11.014}, doi = {10.1016/j.dam.2012.11.014}, timestamp = {Fri, 01 Aug 2014 14:42:24 +0200}, biburl = {http://dblp.uni-trier.de/rec/bib/journals/dam/GolumbicWL14}, bibsource = {dblp computer science bibliography, http://dblp.org} } @article{LekkerkerkerB62, title = "Representation of finite graphs by a set of intervals on the real line ", journal = "Fund. Math.", volume = "51", pages = " 45-64 ", year = "1962", author = "C. Lekkerkerker and D. Boland" } @inproceedings{BenGHPSV04, author = {Ben-Sasson, Eli and Goldreich, Oded and Harsha, Prahladh and Sudan, Madhu and Vadhan, Salil}, title = {Robust Pcps of Proximity, Shorter Pcps and Applications to Coding}, year = {2004}, isbn = {1581138520}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/1007352.1007361}, doi = {10.1145/1007352.1007361}, booktitle = {Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing}, pages = {1–10}, numpages = {10}, keywords = {locally testable codes, locally decodable codes, probabilistically checkable proofs, PCP, property testing}, location = {Chicago, IL, USA}, series = {STOC ’04} } @article{MadhuR96, author = {Rubinfeld, Ronitt and Sudan, Madhu}, title = {Robust Characterizations of Polynomials With Applications to Program Testing}, year = {1996}, issue_date = {February 1996}, publisher = {Society for Industrial and Applied Mathematics}, address = {USA}, volume = {25}, number = {2}, issn = {0097-5397}, url = {https://doi.org/10.1137/S0097539793255151}, doi = {10.1137/S0097539793255151}, journal = {SIAM J. Comput.}, month = feb, pages = {252–271}, numpages = {20}, keywords = {program correctness, low-degree polynomial testing, coding theory} } @INPROCEEDINGS{FalikF11, author={D. {Falik} and E. {Friedgut}}, booktitle={2011 IEEE 52nd Annual Symposium on Foundations of Computer Science}, title={An Algebraic Proof of a Robust Social Choice Impossibility Theorem}, year={2011}, volume={}, number={}, pages={413-422},} @inproceedings{AlweissLWZ20, author = {Ryan Alweiss and Shachar Lovett and Kewen Wu and Jiapeng Zhang}, editor = {Konstantin Makarychev and Yury Makarychev and Madhur Tulsiani and Gautam Kamath and Julia Chuzhoy}, title = {Improved bounds for the sunflower lemma}, booktitle = {Proccedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020}, pages = {624--630}, publisher = {{ACM}}, year = {2020}, url = {https://doi.org/10.1145/3357713.3384234}, doi = {10.1145/3357713.3384234}, timestamp = {Tue, 09 Jun 2020 13:03:16 +0200}, biburl = {https://dblp.org/rec/conf/stoc/AlweissL0Z20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{GolovachHLMSSS17, author = {Petr A. Golovach and Pinar Heggernes and Nathan Lindzey and Ross M. McConnell and Vin{\'{\i}}cius Fernandes dos Santos and Jeremy P. Spinrad and Jayme Luiz Szwarcfiter}, title = {On recognition of threshold tolerance graphs and their complements}, journal = {Discret. Appl. Math.}, volume = {216}, pages = {171--180}, year = {2017}, url = {https://doi.org/10.1016/j.dam.2015.01.034}, doi = {10.1016/j.dam.2015.01.034}, timestamp = {Thu, 20 Feb 2020 15:47:02 +0100}, biburl = {https://dblp.org/rec/journals/dam/GolovachHLMSSS17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{GolovachHLMSS14, author = {Petr A. Golovach and Pinar Heggernes and Nathan Lindzey and Ross M. McConnell and Vin{\'{\i}}cius Fernandes dos Santos and Jeremy P. Spinrad}, editor = {Dieter Kratsch and Ioan Todinca}, title = {Recognizing Threshold Tolerance Graphs in O(n\({}^{\mbox{2}}\)) Time}, booktitle = {Graph-Theoretic Concepts in Computer Science - 40th International Workshop, {WG} 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers}, series = {Lecture Notes in Computer Science}, volume = {8747}, pages = {214--224}, publisher = {Springer}, year = {2014}, url = {https://doi.org/10.1007/978-3-319-12340-0\_18}, doi = {10.1007/978-3-319-12340-0\_18}, timestamp = {Tue, 14 May 2019 10:00:40 +0200}, biburl = {https://dblp.org/rec/conf/wg/GolovachHLMSS14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{GolovachHLMS14, title = "Efficient Recognition of Threshold Tolerance Graphs", journal = "arxiv.org", volume = "", pages = " ", year = "2014", author = "P.A. Golovach and P. Heggernes and N. Lindzey and R.M. McConnell and J.L. Szwarcfiter" } @article{HellH05, author = {Hell, Pavol and Huang, Jing}, title = {Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs}, journal = {SIAM J. Discret. Math.}, issue_date = {2005}, volume = {18}, number = {3}, month = mar, year = {2005}, issn = {0895-4801}, pages = {554--570}, numpages = {17}, url = {http://dx.doi.org/10.1137/S0895480103430259}, doi = {10.1137/S0895480103430259}, acmid = {1055336}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, keywords = {bipartite permutation graphs, bipartite trapezoid graphs, certifying algorithms, forbidden subgraph characterizations, lexicographic breadth first search, proper circular arc graphs, proper interval bigraphs, proper interval graphs, recognition algorithms} } @article{MonmaRT88, author = {Clyde L. Monma and Bruce Reed and William T. Trotter}, title = {Threshold tolerance graphs}, journal = {Journal of Graph Theory}, volume = {12}, number = {3}, year = {1988}, pages = {343-362}, ee = {http://dx.doi.org/10.1002/jgt.3190120307}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{HammerM85, author = {Peter L. Hammer and N.V.R. Mahadev}, title = {Intershold Graphs}, journal = {Utilitas Mathematica}, volume = {27}, year = {1985}, pages = {207-215}, } @article{Edmonds65, author = {Edmonds, Jack}, citeulike-article-id = {9559019}, citeulike-linkout-0 = {http://dx.doi.org/10.4153/CJM-1965-045-4}, doi = {10.4153/CJM-1965-045-4}, journal = {Canadian Journal of Mathematics}, keywords = {algorithms, combinatorics, graph}, month = feb, pages = {449--467}, posted-at = {2011-07-19 07:36:35}, priority = {5}, title = {{Paths, trees, and flowers}}, url = {http://dx.doi.org/10.4153/CJM-1965-045-4}, volume = {17}, year = {1965} } @article{GabowT91, author = {Harold N. Gabow and Robert Endre Tarjan}, title = {Faster Scaling Algorithms for General Graph-Matching Problems}, journal = {J. ACM}, volume = {38}, number = {4}, year = {1991}, pages = {815-853}, ee = {http://doi.acm.org/10.1145/115234.115366}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{ItoY98, author = {Hiro Ito and Mitsuo Yokoyama}, title = {Linear Time Algorithms for Graph Search and Connectivity Determination on Complement Graphs}, journal = {Inf. Process. Lett.}, volume = {66}, number = {4}, year = {1998}, pages = {209-213}, ee = {http://dx.doi.org/10.1016/S0020-0190(98)00071-4}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{LindzeyO13, author = {Benson Joeris and Nathan Lindzey and Ross M. McConnell and Nissa Osheim}, title = {Simple DFS for Partially Complemented Digraphs}, year = {2013}, journal = {Inf. Process. Lett. (submitted and available on arxiv.org)}, } @incollection{LinSS07, year={2007}, isbn={978-3-540-74838-0}, booktitle={Graph-Theoretic Concepts in Computer Science}, volume={4769}, series={Lecture Notes in Computer Science}, editor={Brandstädt, Andreas and Kratsch, Dieter and Müller, Haiko}, doi={10.1007/978-3-540-74839-7_24}, title={Proper Helly Circular-Arc Graphs}, url={http://dx.doi.org/10.1007/978-3-540-74839-7_24}, publisher={Springer Berlin Heidelberg}, keywords={algorithms; forbidden subgraphs; Helly circular-arc graphs; proper circular-arc graphs; unit circular-arc graphs}, author={Lin, MinChih and Soulignac, FranciscoJ. and Szwarcfiter, JaymeL.}, pages={248-257} } @article{Tucker71, author = {Alan Tucker}, title = {Matrix characterizations of circular-arc graphs}, year = {1971}, pages = {535-545}, journal = {Pacific J. Math., 39}, } @inproceedings{KarpinskiS09, author = {Marek Karpinski and Warren Schudy}, title = {Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems}, booktitle = {STOC}, year = {2009}, pages = {313-322}, ee = {http://doi.acm.org/10.1145/1536414.1536458}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{RothV08, author = {Ron M. Roth and Krishnamurthy Viswanathan}, title = {On the Hardness of Decoding the Gale-Berlekamp Code}, journal = {IEEE Transactions on Information Theory}, volume = {54}, number = {3}, year = {2008}, pages = {1050-1060}, ee = {http://dx.doi.org/10.1109/TIT.2007.915716}, bibsource = {DBLP, http://dblp.uni-trier.de} } @phdthesis{Vegh10, author = {Laszlo Vegh}, title = {Connectivity Augmentation Algorithms}, school = {Eotvos Lorand University}, year = {2010} } @phdthesis{OkazakiPhD, author = {Satomi Okazaki}, title = {Cycle Types of Permutations with Restricted Positions and a Characterization of a New Class of Interval Orders}, school = {Massachusetts Institute of Technology}, year = {1996} } @mastersthesis{TessierMS, author = {Rebecca Tessier}, title = {Path Tableaux and the Combinatorics of the Immanant Function}, school = {University of Waterloo}, year = {2013} } @article{Pate92, author = {Pate, Thomas H.}, title = {Immanant Inequalities and Partition Node Diagrams}, journal = {Journal of the London Mathematical Society}, volume = {s2-46}, number = {1}, pages = {65-80}, doi = {https://doi.org/10.1112/jlms/s2-46.1.65}, url = {https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s2-46.1.65}, eprint = {https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/jlms/s2-46.1.65}, year = {1992} } @article{HopcroftK73, author = {John E. Hopcroft and Richard M. Karp}, title = {An n$^{\mbox{5/2}}$ Algorithm for Maximum Matchings in Bipartite Graphs}, journal = {SIAM J. Comput.}, volume = {2}, number = {4}, year = {1973}, pages = {225-231}, ee = {http://dx.doi.org/10.1137/0202019}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{JelinkovaSHK11, author = {Eva Jel\'{\i}nkov{\'a} and Ondrej Such{\'y} and Petr Hlinen{\'y} and Jan Kratochv\'{\i}l}, title = {Parameterized Problems Related to Seidel's Switching}, journal = {Discrete Mathematics {\&} Theoretical Computer Science}, volume = {13}, number = {2}, year = {2011}, pages = {19-44}, } @article{KaoOT98, author = {Ming-Yang Kao and Neill Occhiogrosso and Shang-Hua Teng}, title = {Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs}, journal = {J. Comb. Optim.}, volume = {2}, number = {4}, year = {1998}, pages = {351-359}, ee = {http://dx.doi.org/10.1023/A:1009720402326}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{ChengW86, title = "Switching classes of directed graphs ", journal = "Journal of Combinatorial Theory, Series B ", volume = "40", number = "2", pages = "169 - 186", year = "1986", note = "", issn = "0095-8956", doi = "http://dx.doi.org/10.1016/0095-8956(86)90075-4", url = "http://www.sciencedirect.com/science/article/pii/0095895686900754", author = "Ying Cheng and Albert L Wells Jr." } @article{CheriyanM96, author = {Joseph Cheriyan and Kurt Mehlhorn}, title = {Algorithms for Dense Graphs and Networks on the Random Access Computer}, journal = {Algorithmica}, volume = {15}, number = {6}, year = {1996}, pages = {521-549}, ee = {http://dx.doi.org/10.1007/BF01940880}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{FederM95, author = {Tom{\'a}s Feder and Rajeev Motwani}, title = {Clique Partitions, Graph Compression and Speeding-Up Algorithms}, journal = {J. Comput. Syst. Sci.}, volume = {51}, number = {2}, year = {1995}, pages = {261-272}, ee = {http://dx.doi.org/10.1006/jcss.1995.1065}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{Seidel76, author = {J. J. Seidel}, title = {A survey of two-graphs}, journal = {Discrete Mathematics {\&} Theoretical Computer Science}, booktitle = {Colloquio Internazionale sulle Teorie Combinatorie}, year = {1976}, pages = {481-511}, } @inproceedings{BalasN93, author= "E. Balas and W. Niehaus", title= "Finding large cliques in arbitrary graphs by bipartite matching", booktitle="Cliques, Colouring, and Satisfiability, Second DIMACS Implementations Challenge, Oct. 11-13, 1993", editor="Davis S. Johnson and Michael A. Trick", volume="26", series="DIMACS Series in Discrete Mathematics and Theoretical Computer Science", year="1996", publisher="American Mathematical Society", pages="29--52" } @article{FujiKN69, author = {Fujii, M. and Kasami, T. and Ninomiya, K.}, title = {Optimal Sequencing of Two Equivalent Processors}, journal = {SIAM Journal on Applied Mathematics}, volume = {17}, number = {4}, pages = {784-789}, year = {1969}, doi = {10.1137/0117070}, URL = {http://epubs.siam.org/doi/abs/10.1137/0117070}, eprint = {http://epubs.siam.org/doi/pdf/10.1137/0117070} } @article{DahlhausGM02, author = {Elias Dahlhaus and Jens Gustedt and Ross M. McConnell}, title = {Partially Complemented Representations of Digraphs}, journal = {Discrete Mathematics {\&} Theoretical Computer Science}, volume = {5}, number = {1}, year = {2002}, pages = {147-168}, ee = {http://dmtcs.loria.fr/volumes/abstracts/dm050110.abs.html}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{McConnellS99, author = {Ross M. McConnell and Jeremy Spinrad}, title = {Modular decomposition and transitive orientation}, journal = {Discrete Mathematics}, volume = {201}, number = {1-3}, year = {1999}, pages = {189-241}, ee = {http://dx.doi.org/10.1016/S0012-365X(98)00319-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{MicaliV80, author = {Silvio Micali and Vijay V. Vazirani}, title = {An O(sqrt(n) m) Algorithm for Finding Maximum Matching in General Graphs}, booktitle = {FOCS}, year = {1980}, pages = {17-27}, ee = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1980.12}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{McConnell03, author = {Ross M. McConnell}, title = {Linear-Time Recognition of Circular-Arc Graphs}, journal = {Algorithmica}, volume = {37}, number = {2}, year = {2003}, pages = {93-147}, ee = {http://dx.doi.org/10.1007/s00453-003-1032-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{HabibMPV00, author = {Michel Habib and Ross M. McConnell and Christophe Paul and Laurent Viennot}, title = {Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing}, journal = {Theor. Comput. Sci.}, volume = {234}, number = {1-2}, year = {2000}, pages = {59-84}, ee = {http://dx.doi.org/10.1016/S0304-3975(97)00241-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{Spinrad93, author = {Jeremy Spinrad}, title = {Doubly Lexical Ordering of Dense 0 - 1 Matrices}, journal = {Inf. Process. Lett.}, volume = {45}, number = {5}, year = {1993}, pages = {229-235}, ee = {http://dx.doi.org/10.1016/0020-0190(93)90209-R}, bibsource = {DBLP, http://dblp.uni-trier.de} } @book{AHU74, author = "Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.", title = "The Design and Analysis of Computer Algorithms", year = "1974", publisher = "Addison-Wesley", address = "Reading, Massachusetts" } @article{HellH04, author = {Pavol Hell and Jing Huang}, title = {Interval bigraphs and circular arc graphs}, journal = {Journal of Graph Theory}, volume = {46}, number = {4}, year = {2004}, pages = {313-327}, ee = {http://dx.doi.org/10.1002/jgt.20006}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {GolumbicG78, author = {Golumbic, Martin Charles and Goss, Clinton F.}, title = {Perfect Elimination and Chordal Bipartite Graphs}, journal = {Journal of Graph Theory}, volume = {2}, number = {2}, publisher = {Wiley Subscription Services, Inc., A Wiley Company}, issn = {1097-0118}, url = {http://dx.doi.org/10.1002/jgt.3190020209}, doi = {10.1002/jgt.3190020209}, pages = {155--163}, year = {1978}, } @article{Lubiw87, author = {Anna Lubiw}, title = {Doubly Lexical Orderings of Matrices}, journal = {SIAM J. Comput.}, volume = {16}, number = {5}, year = {1987}, pages = {854-879}, ee = {http://dx.doi.org/10.1137/0216057}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{PaigeT87, author = {Robert Paige and Robert Endre Tarjan}, title = {Three Partition Refinement Algorithms}, journal = {SIAM J. Comput.}, volume = {16}, number = {6}, year = {1987}, pages = {973-989}, ee = {http://dx.doi.org/10.1137/0216062}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{RoseTL76, author = {Donald J. Rose and Robert Endre Tarjan and George S. Lueker}, title = {Algorithmic Aspects of Vertex Elimination on Graphs}, journal = {SIAM J. Comput.}, volume = {5}, number = {2}, year = {1976}, pages = {266-283}, ee = {http://dx.doi.org/10.1137/0205021}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{GolumbicMT84, title = "Tolerance graphs ", journal = "Discrete Applied Mathematics ", volume = "9", number = "2", pages = "157 - 170", year = "1984", note = "", issn = "0166-218X", doi = "http://dx.doi.org/10.1016/0166-218X(84)90016-7", url = "http://www.sciencedirect.com/science/article/pii/0166218X84900167", author = "Martin Charles Golumbic and Clyde L. Monma and William T. Trotter Jr." } @book{GolumbicTTolerance, title={Tolerance Graphs}, author={Golumbic, M.C. and Trenk, A.N.}, isbn={9780521827584}, lccn={2004300266}, series={Cambridge Studies in Advanced Mathematics}, url={http://books.google.com/books?id=nlE3nvXba-0C}, year={2004}, publisher={Cambridge University Press} } @book{ODonnell14, title={Analysis of Boolean Functions}, author={Ryan O'Donnell}, year={2014}, publisher={Cambridge University Press} } @incollection{ChvatalH77, title = "Aggregation of Inequalities in Integer Programming ", editor = "P.L. Hammer, E.L. Johnson, B.H. Korte and G.L. Nemhauser", booktitle = "Studies in Integer Programming", publisher = "Elsevier", year = "1977", volume = "1", pages = "145 - 162", series = "Annals of Discrete Mathematics ", issn = "0167-5060", doi = "http://dx.doi.org/10.1016/S0167-5060(08)70731-3", url = "http://www.sciencedirect.com/science/article/pii/S0167506008707313", author = "Vaclav Chvatal and Peter L. Hammer" } @incollection{GolumbicS02, year={2002}, isbn={978-3-540-43865-6}, booktitle={Artificial Intelligence, Automated Reasoning, and Symbolic Computation}, volume={2385}, series={Lecture Notes in Computer Science}, editor={Calmet, Jacques and Benhamou, Belaid and Caprotti, Olga and Henocque, Laurent and Sorge, Volker}, doi={10.1007/3-540-45470-5_19}, title={Coloring Algorithms for Tolerance Graphs: Reasoning and Scheduling with Interval Constraints}, url={http://dx.doi.org/10.1007/3-540-45470-5_19}, publisher={Springer Berlin Heidelberg}, keywords={AI; OR applications; reasoning; coloring tolerance graphs}, author={Golumbic, Martin Charles and Siani, Assaf}, pages={196-207}, language={English} } @article{BoothL76, title = "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms ", journal = "Journal of Computer and System Sciences ", volume = "13", number = "3", pages = "335 - 379", year = "1976", note = "", issn = "0022-0000", doi = "http://dx.doi.org/10.1016/S0022-0000(76)80045-1", url = "http://www.sciencedirect.com/science/article/pii/S0022000076800451", author = "Kellogg S. Booth and George S. Lueker" } @INPROCEEDINGS{KaplanN06, author = {Haim Kaplan and Yahav Nussbaum}, title = {Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs}, booktitle = {Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science}, year = {2006}, pages = {289--300} } @article{LinSS13, title = "Normal Helly circular-arc graphs and its subclasses ", journal = "Discrete Applied Mathematics ", volume = "161", number = "7–8", pages = "1037 - 1059", year = "2013", note = "", issn = "0166-218X", doi = "http://dx.doi.org/10.1016/j.dam.2012.11.005", url = "http://www.sciencedirect.com/science/article/pii/S0166218X12004295", author = "Min Chih Lin and Francisco J. Soulignac and Jayme L. Szwarcfiter", keywords = "Helly circular-arc graphs", keywords = "Proper circular-arc graphs", keywords = "Unit circular-arc graphs", keywords = "Normal circular-arc graphs " } @book{McKee, title={Topics in Intersection Graph Theory}, author={McKee, T.A. and McMorris, F.R.}, isbn={9780898714302}, lccn={98031901}, series={Monographs on Discrete Mathematics and Applications}, url={http://books.google.com/books?id=5sFBPZnpiCkC}, year={1999}, publisher={Society for Industrial and Applied Mathematics} } @article{LinS09, title = "Characterizations and recognition of circular-arc graphs and subclasses: A survey ", journal = "Discrete Mathematics ", volume = "309", number = "18", pages = "5618 - 5635", year = "2009", note = "Combinatorics 2006, A Meeting in Celebration of Pavol Hell’s 60th Birthday (May 1–5, 2006) ", issn = "0012-365X", doi = "http://dx.doi.org/10.1016/j.disc.2008.04.003", url = "http://www.sciencedirect.com/science/article/pii/S0012365X08002161", author = "Min Chih Lin and Jayme L. Szwarcfiter", keywords = "Algorithms", keywords = "Circular-arc graphs", keywords = "Co-bipartite circular-arc graphs", keywords = "Helly circular-arc graphs", keywords = "Proper circular-arc graphs", keywords = "Unit circular-arc graphs " } @article{Roberts71, title = "On the compatibility between a graph and a simple order ", journal = "Journal of Combinatorial Theory, Series B ", volume = "11", number = "1", pages = "28 - 38", year = "1971", note = "", issn = "0095-8956", doi = "http://dx.doi.org/10.1016/0095-8956(71)90010-4", url = "http://www.sciencedirect.com/science/article/pii/0095895671900104", author = "Fred S Roberts" } @article{Farber83, title = "Characterizations of strongly chordal graphs ", journal = "Discrete Mathematics ", volume = "43", number = "2–3", pages = "173 - 189", year = "1983", note = "", issn = "0012-365X", doi = "http://dx.doi.org/10.1016/0012-365X(83)90154-1", url = "http://www.sciencedirect.com/science/article/pii/0012365X83901541", author = "Martin Farber" } @article{GodsilM10, year={2010}, issn={0218-0006}, journal={Annals of Combinatorics}, volume={13}, number={4}, doi={10.1007/s00026-009-0035-8}, title={Multiplicity-Free Permutation Representations of the Symmetric Group}, url={http://dx.doi.org/10.1007/s00026-009-0035-8}, publisher={SP Birkhäuser Verlag Basel}, keywords={20C30; association schemes; multiplicity-free representations; finite symmetric group}, author={Godsil, Chris and Meagher, Karen}, pages={463-490}, language={English} } @article{Birkhoff46, author = {Garrett Birkhoff}, title = {Tres observaciones sobre el algebra lineal}, journal = {Univ. Nac. Tucumán. Revista A.}, volume = {5}, year = {1946} } @article{MeagherM05, author = {Karen Meagher and Lucia Moura}, title = {Erd{\"o}s-{K}o-{R}ado theorems for uniform set-partition systems}, journal = {Electr. J. Comb.}, pages = {Research Paper 40, 12 pp. (electronic)}, volume = {12}, number = {1}, year = {2005}, ee = {http://www.combinatorics.org/Volume_12/Abstracts/v12i1r40.html}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{GodsilM09, author = {Chris D. Godsil and Karen Meagher}, title = {A new proof of the {E}rd{\H{o}}s--{K}o--{R}ado theorem for intersecting families of permutations}, journal = {Eur. J. Comb.}, volume = {30}, number = {2}, year = {2009}, pages = {404-414}, ee = {http://dx.doi.org/10.1016/j.ejc.2008.05.006}, bibsource = {DBLP, http://dblp.uni-trier.de} } @book{Berge89, added-at = {2010-08-24T18:51:49.000+0200}, author = {Berge, C.}, biburl = {http://www.bibsonomy.org/bibtex/2b7be40a6321a1e32ab7fa073bf0371fb/enitsirhc}, description = {graph mining }, interhash = {19027f5b33bf923fac180c3011a7616f}, intrahash = {b7be40a6321a1e32ab7fa073bf0371fb}, keywords = {hypergraph mathematics}, publisher = {North-Holland}, timestamp = {2010-08-24T18:51:49.000+0200}, title = {Hypergraphs: Combinatorics of Finite Sets}, year = 1989 } @article{ErdosKR61, author = {Erd{\H{o}}s, P. and Ko, Chao and Rado, R.}, title = {INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS}, volume = {12}, number = {1}, pages = {313-320}, year = {1961}, doi = {10.1093/qmath/12.1.313}, URL = {http://qjmath.oxfordjournals.org/content/12/1/313.short}, eprint = {http://qjmath.oxfordjournals.org/content/12/1/313.full.pdf+html}, journal = {The Quarterly Journal of Mathematics} } @article{FranklW86, title = "The {E}rd{\H{o}}s--{K}o--{R}ado theorem for vector spaces ", journal = "Journal of Combinatorial Theory, Series A ", volume = "43", number = "2", pages = "228 - 236", year = "1986", note = "", issn = "0097-3165", doi = "http://dx.doi.org/10.1016/0097-3165(86)90063-4", url = "http://www.sciencedirect.com/science/article/pii/0097316586900634", author = "P. Frankl and R.M. Wilson" } @misc{Pak22, author = {Pak, Igor}, title = {What is a combinatorial interpretation?}, journal={arXiv: Combinatorics}, year = {2022}, eprint = {2209.06142} } @book{Comtet74, added-at = {2010-10-02T18:22:22.000+0200}, address = {Dordrecht}, author = {Comtet, L.}, biburl = {https://www.bibsonomy.org/bibtex/281cdfe0e458947489142d959a37c4d1f/brouder}, interhash = {9360d5ecc6667be9712d85e8e638f851}, intrahash = {81cdfe0e458947489142d959a37c4d1f}, keywords = {imported}, publisher = {Reidel}, timestamp = {2010-10-02T18:22:25.000+0200}, title = {Advanced Combinatorics}, year = 1974 } @article{OkounkovO97, author = {Okounkov, A. and Olshanski, G.}, date-added = {2011-11-14 17:19:39 +0000}, date-modified = {2011-11-14 17:20:33 +0000}, fjournal = {Mathematical Research Letters}, journal = {Mathematical Research Letters}, number = {1}, pages = {69--78}, title = {Shifted {J}ack polynomials, binomial formula, and applications}, volume = {4}, year = {1997} } @article{Feray06, author = {Féray, Valentin}, year = {2006}, month = {01}, pages = {453-461}, title = {Stanley’s Formula for Characters of the Symmetric Group}, volume = {13}, journal = {Annals of Combinatorics}, doi = {10.1007/s00026-009-0038-5} } @article{Stanley06, author = {Stanley, Richard}, year = {2006}, journal={arXiv: Combinatorics}, title = {A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group} } @article{Sniady19, title = {Asymptotics of {J}ack characters}, journal = {Journal of Combinatorial Theory, Series A}, volume = {166}, pages = {91-143}, year = {2019}, issn = {0097-3165}, doi = {https://doi.org/10.1016/j.jcta.2019.02.020}, url = {https://www.sciencedirect.com/science/article/pii/S0097316519300354}, author = {Piotr Śniady}, keywords = {Jack polynomials, Jack characters, Oriented maps, Free cumulants, Kerov polynomials, Kerov–Lassalle polynomials, Structure coefficients, Approximate factorization of characters}, abstract = {Jack characters are a one-parameter deformation of the characters of the symmetric groups; a deformation given by the coefficients in the expansion of Jack symmetric functions in the basis of power-sum symmetric functions. We study Jack characters from the viewpoint of the asymptotic representation theory. In particular, we give explicit formulas for their asymptotically top-degree part, in terms of bicolored oriented maps with an arbitrary face structure. We also study their multiplicative structure and their structure constants and we prove that they fulfill approximate factorization property, a convenient tool for proving Gaussianity of fluctuations of random Young diagrams.} } @Article{FerayS11, Author = {F{\'e}ray, Valentin and {\'S}niady, Piotr}, Title = {Asymptotics of characters of symmetric groups related to {Stanley} character formula}, FJournal = {Annals of Mathematics. Second Series}, Journal = {Ann. Math. (2)}, ISSN = {0003-486X}, Volume = {173}, Number = {2}, Pages = {887--906}, Year = {2011}, Language = {English}, DOI = {10.4007/annals.2011.173.2.6}, Keywords = {05E10,05E15,20C30}, zbMATH = {5960673}, Zbl = {1229.05276} } @article{Lassalle07, author = {Lassalle, Michel}, year = {2007}, month = {04}, pages = {}, title = {Positivity conjecture for {J}ack polynomials}, volume = {15}, journal = {Mathematical Research Letters}, doi = {10.4310/MRL.2008.v15.n4.a6} } @article{Rattan08, title = {Stanley's character polynomials and coloured factorisations in the symmetric group}, journal = {Journal of Combinatorial Theory, Series A}, volume = {115}, number = {4}, pages = {535-546}, year = {2008}, issn = {0097-3165}, doi = {https://doi.org/10.1016/j.jcta.2007.06.008}, url = {https://www.sciencedirect.com/science/article/pii/S0097316507001008}, author = {A. Rattan}, keywords = {Combinatorics, Representation theory, Symmetric group}, abstract = {In Stanley [R.P. Stanley, Irreducible symmetric group characters of rectangular shape, Sém. Lothar. Combin. 50 (2003) B50d, 11 p.] the author introduces polynomials which help evaluate symmetric group characters and conjectures that the coefficients of the polynomials are positive. In [R.P. Stanley, A conjectured combinatorial interpretation of the normalised irreducible character values of the symmetric group, math.CO/0606467, 2006] the same author gives a conjectured combinatorial interpretation for the coefficients of the polynomials. Here, we prove the conjecture for the terms of highest degree.} } @article{FranklT99, author = {Peter Frankl and Norihide Tokushige}, title = {The Erdos-Ko-Rado Theorem for Integer Sequences}, journal = {Combinatorica}, volume = {19}, number = {1}, year = {1999}, pages = {55-63}, ee = {http://dx.doi.org/10.1007/s004930050045}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{Ellis12, author = {David Ellis}, title = {A proof of the {C}ameron-{K}u conjecture}, journal = {Journal of the London Mathematical Society}, volume = {85}, number = {1}, pages = {165--190}, year = {2012}, doi = {10.1112/jlms/jdr035} } @article{EllisFP11, author = {D. Ellis and E. Friedgut and H. Pilpel}, title = {Intersecting families of permutations}, journal = {J. Amer. Math. Soc.}, volume = {24}, year = {2011}, pages = {649-682} } @article{CameronK03, title = "Intersecting families of permutations ", journal = "European Journal of Combinatorics ", volume = "24", number = "7", pages = "881 - 890", year = "2003", note = "", issn = "0195-6698", doi = "http://dx.doi.org/10.1016/S0195-6698(03)00078-7", url = "http://www.sciencedirect.com/science/article/pii/S0195669803000787", author = "Peter J. Cameron and C.Y. Ku" } @article{LaroseM04, author = {Larose, Benoit and Malvenuto, Claudia}, title = {Stable Sets of Maximal Size in {K}neser-type Graphs}, journal = {Eur. J. Comb.}, issue_date = {July 2004}, volume = {25}, number = {5}, month = jul, year = {2004}, issn = {0195-6698}, pages = {657--673}, numpages = {17}, url = {http://dx.doi.org/10.1016/j.ejc.2003.10.006}, doi = {10.1016/j.ejc.2003.10.006}, acmid = {1012075}, publisher = {Academic Press Ltd.}, address = {London, UK, UK}, keywords = {kneser graphs, permutation graphs, stable sets} } @article{WangZ08, author = {Wang, Jun and Zhang, Sophia J.}, title = {An Erdos-Ko-Rado-type Theorem in Coxeter Groups}, journal = {Eur. J. Comb.}, issue_date = {July, 2008}, volume = {29}, number = {5}, month = jul, year = {2008}, issn = {0195-6698}, pages = {1112--1115}, numpages = {4}, url = {http://dx.doi.org/10.1016/j.ejc.2007.07.002}, doi = {10.1016/j.ejc.2007.07.002}, acmid = {1367266}, publisher = {Academic Press Ltd.}, address = {London, UK, UK} } @phdthesis{AhmadiPhD, author = {Bahman Ahmadi}, title = {Maximum Intersecting Families of Permutations}, school = {University of Regina}, year = 2013, } @phdthesis{NewmanPhD, author = {Michael Newman}, title = {Independent Sets and Eigenspaces}, school = {University of Waterloo}, year = 2004, } @phdthesis{MeagherPhD, author = {Karen Meagher}, title = {Covering Arrays on Graphs: Qualitative Independence Graphs and Extremal Set Partition Theory}, school = {University of Ottowa}, year = 2008, } @phdthesis{RooneyPhD, author = {Brendan Rooney}, title = {Spectral Aspects of Cocliques in Graphs}, school = {University of Waterloo}, year = 2014, } @article{Renteln07, author = {Paul Renteln}, title = {On the Spectrum of the Derangement Graph}, journal = {The Electronic Journal of Combinatorics}, language = {eng}, number = {1}, pages = {Research Paper 82, 17 pp. (electronic)}, volume = {14}, year = {2007}, url = {http://www.combinatorics.org/Volume_14/Abstracts/v14i1r82.html}, timestamp = {Mon, 26 May 2008 12:49:47 +0200}, biburl = {http://dblp.uni-trier.de/rec/bib/journals/combinatorics/Renteln07}, bibsource = {dblp computer science bibliography, http://dblp.org} } @article{KuW10, title = "Eigenvalues of the derangement graph ", journal = "Journal of Combinatorial Theory, Series A ", volume = "117", number = "3", pages = "289 - 312", year = "2010", note = "", doi = "http://dx.doi.org/10.1016/j.jcta.2009.10.002", author = "Cheng Yeaw Ku and David B. Wales", } @article{Murali20, author = {Srinivasan, Murali K.}, title = {The perfect matching association scheme}, journal = {Algebraic Combinatorics}, pages = {559--591}, publisher = {MathOA foundation}, volume = {3}, number = {3}, year = {2020}, doi = {10.5802/alco.104}, zbl = {1441.05240}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.104/} } @article{KuW13a, title = "Solving the {K}u--{W}ales conjecture on the eigenvalues of the derangement graph ", journal = "European Journal of Combinatorics ", volume = "34", number = "6", pages = "941 - 956", year = "2013", note = "", doi = "http://dx.doi.org/10.1016/j.ejc.2013.01.008", author = "Cheng Yeaw Ku and Kok Bin Wong" } @article{Berge57, author = {Berge, Claude}, title = {Two Theorems in Graph Theory}, volume = {43}, number = {9}, pages = {842-844}, year = {1957}, URL = {http://www.pnas.org/content/43/9/842.short}, eprint = {http://www.pnas.org/content/43/9/842.full.pdf+html}, journal = {Proceedings of the National Academy of Sciences} } @article{Neumann75, author = {Neumann, Peter M.}, title = {Generosity and Characters of Multiply Transitive Permutation Groups}, volume = {s3-31}, number = {4}, pages = {457-481}, year = {1975}, doi = {10.1112/plms/s3-31.4.457}, URL = {http://plms.oxfordjournals.org/content/s3-31/4/457.short}, eprint = {http://plms.oxfordjournals.org/content/s3-31/4/457.full.pdf+html}, journal = {Proceedings of the London Mathematical Society} } @book{Cameron, title={Permutation Groups}, author={Cameron, P.J. and Series, C.M. and Bruce, J.W.}, isbn={9780521653787}, lccn={98045456}, series={London Mathematical Society}, url={https://books.google.ca/books?id=4bNj8K1omGAC}, year={1999}, publisher={Cambridge University Press} } @article{Baranyai73, author = {Baranyai, Zsolt}, title = {On the Factorization of the Complete Uniform Hypergraph}, volume = {1}, pages = {91-108}, year = {1973}, journal = {Infinite and Finite Sets:Dedicated to Paul Erdős on his 60th Birthday, North Holland} } @book{Lucas92, title={R{\'e}cr{\'e}ations math{\'e}matiques}, author={Lucas, E.}, number={v. 2}, isbn={9782853671217}, series={R{\'e}cr{\'e}ations math{\'e}matiques}, year={1892}, publisher={A. Blanchard} } @book{Cameron76, title={Parallelisms of Complete Designs}, author={Cameron, P.J.}, isbn={9780521211604}, lccn={lc75032912}, series={Cambridge Commonwealth Series}, url={http://books.google.com/books?id=6As4AAAAIAAJ}, year={1976}, publisher={Cambridge University Press} } @article{Birkhoff46, author = {Birkhoff, D.}, citeulike-article-id = {2743580}, journal = {Universidad Nacional de Tucuman Revista , Serie A}, keywords = {file-import-08-05-01}, pages = {147--151}, posted-at = {2008-05-01 23:40:56}, priority = {2}, title = {{Tres observaciones sobre el algebra lineal}}, volume = {5}, year = {1946} } @ARTICLE{Lindzey14B, author = {{Lindzey}, N.}, title = "{Erd$\backslash$H$\{$o$\}$s-Ko-Rado for Perfect Matchings}", journal = {ArXiv e-prints}, archivePrefix = "arXiv", eprint = {1409.2057}, primaryClass = "math.CO", keywords = {Mathematics - Combinatorics}, year = 2014, month = sep, adsurl = {http://adsabs.harvard.edu/abs/2014arXiv1409.2057L}, adsnote = {Provided by the SAO/NASA Astrophysics Data System} } @article{EdmondsPL82, year={1982}, issn={0209-9683}, journal={Combinatorica}, volume={2}, number={3}, doi={10.1007/BF02579233}, title={Brick decompositions and the matching rank of graphs}, url={http://dx.doi.org/10.1007/BF02579233}, publisher={Springer-Verlag}, keywords={05 C 35; 90 C 05; 05 B 35}, author={Edmonds, J. and Pulleyblank, W.R. and Lov\'asz, L.}, pages={247-274}, language={English} } @incollection{HenkRZ97, author = {Henk, Martin and Richter-Gebert, J\"{u}rgen and Ziegler, G\"{u}nter M.}, chapter = {Basic Properties of Convex Polytopes}, title = {Handbook of Discrete and Computational Geometry}, editor = {Goodman, Jacob E. and O'Rourke, Joseph}, year = {1997}, isbn = {0-8493-8524-5}, pages = {243--270}, numpages = {28}, url = {http://dl.acm.org/citation.cfm?id=285869.285884}, acmid = {285884}, publisher = {CRC Press, Inc.}, address = {Boca Raton, FL, USA} } @book{Sagan01, title={The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions}, author={Sagan, B.E.}, isbn={9780387950679}, lccn={00040042}, series={Graduate Texts in Mathematics}, url={http://books.google.com/books?id=Jm-HBaMdt8sC}, year={2001}, publisher={Springer} } @book{StanleyV101, title={Enumerative Combinatorics:}, author={Stanley, R.P.}, volume={1}, series={Cambridge Studies in Advanced Mathematics}, year={2001}, publisher={Cambridge University Press} } @book{JamesL01, title={Representations and characters of groups}, author={James, Gordon and Liebeck, Martin W}, year={2001}, publisher={Cambridge University Press} } @book{KrebsS11, title={Expander Families and Cayley Graphs: A Beginner's Guide}, author={Krebs, M. and Shaheen, A.}, isbn={9780199767113}, lccn={2011027928}, url={http://books.google.com/books?id=aC4k2GgYgZgC}, year={2011}, publisher={Oxford University Press, USA} } @techreport{GreenhalghPhD, title={Random Walks on Groups with Subgroup Invariance Properties}, author={A.S. Greenhalgh}, year = {1989}, institution = {Stanford University, Department of Statistics}, month = {04}, } @book{Delsarte73, title={An Algebraic Approach to the Association Schemes of Coding Theory}, author={Delsarte, P.}, series={Philips research reports: Supplements}, url={http://books.google.com/books?id=zna0SgAACAAJ}, year={1973}, publisher={N.V. Philips' Gloeilampenfabrieken} } @article{FallatMM21, author = {Fallat, Shaun and Meagher, Karen and Shirazi, Mahsa N.}, title = {The {Erd\H{o}s{\textendash}Ko{\textendash}Rado} theorem for 2-intersecting families of perfect matchings}, journal = {Algebraic Combinatorics}, pages = {575--598}, publisher = {MathOA foundation}, volume = {4}, number = {4}, year = {2021}, doi = {10.5802/alco.169}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.169/} } @misc{ChaseDFL22, title={Uniqueness for 2-Intersecting Families of Permutations and Perfect Matchings}, author={Gilad Chase and Neta Dafni and Yuval Filmus and Nathan Lindzey}, year={2022}, eprint={2210.00245}, archivePrefix={arXiv}, primaryClass={math.CO} } @article{MeagherR21, author = {Karen Meagher and Andriaherimanana Sarobidy Razafimahatratra}, title = {The {E}rd{\H{o}}s--{K}o--{R}ado Theorem for 2-Pointwise and 2-Setwise Intersecting Permutations}, journal = {Electron. J. Comb.}, volume = {28}, number = {4}, year = {2021}, url = {https://doi.org/10.37236/9556}, doi = {10.37236/9556}, timestamp = {Tue, 01 Feb 2022 17:01:28 +0100}, biburl = {https://dblp.org/rec/journals/combinatorics/MeagherR21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @book{BannaiI84, title={Algebraic {C}ombinatorics I: {A}ssociation {S}chemes}, author={Bannai, E. and Ito, T.}, isbn={9780805304909}, lccn={83021355}, series={Mathematics lecture note series}, url={http://books.google.com/books?id=bgDvAAAAMAAJ}, year={1984}, publisher={Benjamin/Cummings Pub. Co.} } @book{Godsil93, title={Algebraic Combinatorics}, author={Godsil, C.}, isbn={9780412041310}, lccn={92041097}, series={Chapman Hall/CRC Mathematics Series}, url={http://books.google.com/books?id=eADtlNCkkIMC}, year={1993}, publisher={Taylor \& Francis} } @InProceedings{BHT, author="Brassard, Gilles and H{\o}yer, Peter and Tapp, Alain", editor="Lucchesi, Cl{\'a}udio L. and Moura, Arnaldo V.", title="Quantum cryptanalysis of hash and claw-free functions", booktitle="LATIN'98: Theoretical Informatics", year="1998", publisher="Springer Berlin Heidelberg", address="Berlin, Heidelberg", pages="163--169", abstract="We give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O(3{\textsurd}N/r) expected evaluations of the function, where N is the cardinality of the domain. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Further, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.", isbn="978-3-540-69715-2" } @misc{FilmusL22, doi = {10.48550/ARXIV.2201.02887}, url = {https://arxiv.org/abs/2201.02887}, author = {Filmus, Yuval and Lindzey, Nathan}, keywords = {Combinatorics (math.CO), Discrete Mathematics (cs.DM), FOS: Mathematics, FOS: Mathematics, FOS: Computer and information sciences, FOS: Computer and information sciences}, title = {Simple Algebraic Proofs of Uniqueness for {E}rd{\H{o}}s--{K}o--{R}ado Theorems}, publisher = {arXiv}, year = {2022}, copyright = {Creative Commons Attribution 4.0 International} } @article{Higman75, year={1975}, issn={0046-5755}, journal={Geometriae Dedicata}, volume={4}, number={1}, doi={10.1007/BF00147398}, title={Coherent configurations}, url={http://dx.doi.org/10.1007/BF00147398}, publisher={Kluwer Academic Publishers}, author={Higman, D.G.}, pages={1-32}, language={English} } @article{MartinT09, author = {Martin, William J. and Tanaka, Hajime}, title = {Commutative Association Schemes}, journal = {Eur. J. Comb.}, issue_date = {August, 2009}, volume = {30}, number = {6}, month = aug, year = {2009}, issn = {0195-6698}, pages = {1497--1525}, numpages = {29}, url = {http://dx.doi.org/10.1016/j.ejc.2008.11.001}, doi = {10.1016/j.ejc.2008.11.001}, acmid = {1542958}, publisher = {Academic Press Ltd.}, address = {London, UK, UK} } @article{Rands83, title = "An association scheme for the 1-factors of the complete graph ", journal = "Journal of Combinatorial Theory, Series A ", volume = "34", number = "3", pages = "301 - 312", year = "1983", note = "", issn = "0097-3165", doi = "http://dx.doi.org/10.1016/0097-3165(83)90064-X", url = "http://www.sciencedirect.com/science/article/pii/009731658390064X", author = "B.M.I Rands" } @book{CST2, place={Cambridge}, series={Cambridge Studies in Advanced Mathematics}, title={Representation Theory of the Symmetric Groups: The Okounkov-Vershik Approach, Character Formulas, and Partition Algebras}, publisher={Cambridge University Press}, author={Ceccherini-Silberstein, Tullio and Scarabotti, Fabio and Tolli, Filippo}, year={2010}, collection={Cambridge Studies in Advanced Mathematics}} @book{MacDonald95, title={Symmetric {F}unctions and Hall {P}olynomials}, author={Macdonald, I.G.}, lccn={lc79040605}, series={Oxford mathematical monographs}, year={1995}, publisher={Clarendon Press} } @book{CeccheriniST08, title={Harmonic Analysis on Finite Groups: Representation Theory, Gelfand Pairs and Markov Chains}, author={Ceccherini-Silberstein, T. and Scarabotti, F. and Tolli, F.}, isbn={9781139470803}, series={Cambridge Studies in Advanced Mathematics}, url={http://books.google.com/books?id=3trud4weQ3AC}, year={2008}, publisher={Cambridge University Press} } @article{Thrall42, jstor_articletype = {research-article}, title = {On Symmetrized {K}ronecker Powers and the Structure of the Free {L}ie Ring}, author = {Thrall, R. M.}, journal = {American Journal of Mathematics}, jstor_issuetitle = {}, volume = {64}, number = {1}, jstor_formatteddate = {1942}, pages = {pp. 371-388}, url = {http://www.jstor.org/stable/2371691}, ISSN = {00029327}, abstract = {}, language = {English}, year = {1942}, publisher = {The Johns Hopkins University Press}, copyright = {Copyright © 1942 The Johns Hopkins University Press}, } @article{Godsil98, author = "C. D. Godsil", title = "Eigenpolytopes of distance regular graphs", journal = "Canadian Journal of Mathematics", volume = "50", pages = "739--755", year = "1998", } @manual{GAP, key = "GAP", organization = "The GAP~Group", title = "{GAP -- Groups, Algorithms, and Programming, Version 4.7.5}", year = 2014, url = "\verb+(http://www.gap-system.org)+", } @article{Littlewood44, author = {Littlewood, D. E.}, title = {Invariant Theory, Tensors and Group Characters}, volume = {239}, number = {807}, pages = {305-365}, year = {1944}, doi = {10.1098/rsta.1944.0001}, URL = {http://rsta.royalsocietypublishing.org/content/239/807/305.abstract}, eprint = {http://rsta.royalsocietypublishing.org/content/239/807/305.full.pdf+html}, journal = {Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences} } @article{Foulkes50, author = {Foulkes, H. O.}, title = {Concomitants of the Quintic and Sextic Up To Degree Four in the Coefficients of the Ground Form}, volume = {s1-25}, number = {3}, pages = {205-209}, year = {1950}, doi = {10.1112/jlms/s1-25.3.205}, URL = {http://jlms.oxfordjournals.org/content/s1-25/3/205.short}, eprint = {http://jlms.oxfordjournals.org/content/s1-25/3/205.full.pdf+html}, journal = {Journal of the London Mathematical Society} } @article{FranklD77, author = "Peter Frankl and Mikhail Deza", title = "On the maximum number of permutations with given maximal or minimal distance ", journal = "Journal of Combinatorial Theory, Series A ", volume = "22", number = "3", pages = "352 - 360", year = "1977", note = "", issn = "0097-3165", doi = "http://dx.doi.org/10.1016/0097-3165(77)90009-7"} @InProceedings{CurticapeanLN18a, author= {Radu Curticapean and Nathan Lindzey and Jesper Nederlof}, title= {{A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank}}, booktitle= {{3rd Highlights of Algorithms (HALG 2018), Amsterdam, Netherlands}}, month= {June}, year= {2018}, } @misc{AuLT20, title={Matchings, hypergraphs, association schemes, and semidefinite optimization}, author={Yu Hin Au and Nathan Lindzey and Levent Tunçel}, year={2020}, eprint={2008.08628}, archivePrefix={arXiv}, primaryClass={math.CO} } @inproceedings{LovettTZ18, author = {Shachar Lovett and Avishay Tal and Jiapeng Zhang}, editor = {Artur Czumaj}, title = {The Robust Sensitivity of Boolean Functions}, booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018}, pages = {1822--1833}, publisher = {{SIAM}}, year = {2018}, url = {https://doi.org/10.1137/1.9781611975031.119}, doi = {10.1137/1.9781611975031.119}, timestamp = {Mon, 15 Jun 2020 17:00:15 +0200}, biburl = {https://dblp.org/rec/conf/soda/LovettTZ18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{KaneLR19, author = {Daniel Kane and Shachar Lovett and Sankeerth Rao}, title = {The Independence Number of the {B}irkhoff Polytope Graph, and Applications to Maximally Recoverable Codes}, journal = {{SIAM} J. Comput.}, volume = {48}, number = {4}, pages = {1425--1435}, year = {2019}, url = {https://doi.org/10.1137/18M1205856}, doi = {10.1137/18M1205856}, timestamp = {Sat, 19 Oct 2019 19:34:07 +0200}, biburl = {https://dblp.org/rec/journals/siamcomp/KaneLR19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{Pak00, year={2000}, issn={0218-0006}, journal={Annals of Combinatorics}, volume={4}, number={1}, doi={10.1007/PL00001277}, title={Four Questions on the {B}irkhoff Polytope}, url={http://dx.doi.org/10.1007/PL00001277}, publisher={Birkhauser Verlag}, keywords={Keywords: Birkhoff polytope, simplex method, random walk, symmetric group, mixing time}, author={Pak, I.}, pages={83-90}, language={English} } @inproceedings{Rothvoss14, author = {Thomas Rothvo{\ss}}, title = {The matching polytope has exponential extension complexity}, booktitle = {STOC}, year = {2014}, pages = {263-272}, ee = {http://doi.acm.org/10.1145/2591796.2591834}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{DiaconisH02, author = {Persi Diaconis and Susan Holmes}, title = {Random Walks on Trees and Matchings}, journal = {Electron. J. Probab.}, fjournal = {Electronic Journal of Probability}, volume = {7}, year = {2002}, keywords = {Markov Chain, Matchings, Phylogenetic Tree, Fourier analysis, Zonal polynomials, Coagulation-Fragmentation.}, abstract = {We give sharp rates of convergence for a natural Markov chain on the space of phylogenetic trees and dually for the natural random walk on the set of perfect matchings in the complete graph on $2n$ vertices. Roughly, the results show that $(1/2) n \log n$ steps are necessary and suffice to achieve randomness. The proof depends on the representation theory of the symmetric group and a bijection between trees and matchings.}, pages = {no. 6, 1-17}, issn = {1083-6489}, doi = {10.1214/EJP.v7-105}, url = {http://ejp.ejpecp.org/article/view/105}} @book{Diaconis88, added-at = {2010-02-04T21:40:41.000+0100}, address = {Hayward, CA}, author = {Diaconis, Persi}, biburl = {http://www.bibsonomy.org/bibtex/2933838b3e918380eb835383259944baf/peter.ralph}, description = {MR: Publications results for "MR Number=(964069)"}, interhash = {f8e3d552ac7a2a48d97ec0820620e592}, intrahash = {933838b3e918380eb835383259944baf}, isbn = {0-940600-14-5}, keywords = {discrete_fourier_transform reference representation_theory}, mrclass = {60-02 (20C99 62-02)}, mrnumber = {MR964069 (90a:60001)}, mrreviewer = {Philippe Bougerol}, pages = {vi+198}, publisher = {Institute of Mathematical Statistics}, series = {Institute of Mathematical Statistics Lecture Notes---Monograph Series, 11}, timestamp = {2010-02-04T21:40:41.000+0100}, title = {Group {R}epresentations in {P}robability and {S}tatistics}, url = {http://projecteuclid.org/euclid.lnms/1215467407}, year = 1988 } @article{Chvatal75, title = "On certain polytopes associated with graphs ", journal = "Journal of Combinatorial Theory, Series B ", volume = "18", number = "2", pages = "138 - 154", year = "1975", note = "", issn = "0095-8956", doi = "http://dx.doi.org/10.1016/0095-8956(75)90041-6", url = "http://www.sciencedirect.com/science/article/pii/0095895675900416", author = "V Chvátal" } @article{Polster97, title = "Abstract hyperovals and {H}adamard designs", journal = "Australas. J. Combin.", volume = "16", pages = "29-33", year = "1997", author = "Polster, Burkard" } @ARTICLE{EllisFFa13, author = {{Ellis}, D. and {Filmus}, Y. and {Friedgut}, E.}, title = "{A quasi-stability result for dictatorships in ${S}_n$}", journal = {ArXiv e-prints}, archivePrefix = "arXiv", eprint = {1209.5557}, primaryClass = "math.CO", keywords = {Mathematics - Combinatorics, Mathematics - Representation Theory, 05D99, 05E15}, year = 2012, month = sep, adsurl = {http://adsabs.harvard.edu/abs/2012arXiv1209.5557E}, adsnote = {Provided by the SAO/NASA Astrophysics Data System} } @ARTICLE{EllisFFb13, author = {{Ellis}, D. and {Filmus}, Y. and {Friedgut}, E.}, title = "{A stability result for balanced dictatorships in ${S}_n$}", journal = {ArXiv e-prints}, archivePrefix = "arXiv", eprint = {1210.3989}, primaryClass = "math.CO", keywords = {Mathematics - Combinatorics, 05D99, 05E15}, year = 2012, month = oct, adsurl = {http://adsabs.harvard.edu/abs/2012arXiv1210.3989E}, adsnote = {Provided by the SAO/NASA Astrophysics Data System} } @ARTICLE{Filmus14, author = {{Filmus}, Y.}, title = "{Friedgut--Kalai--Naor theorem for slices of the Boolean cube}", journal = {ArXiv e-prints}, archivePrefix = "arXiv", eprint = {1410.7834}, primaryClass = "math.CO", keywords = {Mathematics - Combinatorics}, year = 2014, month = oct, adsurl = {http://adsabs.harvard.edu/abs/2014arXiv1410.7834F}, adsnote = {Provided by the SAO/NASA Astrophysics Data System} } @INPROCEEDINGS{Wimmer10, author={Wimmer, K.}, booktitle={Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on}, title={Agnostically Learning under Permutation Invariant Distributions}, year={2010}, month={Oct}, pages={113-122}, keywords={Boolean algebra;Fourier analysis;combinatorial mathematics;computational complexity;learning (artificial intelligence);Boolean hypercube;Fourier concentration;Fourier spectrum;Young tableaux;agnostically learning;arbitrary product distributions;combinatorial interpretation;combinatorics;computational learning theory;low noise sensitivity;low-degree algorithm;permutation invariant distributions;polynomial time;probability mass;representation theory;symmetric group;theorem of Peres;uniform distribution;Hypercubes;Loss measurement;Noise;Polynomials;Sensitivity;Support vector machines;Tin;Boolean functions;Fourier analysis;agnostic learning;representation theory;symmetric group}, doi={10.1109/FOCS.2010.17}, ISSN={0272-5428},} @article{FriedgutKN02, author = {Friedgut, Ehud and Kalai, Gil and Naor, Assaf}, title = {Boolean Functions Whose Fourier Transform is Concentrated on the First Two Levels}, journal = {Adv. Appl. Math.}, issue_date = {October 2002}, volume = {29}, number = {3}, month = oct, year = {2002}, issn = {0196-8858}, pages = {427--437}, numpages = {11}, url = {http://dx.doi.org/10.1016/S0196-8858(02)00024-6}, doi = {10.1016/S0196-8858(02)00024-6}, acmid = {638174}, publisher = {Academic Press, Inc.}, address = {Orlando, FL, USA}, } @article{Kalai02, title = "A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem ", journal = "Advances in Applied Mathematics ", volume = "29", number = "3", pages = "412 - 426", year = "2002", note = "", issn = "0196-8858", doi = "http://dx.doi.org/10.1016/S0196-8858(02)00023-4", url = "http://www.sciencedirect.com/science/article/pii/S0196885802000234", author = "Gil Kalai" } @article{Cruse75, title = "A note on symmetric doubly-stochastic matrices ", journal = "Discrete Mathematics ", volume = "13", number = "2", pages = "109 - 119", year = "1975", note = "", issn = "0012-365X", doi = "http://dx.doi.org/10.1016/0012-365X(75)90012-6", url = "http://www.sciencedirect.com/science/article/pii/0012365X75900126", author = "Allan B. Cruse" } @article{Bauer07, title = "A remark on {S}tirling's formula and on approximations for the double factorial", journal = "The Mathematical Intelligencer", volume = "29", number = "2", pages = "10 - 14", year = "2007", author = "F. L. Bauer" } @article{Lovasz87, title = "Matching structure and the matching lattice", journal = "Journal of Combinatorial Theory, Series B", volume = "43", number = "2", pages = "187 - 222", year = "1987", note = "", issn = "0095-8956", doi = "http://dx.doi.org/10.1016/0095-8956(87)90021-9", url = "http://www.sciencedirect.com/science/article/pii/0095895687900219", author = "L\'aszl\'o Lov\'asz", } @INPROCEEDINGS{Wimmer14, author={K. Wimmer}, booktitle={Computational Complexity (CCC), 2014 IEEE 29th Conference on}, title={Low Influence Functions over Slices of the Boolean Hypercube Depend on Few Coordinates}, year={2014}, pages={120-131}, keywords={Boolean functions;combinatorial mathematics;computational complexity;Boolean cube slice;Boolean functions;Boolean hypercube;Young tableaux;fixed Hamming weight;hypercontractivity;junta theorem;low influence functions;natural orthogonal basis determination;nonproduct distribution;product distribution;representation theory;string set;symmetric group;uniform distribution;Boolean functions;Hamming weight;Hypercubes;Shape;Standards;Tin;Vectors;Boolean function;influence;junta theorem;representation theory;symmetric group}, doi={10.1109/CCC.2014.20}, month={June},} @ARTICLE{LindzeyEKR14, author = {{Lindzey}, N.}, title = "{Erd$\backslash$H$\{$o$\}$s-Ko-Rado for Perfect Matchings}", journal = {ArXiv e-prints}, archivePrefix = "arXiv", eprint = {1409.2057}, primaryClass = "math.CO", keywords = {Mathematics - Combinatorics}, year = 2014, month = sep, adsurl = {http://adsabs.harvard.edu/abs/2014arXiv1409.2057L}, adsnote = {Provided by the SAO/NASA Astrophysics Data System} } @article{AlonKKMS02, title = "Scalable Secure Storage When Half the System Is Faulty ", journal = "Information and Computation ", volume = "174", number = "2", pages = "203 - 213", year = "2002", note = "", issn = "0890-5401", doi = "http://dx.doi.org/10.1006/inco.2002.3148", url = "http://www.sciencedirect.com/science/article/pii/S0890540102931482", author = "Noga Alon and Haim Kaplan and Michael Krivelevich and Dahlia Malkhi and Julien Stern" } @book{HornJohnson, author = {Horn, Roger A. and Johnson, Charles R.}, title = {Matrix Analysis}, year = {1986}, isbn = {0-521-30586-1}, publisher = {Cambridge University Press}, address = {New York, NY, USA}, } @inproceedings{MarcusSS13, author = {Marcus, Adam and Spielman, Daniel A. and Srivastava, Nikhil}, title = {Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees}, booktitle = {Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science}, series = {FOCS '13}, year = {2013}, isbn = {978-0-7695-5135-7}, pages = {529--537}, numpages = {9}, url = {http://dx.doi.org/10.1109/FOCS.2013.63}, doi = {10.1109/FOCS.2013.63}, acmid = {2570622}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, keywords = {Ramanujan Graph, Matching Polynomial, Lifts of Graphs}, } @article{AlonM85, title = "λ1, Isoperimetric inequalities for graphs, and superconcentrators", journal = "Journal of Combinatorial Theory, Series B", volume = "38", number = "1", pages = "73 - 88", year = "1985", note = "", issn = "0095-8956", doi = "http://dx.doi.org/10.1016/0095-8956(85)90092-9", url = "http://www.sciencedirect.com/science/article/pii/0095895685900929", author = "N Alon and V.D Milman", } @article{BiluL06, mrkey = {2279667}, author = {Bilu, Yonatan and Linial, Nathan}, title = {Lifts, discrepancy and nearly optimal spectral gap}, journal = {Combinatorica}, fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing}, volume = {26}, year = {2006}, number = {5}, pages = {495--519}, issn = {0209-9683}, mrclass = {05C50}, mrnumber = {2279667}, mrreviewer = {Sebastian M. Cioab{\u{a}}}, doi = {10.1007/s00493-006-0029-7}, zblnumber = {1121.05054}, } @article{ChudnovskyS07, mrkey = {2305888}, author = {Chudnovsky, Maria and Seymour, Paul}, title = {The roots of the independence polynomial of a clawfree graph}, journal = {J. Combin. Theory Ser. B}, fjournal = {Journal of Combinatorial Theory. Series B}, volume = {97}, year = {2007}, number = {3}, pages = {350--357}, issn = {0095-8956}, coden = {JCBTB8}, mrclass = {05C69}, mrnumber = {2305888}, mrreviewer = {Steven D. Noble}, doi = {10.1016/j.jctb.2006.06.001}, zblnumber = {1119.05075}, } @article{BorceaB10, author = {Julius Borcea and P. Branden}, title = {{Multivariate Polya-Schur classification problems in the Weyl algebra}}, journal = {Proceedings of The London Mathematical Society}, volume = {101}, year = {2010}, pages = {73--104}, issue = {1}, doi = {10.1112/plms/pdp049}, masid = {16441955} } @incollection{GodsilG78, mrkey = {0642044}, author = {Godsil, C. D. and Gutman, I.}, title = {On the matching polynomial of a graph}, booktitle = {Algebraic Methods in Graph Theory, {V}ol. {I}, {II}}, venue = {{S}zeged, 1978}, series = {Colloq. Math. Soc. J�nos Bolyai}, volume = {25}, pages = {241--249}, publisher = {North-Holland}, address = {New York}, year = {1981}, mrclass = {05C70 (33A65)}, mrnumber = {0642044}, mrreviewer = {E. J. Farrell}, zblnumber = {0476.05060}, } @article{HeilmannL72, mrkey = {0297280}, author = {Heilmann, Ole J. and Lieb, Elliott H.}, title = {Theory of monomer-dimer systems}, journal = {Comm. Math. Phys.}, fjournal = {Communications in Mathematical Physics}, volume = {25}, year = {1972}, pages = {190--232}, issn = {0010-3616}, mrclass = {82.05}, mrnumber = {0297280}, doi = {10.1007/BF01877590}, zblnumber = {0228.05131}, } @article{LubotzkyPS88, mrkey = {0963118}, author = {Lubotzky, A. and Phillips, R. and Sarnak, P.}, title = {Ramanujan graphs}, journal = {Combinatorica}, fjournal = {Combinatorica. An International Journal of the J�nos Bolyai Mathematical Society}, volume = {8}, year = {1988}, number = {3}, pages = {261--277}, issn = {0209-9683}, coden = {COMBDI}, mrclass = {05C75 (05C25 05C50)}, mrnumber = {0963118}, mrreviewer = {Dave Witte Morris}, doi = {10.1007/BF02126799}, zblnumber = {0661.05035}, } @article{Wagner11, mrkey = {2738906}, author = {Wagner, David G.}, title = {Multivariate stable polynomials: theory and applications}, journal = {Bull. Amer. Math. Soc.}, fjournal = {American Mathematical Society. Bulletin. New Series}, volume = {48}, year = {2011}, number = {1}, pages = {53--84}, issn = {0273-0979}, coden = {BAMOAD}, mrclass = {32A60 (05A20 05B35 15A45)}, mrnumber = {2738906}, doi = {10.1090/S0273-0979-2010-01321-5}, zblnumber = {1207.32006}, } @book{Schrijver, added-at = {2007-07-05T16:17:35.000+0200}, author = {Schrijver, A.}, biburl = {http://www.bibsonomy.org/bibtex/2496d0012f9b295acbef270a129061375/jleny}, description = {bandit problems}, interhash = {dfbeb3a87380195540f44a10e9995230}, intrahash = {496d0012f9b295acbef270a129061375}, keywords = {imported}, publisher = {Springer}, timestamp = {2007-07-05T16:17:37.000+0200}, title = {Combinatorial Optimization - Polyhedra and Efficiency}, year = 2003 } @article{PadbergR82, author = {Manfred W. Padberg and M. R. Rao}, title = {Odd Minimum Cut-Sets and \emph{b}-Matchings}, journal = {Math. Oper. Res.}, volume = {7}, number = {1}, pages = {67--80}, year = {1982}, url = {http://dx.doi.org/10.1287/moor.7.1.67}, doi = {10.1287/moor.7.1.67}, timestamp = {Fri, 08 Apr 2016 10:36:19 +0200}, biburl = {http://dblp.uni-trier.de/rec/bib/journals/mor/PadbergR82}, bibsource = {dblp computer science bibliography, http://dblp.org} } @Article{GrotschelLS81, author="Gr{\"o}tschel, M. and Lov{\'a}sz, L. and Schrijver, A.", title="The ellipsoid method and its consequences in combinatorial optimization", journal="Combinatorica", year="1981", volume="1", number="2", pages="169--197", abstract="L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields a proof that weighted fractional chromatic number is NP-hard.", issn="1439-6912", doi="10.1007/BF02579273", url="http://dx.doi.org/10.1007/BF02579273" } @book{Serre96, title={Linear Representations of Finite Groups}, author={Scott, L.L. and Serre, J.P.}, isbn={9780387901909}, lccn={76012585}, series={Graduate Texts in Mathematics}, url={https://books.google.ca/books?id=NCfZgr54TJ4C}, year={1996}, publisher={Springer New York} } @inproceedings{BraunBHPRRWZ16, author = {Braun, G\'{a}bor and Brown-Cohen, Jonah and Huq, Arefin and Pokutta, Sebastian and Raghavendra, Prasad and Roy, Aurko and Weitz, Benjamin and Zink, Daniel}, title = {The Matching Problem Has No Small Symmetric {S}{D}{P}}, booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms}, series = {SODA '16}, year = {2016}, isbn = {978-1-611974-33-1}, location = {Arlington, Virginia}, pages = {1067--1078}, numpages = {12}, url = {http://dl.acm.org/citation.cfm?id=2884435.2884510}, acmid = {2884510}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, } @article{LeP13, title = "Complexity results for rainbow matchings ", journal = "Theoretical Computer Science ", volume = "524", number = "", pages = "27 - 33", year = "2014", note = "", issn = "0304-3975", doi = "http://dx.doi.org/10.1016/j.tcs.2013.12.013", url = "http://www.sciencedirect.com/science/article/pii/S0304397513009250", author = "Van Bang Le and Florian Pfender", keywords = "Rainbow matching", keywords = "Computational complexity", keywords = "NP-completeness", keywords = "APX-completeness", keywords = "Parameterized complexity " } @inproceedings{MathieuS09, author = {Mathieu, Claire and Sinclair, Alistair}, title = {Sherali-{A}dams Relaxations of the Matching Polytope}, booktitle = {Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing}, series = {STOC '09}, year = {2009}, isbn = {978-1-60558-506-2}, location = {Bethesda, MD, USA}, pages = {293--302}, numpages = {10}, url = {http://doi.acm.org/10.1145/1536414.1536456}, doi = {10.1145/1536414.1536456}, acmid = {1536456}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {0-1 programming, integrality gap, lift-and-project, linear programming relaxation, matching polytope, maximum matching}, } @book{Sagan, title={The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions}, author={Sagan, B.}, isbn={9780387950679}, lccn={00400422}, series={Graduate Texts in Mathematics}, url={https://books.google.ca/books?id=Jm-HBaMdt8sC}, year={2001}, publisher={Springer New York} } @article{EllisFF15A, author = {Ellis, David and Filmus, Yuval and Friedgut, Ehud}, title = {A Quasi-stability Result for Dictatorships in ${S}_n$}, journal = {Combinatorica}, issue_date = {October 2015}, volume = {35}, number = {5}, month = oct, year = {2015}, issn = {0209-9683}, pages = {573--618}, numpages = {46}, url = {http://dx.doi.org/10.1007/s00493-014-3027-1}, doi = {10.1007/s00493-014-3027-1}, acmid = {2872583}, publisher = {Springer-Verlag New York, Inc.}, address = {Secaucus, NJ, USA}, keywords = {05D99e}, } @article{EllisFF15B, author = {Ellis, David and Filmus, Yuval and Friedgut, Ehud}, title = {A Stability Result for Balanced Dictatorships in ${S}_n$}, journal = {Random Struct. Algorithms}, issue_date = {May 2015}, volume = {46}, number = {3}, month = may, year = {2015}, issn = {1042-9832}, pages = {494--530}, numpages = {37}, url = {http://dx.doi.org/10.1002/rsa.20515}, doi = {10.1002/rsa.20515}, acmid = {2915121}, publisher = {John Wiley \& Sons, Inc.}, address = {New York, NY, USA}, keywords = {Fourier transform, stability, symmetric group}, } @article{BrunkH10, title = "Some Erd?s?Ko?Rado theorems for injections", journal = "European Journal of Combinatorics", volume = "31", number = "3", pages = "839 - 860", year = "2010", issn = "0195-6698", doi = "https://doi.org/10.1016/j.ejc.2009.07.013", url = "http://www.sciencedirect.com/science/article/pii/S0195669809001711", author = "Fiona Brunk and Sophie Huczynska" } @book{StirlingNumbers, title={Combinatorial Identities for Stirling Numbers: The Unpublished Notes of H W Gould}, author={Quaintance, J.}, isbn={9789814725286}, lccn={2015032206}, url={https://books.google.ca/books?id=q9XACwAAQBAJ}, year={2015}, publisher={World Scientific Publishing Company Pte Limited} } @article{HanlonW88, title = "On the decomposition of {B}rauer's centralizer algebras", journal = "Journal of Algebra", volume = "121", number = "2", pages = "409 - 445", year = "1989", issn = "0021-8693", doi = "https://doi.org/10.1016/0021-8693(89)90076-8", url = "http://www.sciencedirect.com/science/article/pii/0021869389900768", author = "Phil Hanlon and David Wales" } @misc{IkenmeyerPP22, author = {Ikenmeyer, Christian and Pak, Igor and Panova, Greta}, eprint={2207.05423}, title = {Positivity of the symmetric group characters is as hard as the polynomial time hierarchy}, publisher = {arXiv}, year = {2022} } @article{AlexanderssonHW21, author = {Alexandersson, Per and Haglund, James and Wang, George}, journal = {Journal of Combinatorics}, number = {2}, pages = {215--233}, publisher = {INT PRESS BOSTON, INC}, title = {Some conjectures on the {S}chur expansion of {J}ack polynomials}, volume = {12}, keywords = {Jack polynomials, Schur polynomials, Quasi-Yamanouchi tableaux, Eulerian numbers, Stirling numbers, Rook polynomials}, abstract = {We present positivity conjectures for the Schur expansion of Jack symmetric functions in two bases given by binomial coefficients. Partial results suggest that there are rich combinatorics to be found in these bases, including Eulerian numbers, Stirling numbers, quasi-Yamanouchi tableaux, and rook boards. These results also lead to further conjectures about the fundamental quasisymmetric expansions of these bases, which we prove for special cases. }, year = {2021} } @article{Hanlon88, title = {Jack symmetric functions and some combinatorial properties of {Y}oung symmetrizers}, journal = {Journal of Combinatorial Theory, Series A}, volume = {47}, number = {1}, pages = {37-70}, year = {1988}, doi = {https://doi.org/10.1016/0097-3165(88)90042-8}, author = {Phil Hanlon} } @article{PakP17, title = {On the complexity of computing {K}ronecker coefficients}, journal = {computational complexity}, volume = {26}, pages = {1-36}, year = {2017}, author = {Igor Pak and Greta Panova} } @article{Lovasz06, title = "The rank of connection matrices and the dimension of graph algebras", journal = "European Journal of Combinatorics", volume = "27", number = "6", pages = "962 - 970", year = "2006", issn = "0195-6698", doi = "https://doi.org/10.1016/j.ejc.2005.04.012", url = "http://www.sciencedirect.com/science/article/pii/S0195669805000788", author = "L\'aszl\'o Lov\'asz" } @article{FreedmanLS07, title = "Reflection positivity, rank connectivity, and homomorphism of graphs", keywords = "Connection matrix, Graph homomorphism, Partition function", author = "Michael Freedman and L{\'a}szl{\'o} Lov{\'a}sz and Alexander Schrijver", year = "2007", month = "1", doi = "10.1090/S0894-0347-06-00529-7", language = "English", volume = "20", pages = "37--51", journal = "Journal of the American Mathematical Society", issn = "0894-0347", publisher = "American Mathematical Society", number = "1", } @article{Bellman62, author = {Bellman, Richard}, title = {Dynamic Programming Treatment of the {T}raveling {S}alesman Problem}, journal = {J. ACM}, issue_date = {Jan. 1962}, volume = {9}, number = {1}, month = jan, year = {1962}, issn = {0004-5411}, pages = {61--63}, numpages = {3}, url = {http://doi.acm.org/10.1145/321105.321111}, doi = {10.1145/321105.321111}, acmid = {321111}, publisher = {ACM}, address = {New York, NY, USA}, } @inproceedings{HeldK62, author = {Held, Michael and Karp, Richard M.}, title = {A Dynamic Programming Approach to Sequencing Problems}, booktitle = {Proceedings of the 1961 16th ACM National Meeting}, series = {ACM '61}, year = {1961}, pages = {71.201--71.204}, numpages = {1.003}, url = {http://doi.acm.org/10.1145/800029.808532}, doi = {10.1145/800029.808532}, acmid = {808532}, publisher = {ACM}, address = {New York, NY, USA}, } @INPROCEEDINGS{BlaisWY12, author={E. {Blais} and A. {Weinstein} and Y. {Yoshida}}, booktitle={2012 IEEE 53rd Annual Symposium on Foundations of Computer Science}, title={Partially Symmetric Functions Are Efficiently Isomorphism-Testable}, year={2012}, volume={}, number={}, pages={551-560},} @unpublished{DellPC, title= {Fine-Grained Complexity Classification of Counting Problems}, author = {Holger Dell}, year = {2016}, note= {Simons Institute, The Classification Program of Counting Complexity, https://simons.berkeley.edu/talks/holger-dell-2016-03-28}, url= {\url{https://simons.berkeley.edu/talks/holger-dell-2016-03-28}}, } @book{A=B, title={A = B}, author={Petkovsek, M. and Wilf, H.S. and Zeilberger, D.}, isbn={9781568810638}, lccn={95051210}, series={A K Peters Series}, url={https://books.google.ca/books?id=A-pU8HQOWPMC}, year={1996}, publisher={Taylor \& Francis} } @article{BodlaenderCKN15, author = {Hans L. Bodlaender and Marek Cygan and Stefan Kratsch and Jesper Nederlof}, title = {Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth}, journal = {Inf. Comput.}, volume = {243}, pages = {86--111}, year = {2015}, url = {https://doi.org/10.1016/j.ic.2014.12.008}, doi = {10.1016/j.ic.2014.12.008}, timestamp = {Sat, 16 Sep 2017 12:06:31 +0200}, biburl = {https://dblp.org/rec/bib/journals/iandc/BodlaenderCKN15}, bibsource = {dblp computer science bibliography, https://dblp.org} } @misc{OEIS, author = {N. J. A. Sloane}, title = {The Encyclopedia of Integer Sequences}, year = {}, note={\url{https://oeis.org/}} } @inproceedings{LovaszS88, author = {L{\'{a}}szl{\'{o}} Lov{\'{a}}sz and Michael E. Saks}, title = {Lattices, {M}{\"{o}}bius Functions and Communication Complexity}, booktitle = {29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988}, pages = {81--90}, year = {1988}, crossref = {DBLP:conf/focs/FOCS29}, url = {https://doi.org/10.1109/SFCS.1988.21924}, doi = {10.1109/SFCS.1988.21924}, timestamp = {Fri, 19 May 2017 01:26:00 +0200}, biburl = {https://dblp.org/rec/bib/conf/focs/LovaszS88}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{ScarabottiT09, author = {Scarabotti, Fabio and Tolli, Filippo}, title = {Harmonic analysis on a finite homogeneous space}, journal = {Proceedings of the London Mathematical Society}, volume = {100}, number = {2}, pages = {348-376}, doi = {10.1112/plms/pdp027}, url = {https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/pdp027} } @ARTICLE{Filmus14, author = {{Filmus}, Yuval}, title = "{Friedgut--Kalai--Naor theorem for slices of the Boolean cube}", journal = {ArXiv e-prints}, archivePrefix = "arXiv", eprint = {1410.7834}, primaryClass = "math.CO", keywords = {Mathematics - Combinatorics}, year = 2014, month = oct, adsurl = {http://adsabs.harvard.edu/abs/2014arXiv1410.7834F}, adsnote = {Provided by the SAO/NASA Astrophysics Data System} } @article{Filmus16, author = {Yuval Filmus}, title = {Friedgut-{K}alai-{N}aor Theorem for Slices of the Boolean Cube}, journal = {Chic. J. Theor. Comput. Sci.}, volume = {2016}, year = {2016}, url = {http://cjtcs.cs.uchicago.edu/articles/2016/14/contents.html}, timestamp = {Wed, 22 Jul 2020 22:05:17 +0200}, biburl = {https://dblp.org/rec/journals/cjtcs/Filmus16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{Filmus20, author = {Yuval Filmus}, title = {{FKN} theorem for the multislice, with applications}, journal = {Comb. Probab. Comput.}, volume = {29}, number = {2}, pages = {200--212}, year = {2020}, url = {https://doi.org/10.1017/S0963548319000361}, doi = {10.1017/S0963548319000361}, timestamp = {Tue, 21 Apr 2020 10:19:32 +0200}, biburl = {https://dblp.org/rec/journals/cpc/Filmus20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{LindzeyM16, author = {Nathan Lindzey and Ross M. McConnell}, title = {Linear-Time Algorithms for Finding {T}ucker Submatrices and {L}ekkerkerker-{B}oland Subgraphs}, journal = {{SIAM} J. Discret. Math.}, volume = {30}, number = {1}, pages = {43--69}, year = {2016}, url = {https://doi.org/10.1137/140951631}, doi = {10.1137/140951631}, timestamp = {Sat, 25 Apr 2020 13:57:07 +0200}, biburl = {https://dblp.org/rec/journals/siamdm/LindzeyM16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @unpublished{FilmusLLV20, title= {Complexity measures on symmetric group and beyond}, author = {Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals}, year = {2020}, note= {(Manuscript)~https://yuvalfilmus.cs.technion.ac.il/Papers/measures.pdf}, url= {\url{https://yuvalfilmus.cs.technion.ac.il/Papers/measures.pdf}}, } @article{FilmusKMW18, author = {Yuval Filmus and Guy Kindler and Elchanan Mossel and Karl Wimmer}, title = {Invariance Principle on the Slice}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {3}, pages = {11:1--11:37}, year = {2018}, url = {https://doi.org/10.1145/3186590}, doi = {10.1145/3186590}, timestamp = {Mon, 08 Jun 2020 22:18:56 +0200}, biburl = {https://dblp.org/rec/journals/toct/FilmusKMW18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{FilmusOW19, author = {Yuval Filmus and Ryan O'Donnell and Xinyu Wu}, editor = {Avrim Blum}, title = {A log-{S}obolev Inequality for the Multislice, with Applications}, booktitle = {10th Innovations in Theoretical Computer Science Conference, {ITCS} 2019, January 10-12, 2019, San Diego, California, {USA}}, series = {LIPIcs}, volume = {124}, pages = {34:1--34:12}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2019}, url = {https://doi.org/10.4230/LIPIcs.ITCS.2019.34}, doi = {10.4230/LIPIcs.ITCS.2019.34}, timestamp = {Tue, 11 Feb 2020 15:52:14 +0100}, biburl = {https://dblp.org/rec/conf/innovations/FilmusOW19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{Dukes12, author = {Dukes, Peter J.}, title = {Coding with Injections}, year = {2012}, issue_date = {December 2012}, publisher = {Kluwer Academic Publishers}, address = {USA}, volume = {65}, number = {3}, issn = {0925-1022}, url = {https://doi.org/10.1007/s10623-011-9547-4}, doi = {10.1007/s10623-011-9547-4}, abstract = {A permutation code of length n and minimum distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between any distinct $${u,v in Gamma}$$ is at least d . As a generalization, we introduce the problem of packing injections from an m -set, m n , sometimes called m -arrangements, relative to Hamming distance. We offer some preliminary coding-theoretic bounds, a few design-theoretic connections, and a short discussion on possible applications.}, journal = {Des. Codes Cryptography}, month = {dec}, pages = {213–222}, numpages = {10}, keywords = {Ordered design, Injection, Permutation code, Arrangement, 94A10, Primary 05A05, Secondary 05B40, Hamming distance} } @inproceedings{BjorklundKK17, author = {Andreas Bj{\"{o}}rklund and Petteri Kaski and Ioannis Koutis}, editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl}, title = {Directed {H}amiltonicity and Out-Branchings via Generalized {L}aplacians}, booktitle = {44th International Colloquium on Automata, Languages, and Programming, {ICALP} 2017, July 10-14, 2017, Warsaw, Poland}, series = {LIPIcs}, volume = {80}, pages = {91:1--91:14}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2017}, url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.91}, doi = {10.4230/LIPIcs.ICALP.2017.91}, timestamp = {Tue, 11 Feb 2020 15:52:14 +0100}, biburl = {https://dblp.org/rec/conf/icalp/BjorklundKK17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{Tao07, author = {Terence Tao}, title = {Structure and Randomness in Combinatorics}, booktitle = {48th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS} 2007), October 20-23, 2007, Providence, RI, USA, Proceedings}, pages = {3--15}, publisher = {{IEEE} Computer Society}, year = {2007}, url = {https://doi.org/10.1109/FOCS.2007.68}, doi = {10.1109/FOCS.2007.68}, timestamp = {Wed, 16 Oct 2019 14:14:54 +0200}, biburl = {https://dblp.org/rec/conf/focs/Tao07.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @InProceedings{BjorklundW19, author = {Andreas Bj{\"o}rklund and Ryan Williams}, title = {{Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {25:1--25:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10601}, URN = {urn:nbn:de:0030-drops-106018}, doi = {10.4230/LIPIcs.ICALP.2019.25}, annote = {Keywords: permanent, Hamiltonian cycle, orthogonal vectors} } @misc{LeePC, author = "Lee, James", howpublished = "personal communication" } @misc{LovettPC, author = "Lovett, Shachar", howpublished = "personal communication" } @misc{GouldenPC, author = "Goulden, Ian", howpublished = "personal communication" } @MISC{EllisFF15C, author = {David Ellis and Yuval Filmus and Ehud Friedgut}, title = {A quasi-stability result for low-degree {B}oolean functions on ${S}_n$}, year = {2015} } @phdthesis{LindzeyPhD, author={{Lindzey}, Nathan}, title={Matchings and Representation Theory}, journal = {{P}h{D} Thesis}, year={2018}, school={{U}niversity of {W}aterloo}, publisher="UWSpace"} @misc{AuPhD, author={{Au},Yu Hin}, title={A Comprehensive Analysis of Lift-and-Project Methods for Combinatorial Optimization}, journal = {{P}h{D} Thesis}, year={2014}, publisher="UWSpace", note={\url{https://uwspace.uwaterloo.ca/handle/10012/8662}} } @article{AuT16, author = {Yu Hin Au and Levent Tuncel}, title = {A Comprehensive Analysis of Polyhedral Lift-and-Project Methods}, journal = {SIAM Journal on Discrete Mathematics}, volume = {30}, number = {1}, pages = {411-451}, year = {2016}, doi = {10.1137/130950173}, URL = { http://dx.doi.org/10.1137/130950173 }, eprint = { http://dx.doi.org/10.1137/130950173 } } @article{StephenT99, author = {Stephen, Tamon and Tun\c{c}el, Levent}, title = {On a Representation of the Matching Polytope Via Semidefinite Liftings}, journal = {Math. Oper. Res.}, issue_date = {February 1999}, volume = {24}, number = {1}, month = feb, year = {1999}, issn = {0364-765X}, pages = {1--7}, numpages = {7}, url = {http://dx.doi.org/10.1287/moor.24.1.1}, doi = {10.1287/moor.24.1.1}, acmid = {2781634}, publisher = {INFORMS}, address = {Institute for Operations Research and the Management Sciences (INFORMS), Linthicum, Maryland, USA}, keywords = {Matching polytope, integer programming, semidefinite lifting, semidefinite programming}, } @book{ConfortiCZ, author = {Conforti, Michele and Cornuejols, Gerard and Zambelli, Giacomo}, title = {Integer Programming}, year = {2014}, isbn = {3319110071, 9783319110073}, publisher = {Springer Publishing Company, Incorporated}, } @inproceedings{ChanLRS13, author = {Chan, Siu On and Lee, James R. and Raghavendra, Prasad and Steurer, David}, title = {Approximate Constraint Satisfaction Requires Large LP Relaxations}, booktitle = {Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science}, series = {FOCS '13}, year = {2013}, isbn = {978-0-7695-5135-7}, pages = {350--359}, numpages = {10}, url = {http://dx.doi.org/10.1109/FOCS.2013.45}, doi = {10.1109/FOCS.2013.45}, acmid = {2570604}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, keywords = {linear programming, extended formulations, lower bounds, LP hierarchies, constraint satisfaction problems, approximation complexity}, } @article{Yannakakis91, author = {Mihalis Yannakakis}, title = {Expressing Combinatorial Optimization Problems by Linear Programs}, journal = {J. Comput. Syst. Sci.}, volume = {43}, number = {3}, pages = {441--466}, year = {1991}, url = {http://dx.doi.org/10.1016/0022-0000(91)90024-Y}, doi = {10.1016/0022-0000(91)90024-Y}, timestamp = {Tue, 05 Jul 2011 11:10:52 +0200}, biburl = {http://dblp.uni-trier.de/rec/bib/journals/jcss/Yannakakis91}, bibsource = {dblp computer science bibliography, http://dblp.org} } @article{Tanaka06, title = "Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs", journal = "Journal of Combinatorial Theory, Series A", volume = "113", number = "5", pages = "903 - 910", year = "2006", note = "", issn = "0097-3165", doi = "http://dx.doi.org/10.1016/j.jcta.2005.08.006", url = "http://www.sciencedirect.com/science/article/pii/S009731650500169X", author = "Hajime Tanaka", keywords = "Distance-regular graph", keywords = "Association scheme", keywords = "Erdős–Ko–Rado theorem", abstract = "Brouwer, Godsil, Koolen and Martin [Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A 102 (2003) 255–271] introduced the width w and the dual width w* of a subset in a distance-regular graph and in a cometric association scheme, respectively, and then derived lower bounds on these new parameters. For instance, subsets with the property w+w*=d in a cometric distance-regular graph with diameter d attain these bounds. In this paper, we classify subsets with this property in Grassmann graphs, bilinear forms graphs and dual polar graphs. We use this information to establish the Erdős–Ko–Rado theorem in full generality for the first two families of graphs." } @article{Haemers21, title = {Hoffman's ratio bound}, journal = {Linear Algebra and its Applications}, volume = {617}, pages = {215-219}, year = {2021}, issn = {0024-3795}, doi = {https://doi.org/10.1016/j.laa.2021.02.010}, url = {https://www.sciencedirect.com/science/article/pii/S0024379521000689}, author = {Willem H. Haemers}, keywords = {Graph, Hoffman bound, Clique, Coclique, Independence number, Eigenvalue}, abstract = {Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations.} } @article{ChenS93, author = {William Y. C. Chen and Richard P. Stanley}, title = {Derangements on the $n$-cube}, journal = {Discret. Math.}, volume = {115}, number = {1-3}, pages = {65--75}, year = {1993}, url = {https://doi.org/10.1016/0012-365X(93)90479-D}, doi = {10.1016/0012-365X(93)90479-D}, timestamp = {Fri, 12 Feb 2021 13:45:03 +0100}, biburl = {https://dblp.org/rec/journals/dm/ChenS93.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{KohKW23, title = {Alternating sign property of the perfect matching derangement graph}, journal = {Journal of Combinatorial Theory, Series A}, volume = {194}, pages = {105706}, year = {2023}, doi = {https://doi.org/10.1016/j.jcta.2022.105706}, author = {Zhi Kang Samuel Koh and Cheng Yeaw Ku and Kok Bin Wong} } @Article{Regev10, author="Amitai, Regev", title="Identities for the Number of Standard {Y}oung Tableaux in some $(k,l)$-Hooks", journal="S\'eminaire Lotharingien de Combinatoire", year="2010", volume="63", number="3", } @Article{KuLW16, author= {Ku, C.Y. and Lau, T. and Wong, K.B.}, title="Largest independent sets of certain regular subgraphs of the derangement graph", journal="Journal of Algebraic Combinatorics", year="2016", volume="44", pages="81--98" } @Article{Tokushige13, author="Tokushige, Norihide", title="The eigenvalue method for cross t-intersecting families", journal="Journal of Algebraic Combinatorics", year="2013", volume="38", number="3", pages="653--662", abstract="We show that the Erd{\H{o}}s--Ko--Rado inequality for t-intersecting families of k-element subsets of an n-element set can be easily extended to an inequality for cross t-intersecting families by using the eigenvalue method if n is relatively large depending on k and t. The same method applies to the case of t-intersecting families of k-dimensional subspaces of an n-dimensional vector space over a finite field.", issn="1572-9192", doi="10.1007/s10801-012-0419-4", url="http://dx.doi.org/10.1007/s10801-012-0419-4" } @Article{Wilson84, author="Wilson, Richard M.", title="The exact bound in the Erd{\"o}s-Ko-Rado theorem", journal="Combinatorica", year="1984", volume="4", number="2", pages="247--257", abstract="This paper contains a proof of the following result: ifn≧(t+1)(k−t−1), then any family ofk-subsets of ann-set with the property that any two of the subsets meet in at leastt points contains at most {\$}{\$}{\backslash}left( {\{}{\backslash}begin{\{}array{\}}{\{}*{\{}20{\}}c{\}} {\{}n - t{\}} {\backslash}{\backslash} {\{}k - t{\}} {\backslash}{\backslash} {\backslash}end{\{}array{\}} {\}} {\backslash}right){\$}{\$} subsets. (By a theorem of P. Frankl, this was known whent≧15.) The bound (t+1)(k-t-1) represents the best possible strengthening of the original 1961 theorem of Erd{\"o}s, Ko, and Rado which reaches the same conclusion under the hypothesisn≧t+(k−t) {\$}{\$}{\backslash}left( {\{}{\backslash}begin{\{}array{\}}{\{}*{\{}20{\}}c{\}} k {\backslash}{\backslash} t {\backslash}{\backslash} {\backslash}end{\{}array{\}} {\}} {\backslash}right)^3 {\$}{\$} . Our proof is linear algebraic in nature; it may be considered as an application of Delsarte's linear programming bound, but somewhat lengthy calculations are required to reach the stated result. (A. Schrijver has previously noticed the relevance of these methods.) Our exposition is self-contained.", issn="1439-6912", doi="10.1007/BF02579226", url="http://dx.doi.org/10.1007/BF02579226" } @book{James84, title = "Representations of General Linear Groups:", author = "G. D. James", year = "1984", month = "005", day = "24", doi = "10.1017/CBO9780511661921", abstract = "The most important examples of finite groups are the group of permutations of a set of n objects, known as the symmetric group, and the group of non-singular n-by-n matrices over a finite field, which is called the general linear group. This book examines the representation theory of the general linear groups, and reveals that there is a close analogy with that of the symmetric groups. It consists of an essay which was joint winner of the Cambridge University Adams Prize 1981-2, and is intended to be accessible to mathematicians with no previous specialist knowledge of the topics involved.Many people have studied the representations of general linear groups over fields of the natural characteristic, but this volume explores new territory by considering the case where the characteristic of the ground field is not the natural one. Not only are the results in the book elegant and interesting in their own right, but they suggest many lines for further investigation.", publisher = "Cambridge University Press", url = "https://www.cambridge.org/core/books/representations-of-general-linear-groups/3DC883624B5E3EE836F703F52E1C5B67", isbn = "9780511661921", address = "Cambridge" } @book{CCPS, author = {Cook, William J. and Cunningham, William H. and Pulleyblank, William R. and Schrijver, Alexander}, title = {Combinatorial Optimization}, year = {1998}, isbn = {0-471-55894-X}, publisher = {John Wiley \& Sons, Inc.}, address = {New York, NY, USA}, } @book{Kerber, title={Applied Finite Group Actions}, author={Kerber, A.}, isbn={9783662111680}, series={Algorithms and Combinatorics}, url={https://books.google.ca/books?id=b9b7sgEACAAJ}, year={2014}, publisher={Springer Berlin Heidelberg} } @Article{Giannelli13, author="Giannelli, Eugenio", title="On the decomposition of the Foulkes module", journal="Archiv der Mathematik", year="2013", volume="100", number="3", pages="201--214", abstract="The Foulkes module {\$}{\$}{\{}H^{\{}(a^b){\}}{\}}{\$}{\$} is the permutation module for the symmetric group S ab given by the action of S ab on the collection of set partitions of a set of size ab into b sets each of size a. The main result of this paper is a sufficient condition for a simple {\$}{\$}{\{}{\backslash}mathbb{\{}C{\}} S{\_}{\{}ab{\}}{\}}{\$}{\$} -module to have zero multiplicity in {\$}{\$}{\{}H^{\{}(a^b){\}}{\}}{\$}{\$} . A special case of this result implies that no Specht module labelled by a hook partition (ab − r, 1 r ) with r ≥ 1 appears in {\$}{\$}{\{}H^{\{}(a^b){\}}{\}}{\$}{\$} .", issn="1420-8938", doi="10.1007/s00013-013-0496-1", url="http://dx.doi.org/10.1007/s00013-013-0496-1" } @inproceedings{LeeRS15, author = {Lee, James R. and Raghavendra, Prasad and Steurer, David}, title = {Lower Bounds on the Size of Semidefinite Programming Relaxations}, booktitle = {Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing}, series = {STOC '15}, year = {2015}, isbn = {978-1-4503-3536-2}, location = {Portland, Oregon, USA}, pages = {567--576}, numpages = {10}, url = {http://doi.acm.org/10.1145/2746539.2746599}, doi = {10.1145/2746539.2746599}, acmid = {2746599}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {approximation complexity, lower bounds on positive-semidefinite rank, polynomial optimization, quantum learning, semidefinite programming, sum-of-squares method}, }